3.6: Catalan Numbers
( \newcommand{\kernel}{\mathrm{null}\,}\)
A rooted binary tree is a type of graph that is particularly of interest in some areas of computer science. A typical rooted binary tree is shown in Figure 3.6.1. The root is the topmost vertex. The vertices below a vertex and connected to it by an edge are the children of the vertex. It is a binary tree because all vertices have 0, 1, or 2 children. How many different rooted binary trees are there with n vertices?

Let us denote this number by Cn; these are the Catalan numbers. For convenience, we allow a rooted binary tree to be empty, and let C0=1. Then it is easy to see that C1=1 and C2=2, and not hard to see that C3=5. Notice that any rooted binary tree on at least one vertex can be viewed as two (possibly empty) binary trees joined into a new tree by introducing a new root vertex and making the children of this root the two roots of the original trees; see Figure 3.6.2. (To make the empty tree a child of the new vertex, simply do nothing, that is, omit the corresponding child.)

Thus, to make all possible binary trees with n vertices, we start with a root vertex, and then for its two children insert rooted binary trees on k and l vertices, with k+l=n−1, for all possible choices of the smaller trees. Now we can write
Cn=n−1∑i=0CiCn−i−1.
For example, since we know that C0=C1=1 and C2=2,
C3=C0C2+C1C1+C2C0=1⋅2+1⋅1+2⋅1=5,
as mentioned above. Once we know the trees on 0, 1, and 2 vertices, we can combine them in all possible ways to list the trees on 3 vertices, as shown in Figure 3.6.3. Note that the first two trees have no left child, since the only tree on 0 vertices is empty, and likewise the last two have no right child.

Now we use a generating function to find a formula for Cn. Let f=∑∞i=0Cixi. Now consider f2: the coefficient of the term xn in the expansion of f2 is ∑ni=0CiCn−i, corresponding to all possible ways to multiply terms of f to get an xn term: C0⋅Cnxn+C1x⋅Cn−1xn−1+C2x2⋅Cn−2xn−2+⋯+Cnxn⋅C0. Now we recognize this as precisely the sum that gives Cn+1, so f2=∑∞n=0Cn+1xn. If we multiply this by x and add 1 (which is C0) we get exactly f again, that is, xf2+1=f or xf2−f+1=0; here 0 is the zero function, that is, xf2−f+1 is 0 for all x. Using the quadratic formula,
f=1±√1−4x2x,
as long as x≠0. It is not hard to see that as x approaches 0,
1+√1−4x2x
goes to infinity while
1−√1−4x2x
goes to 1. Since we know f(0)=C0=1, this is the f we want.
Now by Newton's Binomial Theorem, we can expand
√1−4x=(1+(−4x))1/2=∞∑n=0(1/2n)(−4x)n.
Then
1−√1−4x2x=∞∑n=1−12(1/2n)(−4)nxn−1=∞∑n=0−12(1/2n+1)(−4)n+1xn.
Expanding the binomial coefficient (1/2n+1) and reorganizing the expression, we discover that
Cn=−12(1/2n+1)(−4)n+1=1n+1(2nn).
In Exercise 1.E.3.7 in Section 1.E, we saw that the number of properly matched sequences of parentheses of length 2n is (2nn)−(2nn+1), and called this Cn. It is not difficult to see that
(2nn)−(2nn+1)=1n+1(2nn),
so the formulas are in agreement.
Temporarily let An be the number of properly matched sequences of parentheses of length 2n, so from the exercise we know An=(2nn)−(2nn+1). It is possible to see directly that A0=A1=1 and that the numbers An satisfy the same recurrence relation as do the Cn, which implies that An=Cn, without manipulating the generating function.
There are many counting problems whose answers turns out to be the Catalan numbers. Enumerative Combinatorics: Volume 2, by Richard Stanley, contains a large number of examples.