= Catalan recurrence
{c}
{title2=$C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}$}
The <first-return decomposition of a Dyck path> and the <rule of product> give
$$
\boxed{C_0=1,\qquad C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}\quad(n\geq1).}
$$
For a given $k$, choose the inside path in $C_k$ ways and its suffix in $C_{n-1-k}$ ways. Different first-return locations give disjoint groups, so the <rule of sum> adds their counts. For $n=4$, the terms are $1\cdot5+1\cdot2+2\cdot1+5\cdot1=14$. Iterating the <recurrence relation> computes the counts without enumerating every full path.
Back to article page
