Catalan Numbers

The Catalan numbers $C_n$ count a remarkable variety of combinatorial structures: $$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!\, n!}$$ What they count: - Balanced strings of $n$ pairs of parentheses - Full binary trees with $n+1$ leaves - Monotonic lattice paths from $(0,0)$ to $(n,n)$ that don't cross the diagonal - Triangulations of a convex $(n+2)$-gon - Non-crossing partitions of $\{1, \ldots, n\}$ Recurrence: $C_0 = 1$, and $C_{n+1} = \sum_{k=0}^{n} C_k C_{n-k}$. Generating function: $C(x) = \frac{1 - \sqrt{1-4x}}{2x}$. Intuition: Catalan numbers arise whenever you have a "ballot problem" structure — counting paths that stay on one side of a boundary. The reflection principle or cycle lemma proves the formula. When to use: If a problem asks you to count something and the first few values are 1, 1, 2, 5, 14, 42 — it's Catalan. First few values: $C_0 = 1,\ C_1 = 1,\ C_2 = 2,\ C_3 = 5,\ C_4 = 14,\ C_5 = 42$.