The idea: one count, many shapes

The Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, … (starting from C₀ = 1). They count a surprising number of different things. For n = 3 there are exactly 5 balanced strings of 3 pairs of parentheses, 5 binary trees with 3 nodes, 5 lattice paths across a 3×3 grid that never go above the diagonal, and 5 ways to cut a pentagon into triangles. (Demo 1: n = 3 three ways)

Five columns. Top row: the strings ((())), (()()), (())(), ()(()), ()()(). Middle row: the matching binary trees with nodes a, b, c. Bottom row: the matching lattice paths on a 3 by 3 grid, all on or below the dashed diagonal. Each node's colour is shared by its pair of parentheses and its two path steps
For n = 3 each row has 5 objects, and column by column they are the same object: one colour per node, its pair of parentheses and its two path steps.

Balanced parentheses

A string of n '(' and n ')' is balanced when, reading left to right, the number of ')' never gets ahead of the number of '('. For n = 3 they are ((())), (()()), (())(), ()(()) and ()()(). The same rule describes a stack that is never popped when empty, or a mountain range drawn with up and down strokes that never goes below sea level (a Dyck path).

Matching parentheses, trees and paths

A binary tree is either empty or a root with a left and a right subtree (either may be empty). Turn a tree T into a string with one rule:

w(empty) = ""    w(T) = "(" + w(left) + ")" + w(right)

Each node gives one pair of parentheses: its '(' comes first, the left subtree sits inside the pair and the right subtree after it. The rule also runs backwards, so it is a bijection: different trees give different strings and every balanced string comes from a tree. On the canvas the nodes are named a, b, c in the order of their '(' (preorder).

A string becomes a lattice path by reading '(' as a step right and ')' as a step up. After any prefix the path is at (number of '(', number of ')'), so "never more ')' than '('" is exactly "never above the diagonal y = x". Match walks through one object character by character: the character, the tree node and the path step light up together. (Demo 2: the bijection)

The recurrence and the DP table

Split a tree with n nodes at its root: the left subtree has i nodes and the right subtree n−1−i, for i = 0 … n−1. The two sides are chosen independently, so

C₀ = 1    Cₙ = C₀·Cₙ₋₁ + C₁·Cₙ₋₂ + … + Cₙ₋₁·C₀ = Σi=0..n−1 Cᵢ·Cₙ₋₁₋ᵢ

A root node with a left triangle labelled i nodes, C sub i shapes, and a right triangle labelled n minus 1 minus i nodes. Below, for n equals 3: i equals 0 gives 1 times 2, i equals 1 gives 1 times 1, i equals 2 gives 2 times 1, total 5
Fixing the size of the left subtree splits the count into a product; adding over all sizes gives C₃ = 2 + 1 + 2 = 5.

Filling a table from C₀ upward is dynamic programming, just like Fibonacci, except that each entry looks at all earlier entries, so the table to n costs O(n²) multiplications:

nCₙ = Σ Cᵢ·Cₙ₋₁₋ᵢCₙ
11·11
21·1 + 1·12
31·2 + 1·1 + 2·15
41·5 + 1·2 + 2·1 + 5·114
51·14 + 1·5 + 2·2 + 5·1 + 14·142
61·42 + 1·14 + 2·5 + 5·2 + 14·1 + 42·1132

For n = 3 the three terms are visible in the gallery: trees #4 and #5 have an empty left subtree (1·2), tree #3 has one node on each side (1·1), trees #1 and #2 have two nodes on the left (2·1). (Demo 3: the recurrence table) The same split counts the shapes of a binary search tree built from n distinct keys.

The reflection trick: C(2n,n) / (n+1)

There is also a closed formula. A monotone path from (0,0) to (n,n) is n right steps and n up steps in any order, so there are C(2n,n) of them (the binomial coefficients of Pascal's triangle). Call a path bad when it goes above the diagonal. A bad path must touch the line y = x + 1.

Take a bad path and, after its first touch of y = x + 1, swap every right step with an up step. That mirrors the rest of the path in the line, and the end point (n,n) moves to (n−1, n+1). Every path to (n−1, n+1) ends above the line, so it touches it, and mirroring back gives a bad path: bad paths and paths to (n−1, n+1) match one to one.

A 3 by 4 grid with the grey diagonal y equals x and the red line y equals x plus 1. A blue path R U U goes from (0,0) to (1,2) on the red line; the faded tail R R U ends at (3,3); the purple mirrored tail U U R ends at (2,4). Text: 20 paths minus 15 bad paths equals 5
Mirroring the tail after the first touch of y = x + 1 turns each bad path into a path to (2,4), so there are C(6,2) = 15 bad paths and 20 − 15 = 5 good ones.

So

Cₙ = C(2n,n) − C(2n,n+1) = C(2n,n) · (1 − n/(n+1)) = C(2n,n) / (n+1)

For n = 3: C(6,3) − C(6,2) = 20 − 15 = 5 = 20 / 4. For n = 6: 924 / 7 = 132, matching the table. (Demo 4: the reflection trick)

Triangulations and other Catalan families

A convex polygon with n + 2 sides can be cut into n triangles by non-crossing diagonals in Cₙ ways: a pentagon in 5 ways, a hexagon in 14. Fix the bottom edge: the triangle standing on it is the root, the polygon on its left is the left subtree and the polygon on its right the right subtree. On the canvas each triangle carries the name of its tree node. (Demo 5: triangulations of a pentagon)

Other things counted by Cₙ: the ways to fully parenthesize a product of n + 1 factors (the order of matrix multiplications), stack-sortable permutations, full binary trees with n + 1 leaves, non-crossing handshakes of 2n people around a table, and mountain ranges with n up and n down strokes.

The numbers grow roughly like 4ⁿ / (n3/2·√π): C₁₀ = 16 796 and C₂₀ = 6 564 120 420. The ratio Cₙ₊₁ / Cₙ = 2(2n+1)/(n+2) approaches 4, so the next value is easy to compute from the last one.

What the page leaves out

Only n = 3 is drawn object by object; the table stops at n = 6. The generating function C(x) = 1 + x·C(x)², which gives the closed formula by solving a quadratic, the cycle lemma (another proof of the 1/(n+1)), ballot numbers, and the many other Catalan families are only described, not animated.