One word, and four objects

Two sets have the same size. There are two ways to establish that, and they are not equally good.

The first is to count both and compare the numbers. That is a proof, it is often the only route available, and it leaves the question of why entirely open — two sets of size fourteen may have nothing to do with each other. The second is to produce a rule that turns each element of one into an element of the other and back again. That does not merely establish the equality; it explains it, and it usually turns out that everything one set knows how to do, the other now knows too.

The Catalan numbers count so many things that the first method would be exhausting and the second is available everywhere. Richard Stanley’s catalogue of objects counted by them runs past two hundred, and the reason it is a catalogue rather than a list of coincidences is that the entries are connected by explicit translations.

The word is the common ancestor #

Every one of the four objects can be produced from a single balanced word — a string of ups and rights with as many of each, never having taken more rights than ups. It is worth saying why that particular object is the natural centre rather than an arbitrary choice of starting point.

A balanced word has a unique decomposition. Read it from the left and follow the running difference between ups and rights; there is a first moment at which the difference returns to zero. Split there. The word is

$$w = \texttt{U}\,\alpha\,\texttt{R}\,\beta$$

where $\alpha$ and $\beta$ are themselves balanced words, possibly empty. That decomposition is forced — the split point is the first return, which is not a choice — and it is the only structure the word has.

Every one of the four objects has exactly the same decomposition, and that is the whole of the correspondence. A binary tree is a root with a left subtree and a right subtree. A triangulated polygon has a triangle standing on a distinguished edge, and removing it leaves two smaller polygons. A path splits at its first return to the diagonal into an excursion and a remainder. In each case: a marker, and two smaller objects of the same kind.

So the four are not four objects that turn out to be equinumerous. They are four notations for the same recursive shape, and any two of them are translated through it.

The translations, one at a time #

Word to brackets. Write an opening bracket for each up and a closing bracket for each right. The condition “never more rights than ups” becomes “never close what was not opened”, which is what makes a bracket string well-formed. This is a relabelling rather than a construction, which is why the two are usually treated as the same object.

Word to tree. The decomposition $\texttt{U}\,\alpha\,\texttt{R}\,\beta$ becomes: a root, whose left subtree is the tree of $\alpha$ and whose right subtree is the tree of $\beta$. The empty word becomes a leaf. A tree of $n$ internal nodes comes back, and reading the tree out again by the same recursion returns the word.

Word to triangulation. Number the corners of an $(n+2)$-gon and fix the edge from corner $0$ to corner $n+1$. Some triangle in any triangulation stands on that edge; its third corner splits the polygon into two smaller ones. The decomposition of the word says where that third corner is, and the two halves are handled by $\alpha$ and $\beta$.

Triangulation to tree, directly. This one is worth doing separately because it is the prettiest. Put a node in each triangle, and join two nodes when their triangles share a diagonal. The result is a tree — it has $n$ nodes and $n-1$ edges and no cycles, because a cycle of triangles would enclose a diagonal with nothing on the far side. Rooting it at the triangle on the fixed edge makes it binary, since each triangle has at most two other sides available.

That dual tree can be read off a drawing by eye, without any recursion at all, which makes it the translation to reach for when checking whether two objects correspond.

Two more, to show the family is not four #

The pattern is not a coincidence between four specific things, and the fastest way to see that is to add objects whose definitions are unrelated to any of the above.

Non-crossing pairings. Point $1$ is joined to some point $2k$; an odd partner would leave an odd number of points on one side, which cannot be paired among themselves. The two sides are then paired independently, and each is a smaller instance. Marker plus two smaller objects, again.

Non-crossing partitions. Divide $\{1, \ldots, n\}$ into blocks so that no two blocks interleave. The block containing $1$ splits the rest into intervals, each partitioned independently. Same shape.

That last one is worth one more sentence, because the non-crossing condition is doing enormous work and it is easy to skip past. The partitions of an $n$-element set number the Bell numbers, which grow much faster than the Catalan numbers and satisfy no such tidy recursion. Forbidding interleaving is what collapses the count, and the reason it collapses it so cleanly is that the forbidden configuration is exactly the one that would stop the first block from splitting the rest into independent pieces. A condition that makes a decomposition forced is a condition that produces this sequence, which is a better statement of what the Catalan numbers count than any list of six families.

Six objects, six recursions, one shape. And each new entry brings its own natural questions: the pairings suggest asking about the number of chords crossing a fixed diameter, which is a question nobody would think to ask of a bracket string, and which then transfers to bracket strings and means something there.

The recursion carried out, once, by hand #

The translations above are stated as rules. Following one through on an actual word is worth the space, because the rules read as more mysterious than they are.

Take the word $\texttt{UURURRUR}$, which is $\texttt{(()())()}$ in brackets. The running difference goes $1, 2, 1, 2, 1, 0, 1, 0$, so the first return to zero is after the sixth letter. That gives the decomposition

$$\texttt{U}\;\underbrace{\texttt{URUR}}_{\alpha}\;\texttt{R}\;\underbrace{\texttt{UR}}_{\beta}.$$

So the tree has a root whose left subtree is the tree of $\texttt{URUR}$ and whose right subtree is the tree of $\texttt{UR}$. Recursing, $\texttt{URUR}$ decomposes as $\texttt{U}\,\varepsilon\,\texttt{R}\,\texttt{UR}$ — a root with an empty left subtree and a single node on the right — and $\texttt{UR}$ is a single node. So the tree has four internal nodes arranged with two on the right of the root and one to its left, which is exactly the shape drawn.

The polygon runs in step. A hexagon has corners numbered $0$ to $5$; fix the edge from $0$ to $5$. The decomposition says the triangle on that edge has its third corner at position $1 + |\alpha|/2 = 3$, so the triangle is $0\text{–}3\text{–}5$, and it splits the hexagon into the quadrilateral $0,1,2,3$ and the triangle $3,4,5$. The word $\alpha$ triangulates the first and $\beta$ the second.

Nothing in that paragraph required looking at the picture, and that is the test of whether a correspondence is really mechanical. A translation one can execute on paper without drawing anything is a translation a machine can execute, which is what the figures do.

Why the bijections earn their keep #

An equality of counts is worth having. A bijection is worth more, and the concrete gains are the argument for taking the trouble.

The count itself becomes a calculation. The decomposition says immediately that the objects of size $n$ number $\sum_k C_k C_{n-1-k}$, since the marker takes one unit and the two pieces split the rest in every possible way. That recurrence is the definition most treatments start from, and here it arrives as a consequence of the shape rather than as an assumption.

A statistic transfers. Any quantity defined on one object becomes a quantity on all the others. The number of returns to zero on a path becomes the number of triangles on the fixed edge, the number of nodes on the tree’s right spine, and the number of blocks touching the first point. A theorem about the distribution of one is a theorem about all of them, free.

A generation method transfers. Listing every balanced word of length $2n$ is a five-line recursion of the sort that enumerates a small structure exhaustively. Listing every triangulation directly is fiddly. Doing the first and translating is easier than doing the second, and the figures on this rung use exactly that.

A hard question can be moved to where it is easy. Counting triangulations by the number of ears — triangles with two polygon sides — looks like a geometric question. Under the translation it becomes counting binary trees by the number of leaves whose parent has two leaves, which is a routine generating-function exercise of exactly the kind the next rung sets up. Nothing was solved by the translation; the problem was carried to a room with the right tools in it.

A construction transfers, and this is the one that matters most. The associahedron of the last rung on this ladder is built from triangulations, and every statement about it can be restated about bracket strings, where the flip becomes a rewriting rule and the solid becomes a rewriting system. That reading is what connects the object to the theory of rewriting in computer science, and nobody would have looked for the connection while the vertices were polygons.

And a false claim gets caught. If two families are related by a bijection, a proposed identity about one can be tested on the other, where it may be obviously false. Counting alone gives no such test.

Reading the pentagon’s five triangulations against the five chord diagrams is the exercise the whole rung is for. The correspondence can be worked out by hand in a minute — each triangulation’s dual tree is a path or a fork, and each pairing’s nesting structure is the same path or fork — and having done it once, the general claim stops being an assertion about symbols.

Where the correspondences stop #

It is easy to come away with the impression that everything counted by the Catalan numbers is the same object, and that is not true in a way worth being precise about.

A bijection is a choice, and there are many. Between balanced words and triangulations there are $C_n!$ set-theoretic bijections, of which a handful are natural. The recursive one used here respects the decomposition; others respect a different statistic and disagree with this one about which triangulation a given word means. So “the” bijection is always shorthand for one that has been chosen, and two papers can prove the same equality and disagree about the correspondence.

Naturality is not a formal notion here, and it does the work anyway. What makes the recursive bijection the right one is that it takes the natural decomposition of each side to the natural decomposition of the other. Nobody has a definition of “natural” that settles the matter; the test in practice is whether statistics transfer usefully, and that is a judgement.

The translations do not always compose to the identity. Going from words to triangulations by one route and back by another can permute the set, and the permutation is sometimes interesting in its own right — several well-studied maps on Catalan objects were discovered exactly this way, as the discrepancy between two translations that both looked canonical. That is a productive kind of accident and it is also a warning: “the same object in different notations” is a claim about a chosen pair of translations, not about the objects.

And some objects counted by the sequence resist. The number of standard Young tableaux of shape $2 \times n$ is $C_n$, and the bijection to paths is immediate. The number of ways of stacking coins in a triangular pile is $C_n$ too, and the correspondence is genuine but was found late. Stanley’s catalogue includes entries whose bijections to the rest are known and awkward, which is the honest situation: equal counts are cheap and good bijections are not.

Two hundred entries, and what a catalogue is for #

Stanley’s Catalan Numbers lists two hundred and fourteen families in its main exercise and several hundred more in an addendum kept online. That is an unusual kind of object for a mathematician to build, and it is worth asking what it is for.

It is not for looking things up. The value is that a catalogue with explicit bijections between its entries is a machine for transporting theorems, and the entries are chosen with that in mind: they come from combinatorics, from algebra, from geometry, from computer science, and the translations between distant entries are what make a result in one field usable in another. Non-crossing partitions belong to free probability; triangulations belong to geometry; balanced words belong to formal language theory; and the sequence is the passport.

The catalogue also documents the failures, which is the part worth respecting. Several entries have no known bijection to the others that respects any natural statistic, only a proof that the counts agree. Those are open problems of a specific and unglamorous kind: not how many but why these two, and they are open because a good bijection is a genuine discovery rather than a routine construction.

What the pictures cannot show #

Four panels side by side show a correspondence and cannot show that it is one. What makes the translation a bijection is the argument that the recursion inverts, which happens in the prose. The figure draws one word’s four faces, and drawing a second word’s four faces adds a second instance rather than a proof.

The pairings and the triangulations are drawn as two separate galleries and the correspondence between them is not drawn at all. Fourteen and fourteen is what the two figures show; which pairing goes with which triangulation is a matching of twenty-eight objects, and drawing it would need lines between two pages. The prose gives the rule and the reader has to run it.

The recursion is invisible in every panel. Each object is drawn finished. The decomposition that relates them — the first return, the root, the triangle on the fixed edge — is a step in a construction, and the finished object carries no mark saying which step produced which part.

And the tree is drawn with its leaves suppressed. A binary tree with $n$ internal nodes has $n+1$ leaves, and drawing them roughly doubles the picture for no information: the leaves are determined by the internal structure. That is a defensible convention and it makes the tree in the figure look like it has fewer nodes than the polygon has triangles, when in fact those two counts are equal.

Where the ladder goes next #

The next rung stops translating and starts calculating: the decomposition above, written as an equation about a series, solves for a closed form in three lines. After that the triangulations stop being a set and become the corners of a solid, whose edges are the moves between them.

Also named here as a debt, since this rung raises it and does not settle it: the statistics on these objects — the number of returns, the number of ears, the depth of the tree — have a distribution of their own, and the joint distribution of two of them is the q-analogue theory that turns one number into a polynomial. Nothing above touches it, and it is where the subject actually spends its time.

Sideways, the dual tree is the same construction that turns a triangulated surface into a graph, the counting of labelled trees is a different sequence with a slicker proof, and the reflection argument of the previous rung is itself a bijection of exactly this kind.

Sideways: a polynomial that counts is the machinery that turns a bijection into an equation, and more things than boxes is the counting principle a bijection is measured against.

What is worth carrying away #

Two sets of the same size are worth relating; two sets with the same recursive decomposition are the same set in different handwriting.

Every object on this rung is a marker with two smaller copies of itself attached. Once that is seen, the four pictures stop being four pictures and the correspondence stops needing to be checked case by case — it is the observation that both sides answer the same recursion with the same base case, and everything else is notation.

The habit worth taking is to look for the forced decomposition. A choice-free way of breaking an object into smaller ones of the same kind is what makes a bijection mechanical instead of ingenious, and when two families have the same forced decomposition, the translation writes itself.