One number sequence counts brackets, tree shapes, mountain paths and triangulated polygons
How many ways can three pairs of brackets be correctly nested? Five. How many ways can a pentagon be cut into triangles with non-crossing diagonals? Also five. The match is no accident. Both answers come from the Catalan numbers, a sequence that turns up in at least 66 different counting puzzles.
The sequence begins 1, 1, 2, 5, 14, 42, 132, 429, 1430 and grows roughly fourfold at each step for large terms. It carries the name of Eugène Catalan, but the Mongolian mathematician Minggatu had already found it in the 1730s. A compact formula gives each term from central binomial coefficients, and a recurrence builds each one by pairing up all the smaller terms, which hints at why it keeps appearing: many objects split naturally into a left part and a right part.
The combinatorialist Richard Stanley collected 66 interpretations as exercises in his Enumerative Combinatorics. The same numbers count full binary trees with a given number of leaves, which matters in language processing because each tree is a possible parse of a sentence. They count the ways to group factors in a chain of multiplications. They count staircase paths across a square grid that never rise above the diagonal, moving only right or up. They count permutations with no three-term increasing run: for three items, those are 132, 213, 231, 312 and 321.
The sequence has curious arithmetic quirks. Only two of its terms are prime, 2 and 5. The odd terms occur only at positions one less than a power of two, and nearly all odd terms end in the digit 5; the known exceptions include 429.
There is a probabilistic reading too. Picture a walker stepping randomly left or right along a number line, starting at zero, with a trap one step to the left. The number of ways to fall into the trap at each odd-numbered step is a Catalan number, and because such a walk always eventually returns, those possibilities add up to certainty.
Source: Catalan number
