Catalan Number Calculator

Catalan numbers are a sequence of natural numbers with many applications in combinatorics. C(n) = (2n)! / ((n+1)! * n!). The first few are C(0)=1, C(1)=1, C(2)=2, C(3)=5, C(4)=14, C(5)=42. They were studied by Eugène Catalan in the 19th century, though earlier work by Chinese mathematician Mingantu predates Catalan.

Catalan numbers count many combinatorial structures. C(n) equals: the number of valid sequences of n pairs of matching parentheses; the number of full binary trees with n+1 leaves; the number of ways to triangulate a convex polygon with n+2 sides; the number of monotonic paths from (0,0) to (n,n) that never cross above the main diagonal.

Yes. C(0) = 1 and C(n+1) = sum of C(i) * C(n-i) for i from 0 to n. This reflects the combinatorial interpretation: a balanced parenthesisation of length 2(n+1) splits at its first matching close-paren, giving two sub-sequences whose lengths multiply by the Catalan recurrence.

Catalan numbers grow approximately as 4^n / (n^(3/2) * sqrt(pi)). C(10) = 16,796, C(15) = 9,694,845, and C(20) = 6,564,120,420. The exact formula C(n) = (2n)! / ((n+1)! * n!) always gives an integer, though for large n both the numerator and denominator are enormous.

Eugène Catalan (1814-1894) was a Belgian mathematician who studied these numbers in the context of parenthesisation problems. However, the sequence was independently discovered earlier by Chinese mathematician Mingantu around 1730, and it also appears in Euler's work on polygon triangulations from 1751.