One sequence, counting everything

Take a convex polygon and cut it into triangles using diagonals that do not cross. How many different ways are there?

For a triangle: one, by doing nothing. A square: two, since either diagonal works. A pentagon: five. A hexagon: fourteen.

$$1, \quad 2, \quad 5, \quad 14, \quad 42, \quad 132, \quad 429, \ldots$$

The sequence turns up somewhere else immediately #

Now a question with no polygons in it. Given a product of $n$ terms that must be multiplied in pairs — as a computer would, or as anyone must when the operation is not associative — how many ways are there to insert the brackets?

For three terms there are two: $(ab)c$ and $a(bc)$. For four there are five. For five, fourteen.

The same numbers, in the same order. That could be coincidence at two terms, and it is not coincidence at fourteen.

And a third question, with neither polygons nor brackets. Walk on a grid from one corner to the opposite one, moving only right and up, never crossing above the diagonal. How many routes? For a $2\times2$ grid, two. For $3 \times 3$, five. For $4\times4$, fourteen.

And a fourth: how many distinct shapes of binary tree have $n$ leaves? $1, 2, 5, 14$.

Four questions from four subjects, one answer sequence. These are the Catalan numbers, and the explanation is not that they have something in common — it is that they are the same question.

The recursion, read off the picture #

Look again at the hexagon figure and notice what every one of the fourteen has in common: the edge at the bottom belongs to exactly one triangle, and that triangle’s third corner is one of the other four vertices.

So the fourteen split into four groups by where that third corner lands. And once it is chosen, the polygon falls apart into two smaller polygons — one on each side of the chosen triangle — which can then be cut up independently.

That gives the recursion directly. Writing $C_n$ for the number of triangulations of an $(n+2)$-gon:

$$C_n = \sum_{k=0}^{n-1} C_k\,C_{n-1-k}.$$

Each term is left piece times right piece, and the sum runs over where the apex went. For the hexagon: $C_1C_2 + C_2C_1 + C_0 C_3 + C_3C_0$, which is $1\cdot2 + 2\cdot1 + 1\cdot5 + 5\cdot1 = 14$.

That convolution — a sum of products of earlier terms — is the Catalan signature. Any counting problem whose objects split into an independent left part and right part obeys it, and the four questions above all do:

• a bracketing splits at its outermost multiplication, into a left product and a right one;
• a binary tree splits at its root, into a left subtree and a right one;
• a path splits at its first return to the diagonal, into the part before and the part after.

The polygon splits at a triangle. Four splittings, one recursion, one sequence. The recursion is doing all the work, and the four subjects are contributing only the names of their objects.

It is worth contrasting this with the recursion that produces Pascal’s triangle, because the difference explains why one sequence is famous for being everywhere and the other for being simple. Pascal’s rule adds two earlier terms; Catalan’s multiplies pairs of them and sums over the split. Addition arises when an object is built by one binary decision — take the last item or leave it. Multiplication arises when an object is built by splitting into two independent parts, each of which is a smaller object of the same kind. Any structure that decomposes recursively into two of itself will produce this sequence, and a great many structures do.

Counted, not quoted #

The figures are enumerations rather than illustrations, and the difference matters here more than usual.

The generator does not draw fourteen pictures because fourteen is the known answer. It runs the recursive splitting, collects every triangulation it produces, and then asserts that the count equals the Catalan number computed independently. If the enumeration missed one or produced a duplicate, the figure would not build.

It also checks a structural fact on each: every triangulation of an $n$-gon uses exactly $n-3$ diagonals and produces $n-2$ triangles. That is not obvious — one might expect different cuttings to use different numbers of diagonals — and it is checked on all fourteen rather than on the first.

The closed form is

$$C_n = \frac{1}{n+1}\binom{2n}{n},$$

which is a strange-looking expression and is where Pascal’s triangle enters. It says: take the middle entry of an even row, and divide by one more than half the row number. That the division always comes out whole is not obvious from the formula and is a consequence of the counting.

That extraction is worth checking by hand once, because it makes the formula concrete: row $8$’s middle entry is $70$, and $70/5 = 14$, which is the number of pictures in the opening figure.

Where the name came from, and where it did not #

The sequence is named for Eugène Charles Catalan, who worked on it in the 1830s, and the attribution is the usual sort — which is to say wrong by about a century and by several thousand miles.

Minggatu, a Mongolian mathematician at the Qing court, had the numbers by around 1730, in the course of expanding trigonometric series. Euler found them in the 1750s by asking exactly the polygon question this essay opens with, and wrote to Goldbach about the closed form. Segner supplied the recursion in 1758. Catalan arrived in 1838, working on bracketings.

So four people found the sequence by four routes over a century, and each was answering his own question. That is the strongest possible evidence for the essay’s thesis: a sequence that turns up independently that many times is not a curiosity of any one subject, and the objects being counted must be more closely related than the subjects are.

It is also a caution about names, which record who a community heard it from rather than who found it — the same accident that attached Pascal’s name to a triangle known in China, Persia and India centuries before him.

Why the division works #

The closed form has a proof that is one of the prettiest arguments in combinatorics, and it explains the $\frac{1}{n+1}$ rather than merely verifying it.

Count paths on the grid. From corner to corner in an $n \times n$ grid there are $\binom{2n}{n}$ routes in total — choose which $n$ of the $2n$ steps go right. Most of them stray above the diagonal, and those have to be removed.

The reflection trick removes them exactly. Take any bad path, find the first step at which it crosses the diagonal, and reflect everything after that point. The result is a path to a different endpoint — one shifted by one square — and the correspondence is reversible: every path to that shifted endpoint comes from exactly one bad path. So the bad paths number $\binom{2n}{n+1}$, and

$$C_n = \binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1}\binom{2n}{n}.$$

The subtraction produces the division, which is why the fraction is always whole: it was a difference of two whole numbers all along.

This is a bijection argument — the bad paths are not counted directly, they are matched one-to-one with something already countable. That move is the standard tool of the subject, and it is more powerful than counting because a matching, once found, carries every property across rather than merely the total.

The bijections, as the real content #

Which raises the question the essay has been circling. Saying that four problems obey the same recursion explains why they have the same count. A bijection would say something much stronger: that they are the same objects with different names.

They are, and the matchings are explicit.

Triangulations to bracketings. Label the polygon’s edges with the terms of the product, leaving one edge unlabelled as the answer. Each triangle in a cutting takes two labelled sides and produces a label for its third — which is a multiplication. Reading the triangles in order writes the bracketing.

Bracketings to trees. A bracketing is a tree already: each multiplication is a node, its two factors are its children. Nothing is being converted; the two notations describe one object.

Trees to paths. Walk the tree, stepping right when descending and up when returning. The constraint that the path never crosses the diagonal is the constraint that a return never precedes its descent.

Each of those maps has to be checked in both directions, and that is where the work is. It is not enough that every triangulation produces a bracketing; distinct triangulations must produce distinct bracketings, and every bracketing must arise from one. A rule satisfying the first condition and not the others proves an inequality rather than an equality, and inequalities in both directions are a common way to establish a count when no clean matching can be found.

The polygon-to-bracketing map passes because it can be run backwards: given a bracketing, the outermost multiplication names the triangle standing on the answer edge, and its two factors name the two sub-polygons, recursively. Running a construction backwards is the standard test, and a correspondence that cannot be inverted is a correspondence that has lost information.

So there is one family of objects here, and four notations for it. The Catalan numbers are not a sequence that mysteriously counts several things; they count one thing, and the mystery was an artefact of the four communities that named it separately.

That is the pattern this collection keeps meeting. Four conics from one cone, two constructions of one fractal, a signal and its spectrum — in each case the surprise was a disguise, and the work was finding the map that removes it.

How fast they grow #

The numbers grow quickly, and the rate is worth knowing because it decides what can be enumerated.

Stirling’s approximation applied to the closed form gives

$$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}},$$

so they grow like $4^n$, damped by a polynomial. The base is $4$ rather than something smaller because $\binom{2n}{n}$ is about $4^n$ — the central binomial coefficient is the largest entry of a row summing to $2^{2n}$, and it captures a $1/\sqrt{n}$ share of it, which is the same central concentration a Galton board displays.

Practically: a $12$-gon has $16{,}796$ triangulations, a $22$-gon has about $6.6 \times 10^9$, and a $32$-gon about $3.8 \times 10^{15}$. Drawing them all stops being possible somewhere around ten sides, and the figures here stop at seven for that reason.

There is a $\pi$ in the growth formula, and it arrived from Stirling rather than from any circle — the same uninvited appearance that shows up whenever a factorial is approximated.

What the picture cannot show #

The gallery shows every triangulation of a hexagon, which is a complete enumeration and therefore a genuine proof that the count is fourteen — a rare thing on this site, where most figures stand in for a general claim.

That completeness is exactly what does not generalise. At six sides the figure proves its caption; at twelve there are sixteen thousand and no figure proves anything. So this is a case where the picture is a proof precisely in the range where the answer was never in doubt, and stops being one at the point where it would be useful.

The figures also cannot show the bijections, which are the section that matters most. A correspondence between a triangulation and a bracketing is a map — a claim about two collections at once — and a page can show two objects side by side but not the rule joining them, still less that the rule is one-to-one. Every bijection in the previous section was described in prose because that is the only place it could be described.

The ladder from here #

Rungs above: the reflection argument drawn on the grid, with a bad path and its reflection side by side. The bijections given figures, one rung each. Generating functions, where $C(x) = 1 + xC(x)^2$ solves by the quadratic formula and produces the closed form in three lines. Dyck words and the balanced-brackets formulation. The Catalan numbers modulo small primes, where a fractal appears for Lucas’ reason. Non-crossing partitions and the many other objects the sequence counts — Stanley’s list runs past two hundred. Associahedra, where the triangulations become the vertices of a polytope. And the ballot problem, which is the reflection argument in its original clothing.

The habit #

The lesson is about what to do when two counts agree.

The weak response is to note the coincidence and check another term. The strong response is to look for a bijection — a rule turning each object of one kind into exactly one object of the other — because a bijection explains the agreement rather than confirming it, and it usually transfers everything else too. Once triangulations and binary trees are known to be the same objects, every theorem about one is a theorem about the other, for free.

Matching counts on their own prove very little, and Kepler’s five solids and six planets is the standing reminder of how little. The difference between that and this one is that here the correspondence was found, and finding it is the whole of the work.