The Catalan Family

$C_{n} = \frac{1}{n + 1} (n 2 n) = (n 2 n) - (n + 1 2 n), C_{n + 1} = \sum_{i = 0}^{n} C_{i} C_{n - i} .$

$1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, \dots$

A remarkable number of apparently unrelated problems have this answer — and they are all in bijection with one another.

The family

Problem (size $n$ )	Count
Balanced bracket sequences of length $2 n$	$C_{n}$
Binary trees with $n$ internal nodes	$C_{n}$
Full binary trees with $n + 1$ leaves	$C_{n}$
Triangulations of a convex $(n + 2)$ -gon	$C_{n}$
Ways to parenthesise $n + 1$ factors	$C_{n}$
Monotone lattice paths from $(0, 0)$ to $(n, n)$ staying below the diagonal	$C_{n}$
Non-crossing chord diagrams on $2 n$ points	$C_{n}$
Non-crossing partitions of $[n]$	$C_{n}$
Permutations avoiding any one 3-pattern (e.g. 231)	$C_{n}$
Standard Young tableaux of shape $2 \times n$	$C_{n}$
Mountain ranges with $n$ up and $n$ down strokes	$C_{n}$
Ways to stack $n$ coins in a triangular pile	$C_{n}$
Rooted plane trees with $n + 1$ vertices	$C_{n}$
Dyck words of length $2 n$	$C_{n}$
Stack-sortable permutations of $[n]$	$C_{n}$

Recognising any one of these tells you the answer to all of them.

The reflection principle

Paths from $(0, 0)$ to $(n, n)$ using right and up steps that never cross above the diagonal:

$(n 2 n) - (n + 1 2 n) = C_{n} .$

The subtracted term counts the bad paths. Reflect the portion of a bad path after its first violation across the line $y = x + 1$ ; this is a bijection between bad paths and unrestricted paths to $(n + 1, n - 1)$ , which number $(n + 1 2 n)$ .

The reflection argument is the technique, and it generalises far beyond Catalan numbers:

Ballot problem: paths to $(a, b)$ with $a > b$ staying strictly above the diagonal number $\frac{a - b}{a + b} (a a + b)$ .
Paths with a shifted boundary: subtract the reflected count.
Paths between two boundaries: inclusion-exclusion over repeated reflections.

Computing them

// O(n) with factorials mod p
long long catalan(int n) {
    return fact[2*n] % MOD * invFact[n] % MOD * invFact[n+1] % MOD;
}
 
// O(n) iteratively
// C[0] = 1;  C[i] = C[i-1] * 2*(2i-1) / (i+1)
long long c = 1;
for (int i = 1; i <= n; i++)
    c = c % MOD * (2 * (2*i - 1) % MOD) % MOD * inv[i + 1] % MOD;

The recurrence $C_{n + 1} = \sum C_{i} C_{n - i}$ is $O (n^{2})$ directly, or $O (n lo g n)$ as a convolution — but the closed form makes both unnecessary unless the problem is a variant.

Generating function

$C (x) = \frac{1 - 1 - 4 x}{2 x}, C (x) = 1 + x C (x)^{2} .$

The functional equation is the recurrence: a non-empty Dyck path splits uniquely as ( A ) B with $A, B$ Dyck paths. Solving the quadratic gives the closed form — a good demonstration of generating functions doing real work.

The relatives

Sequence	Counts	Formula
Narayana $N (n, k)$	Dyck paths with exactly $k$ peaks	$\frac{1}{n} (k n) (k - 1 n)$ ; $\sum_{k} N = C_{n}$
Motzkin	paths with up/down/flat steps	1,1,2,4,9,21,51
Schröder	paths with diagonal steps	1,2,6,22,90
Ballot numbers	paths to $(a, b)$ staying above	$\frac{a - b}{a + b} (a a + b)$
$k$ -Catalan	$k$ -ary trees	$\frac{1}{( k - 1 ) n + 1} (n k n)$
Bell	set partitions (all, not non-crossing)	1,1,2,5,15,52

Note that Catalan and Bell agree up to $n = 2$ then diverge — the difference is non-crossing versus arbitrary partitions.

The cycle lemma — a bijective proof

For a sequence of integers $\geq - 1$ summing to $k > 0$ , exactly $k$ of its $n$ rotations have all prefix sums positive.

Applied with $k = 1$ to sequences of $n + 1$ ones and $n$ minus-ones, it gives $\frac{1}{2 n + 1} (n 2 n + 1) = C_{n}$ directly — a proof with no algebra at all. The same lemma is why the gas station problem has a unique answer.

Why it is worth knowing

Two reasons: the sequence itself is worth recognising on sight (compute 6 terms, compare against $1, 1, 2, 5, 14, 42$ ), and the reflection principle is a genuinely reusable counting technique for any lattice-path problem with a boundary.

whoashish's cp notes

Directory