Concept
The same numbers appear in counting parentheses, trees, and lattice paths.
Understand it in one breath
The same sequence appears in many counting problems that initially look unrelated. The number of balanced strings with n pairs of parentheses, full binary trees with n internal nodes, and triangulations of an (n+2)-gon is Cₙ. Bijections between those objects reveal much of the fun of combinatorics.
At a glance
n | Cₙ | Meaning (example) |
|---|---|---|
| 0 | 1 | Empty expression |
| 1 | 1 | () |
| 2 | 2 | ()(), (()) |
| 3 | 5 | 5 balanced-parenthesis strings |
| 4 | 14 | 14 binary-tree shapes |
| 5 | 42 | 42 triangulations of a heptagon |
| 6 | 132 | |
| 7 | 429 | |
| 8 | 1430 |
One sequence answers dozens of seemingly different counting problems.
Key formula
Cₙ = 1, 1, 2, 5, 14, 42, 132, ...
Key moments
Euler — polygon triangulations
Euler counted ways to triangulate a polygon, bringing the sequence 1, 2, 5, 14, 42, … into view.
Catalan — parenthesized expressions
Belgian mathematician Eugène Catalan studied the same counting pattern through parenthesized products. The sequence later took his name.
214 different interpretations
Richard Stanley assembled 214 distinct combinatorial interpretations of the Catalan numbers — remarkably different problems with the same answer sequence.
Modern applications
Compiler parse trees, counting binary search trees, algorithm analysis, RNA secondary-structure prediction, and game trees.
Beyond MathVoyage
Loading…