The Catalan numbers \(C_n = \binom{2n}{n}/(n+1)\) form one of the most ubiquitous sequences in combinatorics: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796.
They count an enormous number of seemingly unrelated structures, including:
- The number of ways to triangulate a convex \((n+2)\)-gon
- The number of valid arrangements of \(n\) pairs of parentheses
- The number of full binary trees with \(n+1\) leaves
- The number of monotonic lattice paths along the edges of a grid that don't cross above the diagonal
- The number of ways to form a "mountain range" with \(n\) upstrokes and \(n\) downstrokes
Named after Belgian mathematician Eugène Catalan who studied them in the 1830s, though they had appeared in Chinese mathematics centuries earlier.