nLab Catalan number

Redirected from "Catalan numbers".
Contents

Contents

Idea

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

C n=1n+1(2nn)=12n+1(2n+1n)=(2n)!n!(n+1)!. 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 nC_n count a myriad of different families of objects, including:

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

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

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

  • nonisomorphic rooted planar trees with nn edges;

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

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

  • monotone functionsf:[n][n]f : [n] \to [n] such that f(0)=0f(0) = 0 and xf(x)x \le f(x) for all 0xn0 \le x \le n, or in other words, 1-cells f:[n][n]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]f\id_{[n]} \Rightarrow f;

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

  • “stay-ahead races”, i.e., functions f:[2n]{1,1}f: [2n] \to \{1, -1\} such that i=0 jf(i)>0\sum_{i=0}^j f(i) \gt 0 for 0j2n0 \leq j \leq 2n, and i=0 2nf(i)=1\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 TT with nn internal vertices (i.e., vertices that have a left child and a right child) either consists of only a root (the case n=0n=0), or has a left subtree T lT_l and a right subtree T rT_r adjacent to the root. The associated magma word m(T)Mag(x)m(T) \in Mag(x) is defined recursively according to these cases:

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

  • m(T)=m(T l)m(T r)m(T) = m(T_l) m(T_r) [expressing the magma product by simple juxtaposition] in the case n>0n \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)T(T_l, T_r) \mapsto T using the notation above, and we have the following result.

Proposition

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

The inverse is given by the unique magma map Mag(x)BinMag(x) \to Bin that takes xx 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)x y(x, y) \mapsto x^y. For each element aa of the free magma Mag(x)Mag(x), there is thus an unary operation () a(-)^a. If Mag(x) *Mag(x)^\ast denotes the free monoid on the set Mag(x)Mag(x), there is a unique monoid map

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

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

Mag(x) *ϕhom(Mag(x),Mag(x))eval aMag(x)Mag(x)^\ast \stackrel{\phi}{\to} \hom(Mag(x), Mag(x)) \stackrel{eval_a}{\to} Mag(x)

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

(a b) c=a bc.(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 da^d, either a=xa = x, or we may write a=b ca = b^c and then reduce a da^d to b cdb^{c d}.

Continuing recursively in this manner, every word aMag(x)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 xx is a reduced form;

  • If w 1,w 2,,w nw_1, w_2, \ldots, w_n are reduced forms, then so is x w 1w 2w nx^{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 TreeTree of isomorphism classes of rooted planar trees is the least fixed point, or initial algebra, of the endofunctor TT *T \mapsto T^\ast on SetSet.

To put it more visually: let us designate the term xx appearing as the base of a reduced form x w 1w nx^{w_1 \ldots w_n} as the root of a corresponding tree. (If the reduced form is just xx, then that xx is designated the root of a tree consisting of only a root.) The reduced forms w iw_i themselves have roots, and we draw an edge connecting those roots to the root xx 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 xx 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)Red(w) denote the reduced form of a magma word wMag(x)w \in Mag(x), we thus have the following result.

Proposition

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

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

(((x μ(w 1)) μ(w 2))) μ(w n)(\ldots ((x^{\mu(w_1)})^{\mu(w_2)})\ldots )^{\mu(w_n)}

and μ(x)=x\mu(x) = x.

Rooted planar trees and mountain ranges

To each rooted planar tree or reduced form x w 1w nx^{w_1 \ldots w_n} with kk edges, we associate a mountain range f:[2k]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]f: [2m] \to \mathbb{N} and g:[2n]g: [2n] \to \mathbb{N} are mountain ranges, then their product

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

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

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

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

  • If Moun(w 1),Moun(w n)Moun(w_1), \ldots Moun(w_n) have been defined for reduced forms w 1,,w nw_1, \ldots, w_n, then

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

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

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

Proposition

The mapping Tρ(T)T \mapsto \rho(T) defines a bijection from Tree nTree_n to Range nRange_n , consisting of mountain ranges of the form f:[2n]f: [2n] \to \mathbb{N}.

The inverse mapping can be described as follows. For each mountain range f:[2n]f: [2n] \to \mathbb{N}, we may subdivide the interval [2n][2n] into subintervals according to subdivision points 2n k2n_k where f(2n k)=0f(2n_k) = 0. If there is at least one internal subdivision point given by an n kn_k such that 0<n k<n0 \lt n_k \lt n, then the restriction of ff to the subintervals (before and after n kn_k) gives mountain ranges f 1,f 2f_1, f_2, which by strong induction on nn have assigned reduced trees x w 1=ρ 1(f 1),x w 2=ρ 1(f 2)x^{w_1} = \rho^{-1}(f_1), x^{w_2} = \rho^{-1}(f_2), and then we put ρ 1(f)=x w 1w 2\rho^{-1}(f) = x^{w_1 w_2}. If there are no internal subdivision points, then f1f \geq 1 on the subinterval {1,2,,2n1}\{1, 2, \ldots, 2n-1\}. Notice moreover that f(1)=1=f(2n1)f(1) = 1 = f(2n-1), using the mountain range conditions f(0)=0=f(2n)f(0) = 0 = f(2n) and f(j+1)f(j){1,1}f(j+1) - f(j) \in \{1, -1\}. This means the function g=f1g = f-1 defines a mountain range over the subinterval {1,,2n1}\{1, \ldots, 2n-1\}; by induction this has an assigned reduced tree T=ρ 1(g)T = \rho^{-1}(g), and then we define ρ 1(f)=x T\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 11, a vote for O by 1-1. Votes are counted one after another (tracked by a function f:[2n]{1,1}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., i=0 jf(i)>0\sum_{i=0}^j f(i) \gt 0 for each j[2n]j \in [2n]), and that P wins in the end by just one vote: i=0 2nf(i)=1\sum_{i=0}^{2n} f(i) = 1.

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

Proposition

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

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

Mountain ranges and monotonic lattice paths

A mountain range f:[2n]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][n]×[n]g = (g_1, g_2): [2n] \to [n] \times [n] satisfying the diagonal conditions g(0)=(0,0)g(0) = (0, 0), g(2n)=(n,n)g(2n) = (n, n), and g 1g 2g_1 \leq g_2.

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

  • g 1(j)=12(jf(j))g_1(j) = \frac1{2}(j - f(j)),

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

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

Proposition

The mapping fλ(f)f \mapsto \lambda(f) defines a bijection Range nPath nRange_n \to Path_n.

The inverse mapping takes an element (g 1,g 2)Path n(g_1, g_2) \in Path_n to the mountain range defined by jg 2(j)g 1(j)j \mapsto g_2(j) - g_1(j). The injectivity of g=(g 1,g 2)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)g_2(j+1) - g_1(j+1) and g 2(j)g 1(j)g_2(j) - g_1(j) always lies in {1,1}\{1, -1\}.

Monotonic lattice paths and pointed inflationary maps

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

Proposition

The mapping gϕ(g)g \mapsto \phi(g) defines a bijection from Path nPath_n to the set PtInf nPtInf_n consisting of maps f:[n][n]f: [n] \to [n] such that f(0)=0f(0) = 0 and jf(j)j \leq f(j) for all j[n]j \in [n].

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

(0,0)(0,f(1))(1,f(1))(1,f(2))(n,n).(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 nC_n. There are several ways of establishing the binomial expressions for C nC_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 nn internal indices, use the fact that there is just one such tree where n=0n=0 (i.e., C 0=1C_0 = 1), and that in the case n>0n \gt 0, each tree TT is determined by a pair (T l,T r)(T_l, T_r) consisting of a left tree and right tree adjacent to the root; if T lT_l has n ln_l internal vertices and T rT_r has n rn_r internal vertices, then n=n l+n r+1n = n_l + n_r + 1. Hence for n0n \geq 0 we have the recursive equation

C n+1= j+k=nC jC k.C_{n+1} = \sum_{j + k = n} C_j C_k.

Letting C(x)= n0C nx nC(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+xC(x) 2C(x) = 1 + x C(x)^2

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

C n=1n+1(2nn).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 nS_n be the set of functions f:[2n]{1,1}f: [2n] \to \{1, -1\} for which i=0 2nf(i)=1\sum_{i=0}^{2n} f(i) = 1. Each such ff takes the value 11 a total of n+1n+1 times, and the value 1-1 a total of nn times, so the cardinality of S nS_n is (2n+1n)\binom{2n+1}{n}.

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

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

The number of stay-ahead races in Race nRace_n is seen to be C n=12n+1(2n+1n)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 nS_n contains exactly one stay-ahead race, and has exactly 2n+12n+1 elements.

Proof

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

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

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

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

Pick jj so that the line L jL_j is “lowest”; all the lines have the same slope 12n+1\frac1{2n+1}, so lowest just means L j(0)L_j(0) is minimal. Minimality implies that that for every other kjk \neq j within a periodic block, the point (k,g(k))(k, g(k)) lies above the line y=L j(x)y = L_j(x). Translating this picture horizontally by jj by considering gτ jg \circ \tau^j, and then vertically by subtracting g(j)=(gτ j)(0)g(j) = (g \circ \tau^j)(0), i.e., putting h=σ(fτ j)h = \sigma(f \circ \tau^j), this means that all points (k,h(k))(k, h(k)) for k=1,,2n+1k = 1, \ldots, 2n+1 stay above the line y=L h,0(x)=12n+1(x)y = L_{h, 0}(x) = \frac1{2n+1}(x). In other words, these values h(k)h(k) are all positive and h(2n+1)=1h(2n+1) = 1: precisely the stay-ahead conditions for fτ jf \circ \tau^j. Thus the orbit of any fS nf \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 jL_j, and all the L jL_j are distinct.

Finally, the stabilizer of ff must be trivial, else we would have L g,j=L g,j+kL_{g, j} = L_{g, j+k} for kk a non-multiple of 2n+12n+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 nn 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 nn internal nodes, together with a labelling of its leaves by distinct labels in 0n0 \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 kkth iteration of the algorithm there are exactly (2k1)2(2k-1)\cdot 2 possible choices of an edge and a direction, after nn iterations we obtain the identity:

C n(n+1)!=(2n1)!!2 nC_n\cdot (n+1)! = (2n-1)!! \cdot 2^n

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

C n=(2n1)!!2 n/(n+1)!=(2n)!n!(n+1)!.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+2n+2 points (labeled by elements in [n+1][n+1] in clockwise order) into nn triangles. Thus there are 22 distinct subdivisions of a square, 55 possible subdivisions of a pentagon, and in general C nC_n possible subdivisions of an (n+2)(n+2)-gon.

(To be continued.)

References

General references:

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

Last revised on September 12, 2018 at 10:46:45. See the history of this page for a list of all contributions to it.