A sequence that counts structure
The Catalan numbers form a sequence beginning one, one, two, five, fourteen, forty two. They appear whenever you count balanced or properly nested structures, making them one of combinatorics' most recurring patterns.
What they count
The n-th Catalan number counts:
- The valid sequences of n pairs of balanced parentheses.
- The distinct binary trees with n nodes.
- The ways to triangulate a convex polygon.
- The paths on a grid that never cross the diagonal.
All these problems share the same recursive shape, which is why one number counts them all.
Computing them
A Catalan number satisfies a recurrence: the n-th value is a sum over a split point, multiplying the Catalan numbers of the two parts. This mirrors choosing where a root or a matching pair divides the structure. Filling a table with this recurrence is straightforward. There is also a closed form using a binomial coefficient, the central one for two n, divided by n plus one.
Because the values grow fast, modular arithmetic is common when the inputs are large.
Key idea
Catalan numbers count balanced nested structures such as parentheses and binary trees; a split point recurrence or a central binomial closed form computes them, and they grow rapidly.