Overview
Count the shapes of a binary search tree, the valid ways to nest brackets, or the triangulations of a polygon, and the same numbers keep appearing: 1, 1, 2, 5, 14, 42, 132.
How to solve 1, 1, 2, 5, 14, …?
- Pick the root of the tree. If it has k keys on the left, it has n−1−k on the right.
- That gives the recurrence Cₙ = Σ Cₖ · Cₙ₋₁₋ₖ over all splits — a convolution, not a simple difference.
- Summing it gives the closed form Cₙ = C(2n, n)/(n + 1), so C₅ = 252/6 = 42.
The key insight
Every Catalan object is secretly the same object: a balanced bracket string IS a tree shape IS a lattice path that never crosses the diagonal. Once you see one bijection, the whole family collapses into a single count.
Variations & echoes
- Cₙ also counts the ways to fully parenthesise a product of n + 1 factors — the reason it shows up in matrix-chain DP.
- The ratio Cₙ₊₁/Cₙ tends to 4, so Catalan numbers grow roughly like 4ⁿ/n^1.5.
Frequently asked questions
Why do differences not reveal the pattern?
Because the sequence is built by multiplying and convolving, not adding. Ratios (or the closed form) expose it; differences never will.