 Catalan recurrence

The first-return decomposition of a Dyck path and the rule of product giveFor 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\cdot 5+1\cdot 2+2\cdot 1+5\cdot 1=14$. Iterating the recurrence relation computes the counts without enumerating every full path.