Catalan Numbers

C_n = 1/n+1 2nn — balanced parens, binary trees, Dyck paths.

The idea

The Catalan numbers $C_{0}, C_{1}, C_{2}, \ldots = 1, 1, 2, 5, 14, 42, 132, \ldots$ answer several counting problems at once: the strings of $n$ pairs of parentheses in which every parenthesis closes properly, the full binary trees with $n$ splits, the ways to cut a convex polygon into triangles along non-crossing diagonals. Each problem counts arrangements of two kinds of move in which one kind must never get ahead of the other.

The standard model is a lattice path. Walk from $(0,0)$ to $(n,n)$ in $n$ right steps and $n$ up steps. Two walks are the same path exactly when they take the same steps in the same order; how the picture is drawn is not part of the object. Call a path good when at every moment it has taken at least as many right steps as up steps, so that it never rises above the diagonal $y = x$.

The $n$th Catalan number $C_n$ is the number of good paths, and $C_n = \frac{1}{n+1}\binom{2n}{n}.$ Reading a right step as an opening parenthesis and an up step as a closing one turns "never rises above the diagonal" into "never closes a parenthesis before opening it", so the parenthesis problem has the same count.

Ways to work on it

• Walkthrough. Meet the Catalan numbers through balanced parentheses, and verify their recursion.
• Proof. See why the Dyck-path count is 2nn - 2nn-1 — the reflection principle.
• Practice. Compute small Catalan numbers from the formula.
• Hardest. Decide whether a counting problem is answered by a Catalan number or by a different formula.

Not sure where to start? Take the ten-question placement test.