Catalan recurrence ($C_n={\sum }_{k=0}^{n-1}{C}_k{C}_{n-1-k}$)

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.

The ordinary generating function $C(x)={\sum }_{n\ge 0}{C}_n{x}^n$ packages the Catalan recurrence. Its Cauchy product gives the formal power series identityThe constant term is $C_0=1$. Solving the quadratic equation chooseswith the formal power series square root having constant term one. The apparent quotient at $x=0$ has constant term one after cancellation; the other quadratic solution has a pole and cannot be this ordinary generating function. The equation records the empty object or an outer unit with two ordered smaller objects.