Catalan Numbers
The Catalan numbers 1, 1, 2, 5, 14, 42, 132, ... are one of the most ubiquitous sequences in combinatorics. They count Dyck paths, binary trees, polygon triangulations, and over 200 other combinatorial structures.
Catalan Number Values
Properties
How it works
The n-th Catalan number Cn counts the number of ways to arrange n pairs of matching parentheses. Equivalently, it counts lattice paths from (0,0) to (n,n) using only right and up steps that never go below the diagonal — these are called Dyck paths, and when drawn as mountain ranges they form beautiful non-crossing profiles.
The same number also counts the distinct binary trees with n internal nodes, and the number of ways to triangulate a convex polygon with n+2 sides. These seemingly unrelated structures are all in bijection with each other — there is a one-to-one correspondence between any two of them.
The Catalan numbers satisfy the recurrence Cn+1 = Σi=0n Ci Cn-i, which reflects the decomposition of a Dyck path into its first "arch" and the remaining path, or equivalently the decomposition of a binary tree into its left and right subtrees.
The closed-form formula Cn = (2n)! / ((n+1)! n!) = 1⁄n+1 C(2n, n) can be derived from the ballot problem or through generating functions. The sequence grows asymptotically as 4n / (n3/2√π), showing exponential growth modulated by a polynomial correction.
There are over 200 known combinatorial interpretations of the Catalan numbers, making them one of the most well-connected sequences in all of mathematics. They appear in algebra (associativity of products), geometry (polygon dissections), computer science (parse trees), and even probability (random walk excursions).