One Sequence Counts Brackets, Trees and Triangulations

Why a parser cannot try every option

The number of ways to bracket a chain of multiplications is a Catalan number, and it passes a billion before the chain reaches twenty terms. Matrix multiplication is associative, so every bracketing gives the same product — but they do not all cost the same, and the difference between the best and worst orders can be orders of magnitude of arithmetic. Enumerating the possibilities to find the cheapest is therefore hopeless beyond a handful of matrices, and the standard solution is dynamic programming, which finds the optimum in cubic time by never re-solving the same subproblem. The Catalan number is what that algorithm avoids.

The bracket picture explains the whole family

Every one of these problems is a sequence of steps that must never go negative. Read an opening bracket as plus one and a closing bracket as minus one, and a valid string is exactly a walk that ends at zero without ever dipping below it. A binary tree traversed in order gives the same walk; so does a triangulation, and so does a queue that must never serve a customer who has not arrived. Once the disguise is off, one counting argument covers them all, and the standard proof is a reflection trick that counts the bad walks by mirroring them into a set that is easy to count.

Frequently asked questions

Why does the sequence start with two ones?

Because there is exactly one way to do nothing and exactly one way to do the smallest possible thing. With zero pairs of brackets the empty string is the only valid arrangement, and with one pair there is only one way to place it. Sequences that count arrangements very often begin this way, and the repeated one is a sign the definition has been extended sensibly to the empty case rather than starting arbitrarily at the first interesting value. It also matters computationally: the recurrence needs both of them as a base before it can generate anything else.

How fast do these numbers actually grow?

A little under four times per step, and the ratio creeps upward towards four as n grows: from the nineteenth term to the twentieth it is 3.714, and from the twenty-ninth to the thirtieth it is 3.807. That places them between the exponential growth of powers of two and the far more violent growth of factorials — enough to defeat brute force quickly, not enough to defeat it instantly. In practice the crossover is around twenty: below that an exhaustive search is often fine, above it something cleverer is required, and the exact point depends on how much work each case costs.