How Many Ways Can You Bracket That Expression? The Same Sequence Every Time
By the BrainSnail editorial team. How these articles are written and checked, and how to tell us when one is wrong.
One sequence of numbers answers dozens of counting questions that appear completely unrelated, and finding that a new problem produces it is a strong hint about its structure.
Where the sequence turns up
Count the ways of inserting brackets into a product of several terms so that multiplication happens two at a time. Count the ways a convex polygon can be cut into triangles by non-crossing diagonals. Count the paths from one corner of a grid to the opposite one that never cross the diagonal. Count sequences of opening and closing brackets that are properly matched. Count the shapes a branching structure can take with a given number of splits. Every one of those produces the same numbers, beginning one, one, two, five, fourteen, forty two and one hundred thirty two.
The pattern in the numbers
Several facts about the sequence are worth having:
- •Each term can be built from all the earlier ones combined in pairs
- •There is also a direct formula using binomial coefficients
- •The terms grow roughly by a factor of four each time
- •Only the first two terms are odd, and the pattern of parity is regular
- •Every term counts something, so they are all whole numbers
- •That whole number property is not obvious from the formula
Why the problems are the same
The shared structure is recursion in a particular shape, and seeing it once makes all the examples obvious. Each of these problems can be solved by choosing a split point, solving the two smaller problems on either side independently, and adding up over every possible split. Bracketing a product splits it at the last multiplication. Triangulating a polygon splits it at the triangle containing one fixed edge. A path splits at the point it first returns to the diagonal. Because every problem reduces the same way, they all satisfy the same recursion and therefore produce the same numbers.
One problem solved twice
A single problem shows the structure particularly clearly and is worth working through. Suppose votes are counted one at a time in a two candidate election that ends in a tie, and ask in how many orders the counting can proceed so that one candidate is never behind. Each such order is a sequence of steps up and down that starts and ends level and never goes below the starting line, which is exactly the matched bracket problem in another costume. Counting them by subtracting the bad orders from all orders produces the formula directly, which is the neatest of the standard derivations.
Where the name came from
The numbers were in use well before the name attached to them, which is a common pattern in mathematics. Mongolian and Chinese mathematicians studied them in the eighteenth century in the context of counting geometric configurations. Leonhard Euler posed the polygon triangulation question in the 1750s and found the formula. Eugene Charles Catalan worked on the bracketing problem in the 1830s, and the name stabilised much later through an influential textbook. The sequence now has hundreds of documented interpretations, collected and catalogued, and new ones are still being added.
The takeaway
One sequence beginning one, one, two, five, fourteen and forty two counts bracketings of a product, triangulations of a polygon, matched bracket sequences, non-crossing lattice paths and branching shapes. They agree because each problem splits into two independent smaller copies of itself at a chosen point. Euler found the formula in the 1750s, long before the name was attached.