How to count Catalan numbers and identify their combinatorial interpretations?

**Recurrence to Closed Form:** Catalan numbers satisfy $C_0 = 1$ and $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$. Let $C(x) = \sum_{n=0}^{\infty} C_n x^n$ be the generating function. The recurrence gives: $$C(x) = 1 + x C(x)^2$$ Solving: $x C(x)^2 - C(x) + 1 = 0 \Rightarrow C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$. Expanding $\sqrt{1 - 4x}$ using the binomial theorem gives the closed form: $$C_n = \frac{1}{n+1} \binom{2n}{n}$$ **Combinatorial Interpretations (all counted by $C_n$):** | Interpretation | Example for $n = 3$ | |---|---| | Valid parentheses ($n$ pairs) | ((())), (()()), (())(), ()(()), ()()() | | Binary trees with $n$ nodes | 5 distinct trees | | Triangulations of $(n+2)$-gon | 5 ways to triangulate a pentagon | | Dyck paths of length $2n$ | Paths from $(0,0)$ to $(2n,0)$ staying above diagonal | | Non-crossing partitions of $\{1,\ldots,n\}$ | 5 partitions | | Stack-sortable permutations of length $n$ | 5 permutations | **Parentheses example ($n = 3$):** A sequence of $n$ opening and $n$ closing parentheses is valid if at any prefix, #($\geq$ #). This is exactly a Dyck path: $\uparrow$ for "(", $\downarrow$ for ")". **Binary trees:** A binary tree with $n$ nodes: pick $i$ nodes for the left subtree ($0 \leq i \leq n-1$), the remaining $n-1-i$ go to the right. This gives $C_n = \sum C_i C_{n-1-i}$. **Triangulations of a convex $(n+2)$-gon:** Pick one triangulation, fix edge $(1, n+2)$, and the third vertex $k$ of the triangle containing it splits the polygon into a $k$-gon and an $(n+3-k)$-gon, giving the recurrence. These many interpretations make Catalan numbers one of the most ubiquitous sequences in combinatorics.