nLab Catalan number

Idea

Catalan numbers are a specific sequence of nonnegative integers, here denoted $C_n$, with a ubiquitous combinatorial interpretations. In terms of binomial coefficients they are given by

$$C_n = \frac{1}{n+1}\binom{2 n}{n} = \frac1{2n+1}\binom{2n+1}{n} = \frac{(2n)!}{n!(n+1)!} \,.$$

The Catalan numbers $C_n$ count a myriad of different families of objects, including:

• nonisomorphic (rooted planar) binary trees with $n$ internal vertices;

• ways of unambiguously defining the product of elements $x_0,\dots,x_n$ within an arbitrary (not necessarily associative) magma, or equivalently, ways of fully parenthesizing a string of $n+1$ letters;

• elements of the free magma $Mag(x)$ generated by a singleton $x$ (called words) that have $n+1$ instances of the letter $x$;

• nonisomorphic rooted planar trees with $n$ edges;

• strings consisting of $n$ well-balanced pairs of parentheses (also known as “Dyck words”), or equivalently, surjective monotone functions $w : (n) + (n) \to (2n)$ such that $w(\iota_1 j) \le w(\iota_2 j)$ for all $1 \le j \le n$ (where we write $(k)$ for the finite ordinal $(k) = \{1,\dots,k\}$);

• monotonic lattice paths in an $n\times n$ grid which do not cross below the diagonal, or equivalently, injective monotone functions $p : [2n] \to [n] \times [n]$ such that $\pi_1 p(i) \le \pi_2 p(i)$ for all $0 \le i \le 2n$ (where we write $[k]$ for the non-empty finite ordinal $[k] = \{0,\dots,k\}$);

• monotone functions$f : [n] \to [n]$ such that $f(0) = 0$ and $x \le f(x)$ for all $0 \le x \le n$, or in other words, 1-cells $f : [n] \to [n]$ in $\Delta_\bot$ (the sub-2-category of the simplex 2-category $\Delta$ spanned by the first-element-preserving functions) which are pointed in the sense of being equipped with a 2-cell $\id_{[n]} \Rightarrow f$;

• “mountain ranges”, i.e., functions $f: [2n] \to \mathbb{N}$ such that $f(0) = 0 = f(2n)$ and $f(j+1) - f(j) \in \{1, -1\}$ for $0 \leq j \lt 2n$ (so called because graphs of such depict mountain ranges);

• “stay-ahead races”, i.e., functions $f: [2n] \to \{1, -1\}$ such that $\sum_{i=0}^j f(i) \gt 0$ for $0 \leq j \leq 2n$, and $\sum_{i=0}^{2n} f(i) = 1$ (see below for explanation of terminology);

and many, many more besides (see the Stanley references and OEIS A000108).

Some structural bijections

In this section we describe some “canonical” isomorphisms between various structures named above. Most of these can be seen as isomorphisms between various species of structures, which collectively might be called “the Catalan species”.

Rooted planar binary trees and magma words

Each (finite) rooted planar binary tree $T$ with $n$ internal vertices (i.e., vertices that have a left child and a right child) either consists of only a root (the case $n=0$), or has a left subtree $T_l$ and a right subtree $T_r$ adjacent to the root. The associated magma word $m(T) \in Mag(x)$ is defined recursively according to these cases:

• $m(T) = x$ in the case $n=0$;

• $m(T) = m(T_l) m(T_r)$ [expressing the magma product by simple juxtaposition] in the case $n \gt 0$.

Put slightly differently, the collection of isomorphism classes of rooted planar binary trees carries a magma structure, defined by $(T_l, T_r) \mapsto T$ using the notation above, and we have the following result.

Proposition

The mapping $T \mapsto m(T)$ defines a bijection from the set $Bin_n$ of isomorphism clases of rooted planar binary trees with $n$ internal vertices to the set $Mag(x)_n$ of magma words with $n+1$ instances of $x$.

The inverse is given by the unique magma map $Mag(x) \to Bin$ that takes $x$ to the isomorphism class of trees consisting of just a root.

Magma words and rooted planar trees

It is often suggestive to use exponential notation to denote the magma operation: $(x, y) \mapsto x^y$. For each element $a$ of the free magma $Mag(x)$, there is thus an unary operation $(-)^a$. If $Mag(x)^\ast$ denotes the free monoid on the set $Mag(x)$, there is a unique monoid map

$$\phi: Mag(x)^\ast \to \hom(Mag(x), Mag(x))$$

that carries $a \in Mag(x)$ to the unary operation $(-)^a$. For $a \in Mag(x)$, it is reasonable to denote the composite

$$Mag(x)^\ast \stackrel{\phi}{\to} \hom(Mag(x), Mag(x)) \stackrel{eval_a}{\to} Mag(x)$$

by $w \mapsto a^w$. Denote the monoid product in $Mag(x)^\ast$ by simple juxtaposition. Under these conventions, we have for $a, b, c \in Mag(x)$ the exponential equation

$$(a^b)^c = a^{b c}.$$

If we regard the right-hand side of the exponential equation as a reduction of the left-hand side, then for any formal magma expression $a^d$, either $a = x$, or we may write $a = b^c$ and then reduce $a^d$ to $b^{c d}$.

Continuing recursively in this manner, every word $a \in Mag(x)$ can be eventually expressed as a “reduced form” (where no further reductions are possible), where we formally define a reduced form as follows:

• The expression $x$ is a reduced form;

• If $w_1, w_2, \ldots, w_n$ are reduced forms, then so is $x^{w_1 w_2 \ldots w_n}$.

The reader who is following where this is going will have observed that this recursive description of reduced forms matches precisely the recursive description of rooted planar trees, formalized by saying the set $Tree$ of isomorphism classes of rooted planar trees is the least fixed point, or initial algebra, of the endofunctor $T \mapsto T^\ast$ on $Set$.

To put it more visually: let us designate the term $x$ appearing as the base of a reduced form $x^{w_1 \ldots w_n}$ as the root of a corresponding tree. (If the reduced form is just $x$, then that $x$ is designated the root of a tree consisting of only a root.) The reduced forms $w_i$ themselves have roots, and we draw an edge connecting those roots to the root $x$ appearing in the base. Continuing this pattern, we climb recursively up the stacked exponentials, eventually obtaining a structure of rooted planar tree from a reduced form, whose vertices are just the instances of $x$ appearing in the reduced form.

In fact, there is no harm in identifying rooted planar trees with reduced forms, and we will repeatedly use this identification below.

Letting $Red(w)$ denote the reduced form of a magma word $w \in Mag(x)$, we thus have the following result.

Proposition

The mapping $w \mapsto Red(w)$ defines a bijection from $Mag(x)_n$ to $Tree_n$, i.e., from magma words having $n+1$ instances of $x$ to isomorphism classes of rooted planar trees with $n$ edges.

The inverse takes a reduced form $x^w = x^{w_1 w_2 \ldots w_n}$ to the magma word $\mu(x^w)$ defined recursively by

$$(\ldots ((x^{\mu(w_1)})^{\mu(w_2)})\ldots )^{\mu(w_n)}$$

and $\mu(x) = x$.

Rooted planar trees and mountain ranges

To each rooted planar tree or reduced form $x^{w_1 \ldots w_n}$ with $k$ edges, we associate a mountain range $f: [2k] \to \mathbb{N}$ as follows.

In the first place, there is a monoid structure on the set of mountain ranges, essentially given by juxtaposition. Formally, if $f: [2m] \to \mathbb{N}$ and $g: [2n] \to \mathbb{N}$ are mountain ranges, then their product

$$f \ast g: [2(m+n)] \to \mathbb{N}$$

is defined by $j \mapsto f(j)$ if $0 \leq j \leq 2m$, and $j \mapsto g(j-2m)$ if $2m \leq 2(m+n)$, noting that $(f \ast g)(2m) = 0$ in either case by definition of mountain range ($f(2m) = 0 = g(0)$).

We define $Moun: Tree^\ast \to Range$, from the free monoid on trees to mountain ranges, by the following recursive rules:

• $Moun(x): \{0\} \to \mathbb{N}$ takes the value $0$.

• If $Moun(w_1), \ldots Moun(w_n)$ have been defined for reduced forms $w_1, \ldots, w_n$, then

  • $Moun(w_1 \ldots w_n) = Moun(w_1) \ast \ldots \ast Moun(w_n)$, as a function $[2k] \to \mathbb{N}$ for some $k$, in which case

  • $Moun(x^{w_1 \ldots w_n}): [2(k+1)] \to \mathbb{N}$ takes $j$ for $1 \leq j \leq 2k+1$ to $1 + Moun(w_1 \ldots w_n)(j-1)$.

Then define $\rho: Tree \to Range$ to be the mapping that takes a tree $T = x^w$ to $Moun(w)$.

Proposition

The mapping $T \mapsto \rho(T)$ defines a bijection from $Tree_n$ to $Range_n$ , consisting of mountain ranges of the form $f: [2n] \to \mathbb{N}$.

The inverse mapping can be described as follows. For each mountain range $f: [2n] \to \mathbb{N}$, we may subdivide the interval $[2n]$ into subintervals according to subdivision points $2n_k$ where $f(2n_k) = 0$. If there is at least one internal subdivision point given by an $n_k$ such that $0 \lt n_k \lt n$, then the restriction of $f$ to the subintervals (before and after $n_k$) gives mountain ranges $f_1, f_2$, which by strong induction on $n$ have assigned reduced trees $x^{w_1} = \rho^{-1}(f_1), x^{w_2} = \rho^{-1}(f_2)$, and then we put $\rho^{-1}(f) = x^{w_1 w_2}$. If there are no internal subdivision points, then $f \geq 1$ on the subinterval $\{1, 2, \ldots, 2n-1\}$. Notice moreover that $f(1) = 1 = f(2n-1)$, using the mountain range conditions $f(0) = 0 = f(2n)$ and $f(j+1) - f(j) \in \{1, -1\}$. This means the function $g = f-1$ defines a mountain range over the subinterval $\{1, \ldots, 2n-1\}$; by induction this has an assigned reduced tree $T = \rho^{-1}(g)$, and then we define $\rho^{-1}(f) = x^T$. This completes the description of the inverse mapping.

Mountain ranges and stay-ahead races

The terminology “stay-ahead” race is suggested by the following scenario: a poll race is held between a proponent P and an opponent O. A vote for P is indicated by the value $1$, a vote for O by $-1$. Votes are counted one after another (tracked by a function $f: [2n] \to \{1, -1\}$) and partial tallies are recorded. The stay-ahead conditions are that each partial tally has P ahead of O (i.e., $\sum_{i=0}^j f(i) \gt 0$ for each $j \in [2n]$), and that P wins in the end by just one vote: $\sum_{i=0}^{2n} f(i) = 1$.

To each stay-ahead race $f: [2n] \to \{1, -1\}$ we associate a mountain range $g = \Sigma(f): [2n] \to \mathbb{N}$ by defining $g(j) = -1 + \sum_{i=0}^j f(i)$.

Proposition

The mapping $f \mapsto \Sigma(f)$ defines a bijection $Race_n \to Range_n$ from stay-ahead races $[2n] \to \{1, -1\}$ to mountain ranges $[2n] \to \mathbb{N}$.

The inverse mapping takes a mountain range $g: [2n] \to \mathbb{N}$ to the stay-ahead race defined by the function $j \mapsto g(j) - g(j-1)$ for $0 \leq j \leq 2n$, making use of a nonce convention $g(-1) \coloneqq -1$.

Mountain ranges and monotonic lattice paths

A mountain range $f: [2n] \to \mathbb{N}$ (or more precisely, the graph of a mountain range) can easily be converted, by a linear transformation, to an injective poset mapping $g = (g_1, g_2): [2n] \to [n] \times [n]$ satisfying the diagonal conditions $g(0) = (0, 0)$, $g(2n) = (n, n)$, and $g_1 \leq g_2$.

To wit: we remark that for a mountain range $f$, each value $f(j)$ has the same parity as $j$, and $f(j) \leq j$ for all $j \in [2n]$. (Both are simple consequences of the mountain range conditions.) Define

• $g_1(j) = \frac1{2}(j - f(j))$,

• $g_2(j) = \frac1{2}(j + f(j))$.

Denote the poset map $g = (g_1, g_2)$ thus defined by $\lambda(f)$. Let $Path_n$ denote the set of monotonic lattice paths satisfying the diagonal conditions.

Proposition

The mapping $f \mapsto \lambda(f)$ defines a bijection $Range_n \to Path_n$.

The inverse mapping takes an element $(g_1, g_2) \in Path_n$ to the mountain range defined by $j \mapsto g_2(j) - g_1(j)$. The injectivity of $g = (g_1, g_2)$ forces each step of the path to go just one step (or block) north or just one block east, corresponding to the fact that the difference between $g_2(j+1) - g_1(j+1)$ and $g_2(j) - g_1(j)$ always lies in $\{1, -1\}$.

Monotonic lattice paths and pointed inflationary maps

Each injective map $g = (g_1, g_2): [2n] \to [n] \times [n]$ determines and is determined by a map $f = \phi(g): [n] \to [n]$ defined as follows: if $0 \leq j \leq n$, then $f(j) = \min \{g_2(k): g_1(k) = j\}$. (The injectivity of $g$ implies that the lattice path crosses each line $x = j$.)

Proposition

The mapping $g \mapsto \phi(g)$ defines a bijection from $Path_n$ to the set $PtInf_n$ consisting of maps $f: [n] \to [n]$ such that $f(0) = 0$ and $j \leq f(j)$ for all $j \in [n]$.

Indeed, the pointed inflationary conditions on $f$ are direct consequences of the diagonal conditions on $g$. The inverse mapping takes such a function $f$ to the lattice path that proceeds north and east, interpolating through the points

$$(0, 0)\;\; (0, f(1))\;\; (1, f(1))\;\; (1, f(2))\;\; \ldots\;\; (n, n).$$

Structural enumeration

The bijections of the last section indicate that all of the structures named above are counted by the same quantity $C_n$. There are several ways of establishing the binomial expressions for $C_n$ mentioned above.

Method 1

A tried-and-true approach (explained in Baez-Dolan) is by means of generating functions. To enumerate rooted planar binary trees with $n$ internal indices, use the fact that there is just one such tree where $n=0$ (i.e., $C_0 = 1$), and that in the case $n \gt 0$, each tree $T$ is determined by a pair $(T_l, T_r)$ consisting of a left tree and right tree adjacent to the root; if $T_l$ has $n_l$ internal vertices and $T_r$ has $n_r$ internal vertices, then $n = n_l + n_r + 1$. Hence for $n \geq 0$ we have the recursive equation

$$C_{n+1} = \sum_{j + k = n} C_j C_k.$$

Letting $C(x) = \sum_{n \geq 0} C_n x^n$ be the generating function (really a formal power series), the recursion leads to

$$C(x) = 1 + x C(x)^2$$

which we solve as $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$ in the formal power series sense. Starting with the binomial theorem to expand $(1 - 4x)^{1/2}$ as a power series, a series of (somewhat tedious and unilluminating) manipulations eventually leads to the calculation

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

Method 2

A more structural derivation can be obtained by counting stay-ahead races, in the following manner. Let $S_n$ be the set of functions $f: [2n] \to \{1, -1\}$ for which $\sum_{i=0}^{2n} f(i) = 1$. Each such $f$ takes the value $1$ a total of $n+1$ times, and the value $-1$ a total of $n$ times, so the cardinality of $S_n$ is $\binom{2n+1}{n}$.

We let the cyclic group $\mathbb{Z}/(2n+1)$ act on $S_n$, by precomposing functions $f: [2n] \to \{1, -1\}$ with powers of the cyclic permutation

$$\tau = (0\; 1\; \ldots\; 2n): [2n] \to [2n].$$

The number of stay-ahead races in $Race_n$ is seen to be $C_n = \frac1{2n+1}\binom{2n+1}{n}$, as soon as we establish the following result.

Proposition

Each orbit of the cyclic group action on $S_n$ contains exactly one stay-ahead race, and has exactly $2n+1$ elements.

Proof

Given $f \in S_n$, form the unique extension $\tilde{f}: \mathbb{Z} \to \{1, -1\}$ that is periodic with period $2n+1$. Let $g = \sigma(f)$ be the unique function such that $g(0) = 0$ and

$$g(j+1) - g(j) = \tilde{f}(j)$$

for all $j \in \mathbb{Z}$. For example, $g(j) = \sum_{0 \leq i \lt j} \tilde{f}(i)$ for all $j \geq 0$.

Observe that $g(j+2n+1) = g(j)+1$ for all $j$, so that the line $L_{g, j}$ with slope $\frac1{2n+1}$ that passes through $(j, g(j))$ also passes through $(j+2n+1, g(j+2n+1))$, but passes through no other $(k, g(k))$ for $j \lt k \lt j+2n+1$ since $g(k)$ is integral but $L_{g, j}(k)$ is not, being strictly between $g(j)$ and $g(j)+1$. This implies that the lines $L_{g, j}$ for $j$ ranging over a period block $\{j, j+1, \ldots, j+2n\}$ are all distinct, i.e., the cyclic group action on these $L_{g, j}$ according to the formula $\tau L_{g, j} = L_{g, j+1}$ is faithful.

Pick $j$ so that the line $L_j$ is “lowest”; all the lines have the same slope $\frac1{2n+1}$, so lowest just means $L_j(0)$ is minimal. Minimality implies that that for every other $k \neq j$ within a periodic block, the point $(k, g(k))$ lies above the line $y = L_j(x)$. Translating this picture horizontally by $j$ by considering $g \circ \tau^j$, and then vertically by subtracting $g(j) = (g \circ \tau^j)(0)$, i.e., putting $h = \sigma(f \circ \tau^j)$, this means that all points $(k, h(k))$ for $k = 1, \ldots, 2n+1$ stay above the line $y = L_{h, 0}(x) = \frac1{2n+1}(x)$. In other words, these values $h(k)$ are all positive and $h(2n+1) = 1$: precisely the stay-ahead conditions for $f \circ \tau^j$. Thus the orbit of any $f \in S_n$ contains a stay-ahead race. Moreover, this is the only stay-ahead race in the orbit since the stay-ahead positivity condition is equivalent to the minimality condition on $L_j$, and all the $L_j$ are distinct.

Finally, the stabilizer of $f$ must be trivial, else we would have $L_{g, j} = L_{g, j+k}$ for $k$ a non-multiple of $2n+1$: as we saw before, this can’t happen.

Method 3

Yet another proof of the formula is based on Jean-Luc Rémy’s algorithm for generating binary trees uniformly at random (see Knuth TACP 4A, Section 7.2.1.6), which can be described as $n$ iterations of the following simple rule:

• Pick any edge of the tree.

• Create a new internal node by splitting the edge in two and budding off a freshly-labelled leaf, either to the left or to the right of the new internal node.

Starting from the trivial binary tree (containing no internal nodes and a single leaf labelled “0”), this algorithm will generate a binary tree with $n$ internal nodes, together with a labelling of its leaves by distinct labels in $0 \dots n$. Moreover, it does so exhaustively and without repetition, that is, every binary tree equipped with a permutation of its leaves will be generated exactly once. (An easy way to see this is by thinking of applying the algorithm “in reverse” to an arbitrary leaf-labelled binary tree, repeatedly pruning off the leaf with the largest label while recording whether it is a left leaf or a right leaf, until only the root edge remains.)

Since at the $k$th iteration of the algorithm there are exactly $(2k-1)\cdot 2$ possible choices of an edge and a direction, after $n$ iterations we obtain the identity:

$$C_n\cdot (n+1)! = (2n-1)!! \cdot 2^n$$

(where $(2n-1)!! = (2n-1)(2n-3)\cdots 1 = \frac1{2^n} \frac{(2n)!}{n!}$ is the double factorial), which implies that

$$C_n = (2n-1)!! \cdot 2^n/(n+1)! = \frac{(2n)!}{n!(n+1)!} \,.$$

Relation to cyclic objects

As pointed out for example in Kapranov-Voevodsky, another description of a Catalan species is by way of subdivisions of a regular polygon with $n+2$ points (labeled by elements in $[n+1]$ in clockwise order) into $n$ triangles. Thus there are $2$ distinct subdivisions of a square, $5$ possible subdivisions of a pentagon, and in general $C_n$ possible subdivisions of an $(n+2)$-gon.

(To be continued.)

Related concepts

• associahedron

References

General references:

• Wikipedia, Catalan number
• Richard P. Stanley, Catalan addendum, (to problems in Chapter 6 of Enumerative Combinatorics, vol. 2) 96 pp. pdf
• Richard P. Stanley, Catalan numbers, 215 pp., Cambridge University Press 2015

Other references:

• Donald E. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011. See Section 7.2.1.6 on “Generating all trees” (also available as a pre-fascicle).

• Sequence A000108 in the OEIS

For an interpretation in terms of species (or structure types) see

• John Baez, James Dolan, From Finite Sets to Feynman Diagrams, (arXiv:math/0004133, p. 19).