Nick Olson-Harris

As an undergrad I never learned about the Catalan numbers, and while I naturally picked some things up by osmosis as a grad student, I had never quite felt at home with them the way most enumerators seem to. Earlier this summer, in preparation for the comprehensive exam in enumeration, I decided to try and remedy that. This blog post, which was mostly written during that time, is the result.

The Catalan numbers are defined by the recurrence relation \[ c_n = \sum_{k=1}^n c_{k-1}c_{n-k} \] with the initial condition \(c_0 = 1\). The sequence begins 1, 1, 2, 5, 14, 42.

The recurrence translates into the quadratic equation \[ C(x) = 1 + xC(x)^2 \] for the ordinary generating function \(C(x)\). This is one of the simplest functional equations you can write down which has a power series solution that isn’t a rational function. Using the good old quadratic formula (taking the branch with positive coefficients) we get the closed form \[ C(x) = \frac{1 - \sqrt{1 - 4x}}{2x} \] and messing with binomial identities gives the explicit formula \[ c_n = \frac{1}{n+1} \binom{2n}{n} \] for the coefficients. One can also derive this formula by a routine application of the Lagrange implicit function theorem, which is maybe easier if you ignore the difficulty of actually proving LIFT.

The Catalan numbers have dozens of different combinatorial interpretations. They’re especially nice because most of the objects counted by Catalan numbers can be put in straightforward bijections with one another, despite looking superficially different. Given this, one perspective is that these “different” interpretations are really just cryptomorphic descriptions of the same thing: “Catalan objects”. The remainder of this post will go over some of those descriptions.

Binary trees

The most straightforward interpretation of the recurrence relation is that a Catalan object of size \(n\) consists of an (unlabelled) “root vertex” together with two Catalan objects with sizes adding up to \(n - 1\). This is essentially the definition of a binary tree. Here I mean a “binary tree” in the computer scientist’s sense, in which each vertex has a distinguished “left” and “right” child, either or both of which may be empty. So \(c_n\) is the number of unlabelled binary trees with \(n\) vertices, at least for \(n > 0\). (Whether this remains true for \(n = 0\) is a matter of definition, but to me a tree has to have at least one vertex.)

A binary tree is full if every vertex has either zero or two children. Given a binary tree, we can construct a full binary tree as follows: for each vertex with fewer than two children, attach the necessary number (one or two) to make the tree full. By constructing it this way, we get that the terminal vertices (those with no children) of the resulting tree are exactly those which don’t correspond to vertices of the original tree, so this construction is invertible by deleting the terminal vertices.

In a full binary tree, the number of edges is clearly twice the number of non-terminal vertices. So if there are \(n\) of these, there are \(2n + 1\) vertices in total and hence \(n + 1\) terminal vertices. Thus using the above bijection, we get that \(c_n\) is also the number of full binary trees with \(n + 1\) terminal vertices. In this case it does still make sense for \(n = 0\). (However, the bijection as I described it doesn’t work if you allow the “empty tree” as input.)

Abstractly, full binary trees can be thought of as elements of the free magma on one generator. A magma is just a set equipped with a binary operation, with no other requirements. For full binary trees, the operation is given by taking two trees and attaching them as the left and right children of a new root. The “free” property corresponds to the fact that every full binary tree is constructed in a unique way using this operation, starting with one-vertex trees. (More generally, the free magma on several generators is given by binary trees with their leaves decorated by generators.) Magmas may not be the most interesting kind of algebraic object, but this does show that Catalan objects can be characterized by a universal property.

Dyck words

A Dyck word is a string of brackets which are correctly matched. For instance, there are two Dyck words of length 4, namely \([\,]\,[\,]\) and \([\,[\,]\,]\). The set \(\mathcal D\) of Dyck words can be characterized as the smallest set of strings such that:

• The empty string is in \(\mathcal D\).
• If \(w \in \mathcal D\) then \([\,w\,] \in \mathcal D\).
• If \(w, x \in \mathcal D\) then \(wx \in \mathcal D\).

These rules are an (informally stated) context-free grammar for \(\mathcal D\). Indeed, \(\mathcal D\) is the prototypical example of a context-free language which isn’t regular (and the Chomsky–Schützenberger theorem makes precise the notion that it is the simplest such language).

Say a Dyck word is “irreducible” if it can’t be written as the concatenation of two Dyck words. This means that at every point before the end there needs to be some opening bracket which hasn’t been closed yet. This only happens if the very first open-bracket is not closed until the end, which is the same as saying that the word is of the form \([\,w\,]\) where \(w\) is a Dyck word. So if we take \(D(x)\) to be the generating function for Dyck words according to the number of opening (or closing) brackets, the generating function for the irreducible Dyck words is just \(xD(x)\). Now every Dyck word can be uniquely written as a concatenation of irreducible ones. So we get \[ D(x) = \frac{1}{1 - xD(x)} \] which can be rearranged to the same quadratic equation satisfied by the Catalan numbers. So the number of Dyck words of length \(2n\) is \(c_n\).

This argument leads to a slightly different interpretation of the defining recurrence relation than in the binary tree case. The idea is to think of the \(c_{k-1}\) factor as counting, not the Catalan objects of size \(k - 1\), but the irreducible Catalan objects of size \(k\). Then the recurrence reflects a “first + rest” decomposition of the Dyck word into an irreducible Dyck word followed by an arbitrary Dyck word. Equivalently we decompose a (nonempty) Dyck word \(w\) of length \(2n\) as \([\,w_1\,]\,w_2\) where \(w_1\) and \(w_2\) are Dyck words of lengths adding up to \(2n - 2\). This immediately gives us a bijection with binary trees: each vertex of the tree corresponds to a pair of brackets, with the left child being the first pair of brackets inside and the right child being the first pair afterward. (Either of which might be nonexistent.)

Like full binary trees, there is a more abstract algebraic way to think about Dyck words. To begin, note that since \(\mathcal D\) is closed under concatenation and contains the empty string, it forms a monoid (indeed, a submonoid of the free monoid on two generators). The unique factorization property we used to count Dyck words essentially says that \(\mathcal D\) is in fact the free monoid generated by the irreducible Dyck words. Now suppose \(M\) is any monoid and \(b\colon M \to M\) is some operator (i.e. just a set-theoretic map, no compatibility with th monoid operation required). Then there is a unique monoid homomorphism \(\varphi\colon \mathcal D \to M\) with the property that \(\varphi([\,w\,]) = b(\varphi(w))\). This is a different universal property of Catalan objects.

Dyck paths

A Dyck path is a lattice path from \((0, 0)\) to \((n, n)\) using the steps \((1, 0)\) and \((0, 1)\) which stays above the diagonal line \(x = y\); i.e. for any point \((x, y)\) on the path we have \(x \ge y\). These are in bijection with Dyck words: an open bracket corresponds to an upward step, a closing bracket to a rightward step. At each point \((x, y)\) on the path, \(x\) is the number of opening brackets and \(y\) the number of closing brackets, so staying above the diagonal is exactly the condition that the brackets are properly matched. The irreducible Dyck paths are the ones which stay strictly above the diagonal except at the start and end.

By rotating the picture (and stretching it a bit) we can also represent Dyck paths as “mountain ranges” that go from \((0, 0)\) to \((2n, 0)\) using the steps \((1, 1)\) and \((1, -1)\) while staying above the horizontal axis. Sometimes the term “Dyck path” is reserved for these and the diagonal ones are called “Catalan paths”.

The bijection between Dyck words and Dyck paths is straightforward enough that most interesting statements about either one translate immediately to the other. One advantage of thinking of them as paths, however, is that we can use the Gessel–Viennot lemma to get a combinatorial interpretation of determinants involving Catalan numbers. Explicitly, for \(0 \le i \le n\), let \(s_i = (n - i, n - i)\) and \(t_i = (n + i, n + i)\). Then we can consider lattice paths \(s_i \to t_j\) that stay above the diagonal; these are just translated Dyck paths and the number of them is \(c_{i + j}\). Now consider the determinant \(\det[c_{i+j}]_{i,j = 0}^n\). By Gessel–Viennot, this determinant counts \(n\)-tuples \((P_0, \dots, P_n)\) of pairwise nonintersecting Dyck-type paths where each \(P_i\) starts at \(s_i\) and ends somewhere in the set \(\{t_0, \dots, t_n\}\). But it’s geometrically clear (or easy enough to prove inductively) that there is only one such configuration, namely the one where \(P_i\) is the path from \(s_i\) to \(t_i\) given by taking \(i\) up-steps followed by \(i\) right-steps. So this determinant equals \(1\). This argument doesn’t change if we dispense with the zero-length path by taking \(t_i = (n + i + 1, n + i + 1)\) instead, so we also get \(\det[c_{i+j+1}]_{i,j=0}^n = 1\).

Plane rooted trees

A plane rooted tree is a rooted tree with a total ordering on the children of each vertex. The terminology is a little bit unfortunate since embedding a tree in the plane isn’t quite enough to get this structure. Nonetheless it is quite standard.

There is a bijection between irreducible Dyck words and plane rooted trees as follows: the vertices of a tree correspond to pairs of brackets, and the children of a vertex correspond to all of the “outermost” pairs of brackets directly inside. Another way to think about this is to think of trees as a special kind of partially ordered set; then given an irreducible Dyck word we partially order the irreducible “sub-Dyck words” by containment. (By a sub-Dyck word I mean a contiguous substring which is a Dyck word.) Then this poset is a tree, and it gets a plane structure from the left-to-right ordering in the original word. In any case, this shows that the number of plane rooted trees on \(n\) vertices is \(c_{n-1}\).

There are two interesting observations here. The first is that full binary trees are a special case of plane rooted trees. (The non-full ones are not, because when a vertex has a single child you have the extra structure of distinguishing whether it’s a “left” or “right” child.) Now full binary trees on \(2n + 1\) vertices are counted by \(c_n\), whereas plane rooted trees of the same size are counted by \(c_{2n}\). This is one of several instances of the phenomenon in which Catalan objects of size \(n\) can be interpreted as a “binary” special case of Catalan objects of size \(2n\).

The other observation is that the bijection with Dyck words can be cast in terms of the universal property of Dyck words. Denote the set of plane rooted trees by \(\mathcal P\). The free monoid \(\mathcal P^*\) of lists of plane rooted trees has a bijection \(b\colon \mathcal P^* \to \mathcal P\), the “add-a-root operator”. Since \(\mathcal P\) is naturally thought of as a subset of \(\mathcal P^*\) consisting of lists of length 1, we can view this as a map \(\mathcal P^* \to \mathcal P^*\), and this gives a monoid homomorphism \(\mathcal D \to \mathcal P^*\) which turns out to be an isomorphism. Restricted to irreducible Dyck words this is the same bijection as above.

Using this, we can say that \(\mathcal P^*\) with the add-a-root operator is also universal for monoids equipped with an operator. While the universal property is a little more obvious for Dyck words, thinking in terms of trees is more useful. For instance, it allows one to give a very similar description for the universal commutative monoid equipped with an operator. Essentially it’s the same but instead of plane rooted trees you just get plain rooted trees.

This universal property of trees has a special place in my heart because I (re)discovered it for myself while first thinking about the bijection between plane trees and Dyck words. At the time I thought it was just a bit of fun, but the following term I took a course in which I learned of the essential role that the commutative version plays in the Connes–Kreimer theory of renormalization!

And more?

There are plenty of other of interpretations of Catalan numbers. When I first wrote this post I had in mind that there would be (at least) a second part covering some of these. (Indeed, the point was to teach myself things about Catalan numbers I didn’t already know, but this post mostly consisted of the ones I did already know.) However, I didn’t get to writing it before the comps and I lost some of my desire to do so after I couldn’t pretend it was studying anymore. So we’ll see…