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.5.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 $C_n$; these are the Catalan numbers. For convenience, we allow a rooted binary tree to be empty, and let $C_0=1$. Then it is easy to see that $C_1=1$ and $C_2=2$, and not hard to see that $C_3=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.5.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 $$ C_n=\sum_{i=0}^{n-1} C_iC_{n-i-1}. $$ For example, since we know that $C_0=C_1=1$ and $C_2=2$, $$ C_3 = C_0C_2 + C_1C_1+C_2C_0 = 1\cdot2 + 1\cdot1 + 2\cdot1 = 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.5.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 $C_n$. Let $f=\sum_{i=0}^\infty C_ix^i$. Now consider $f^2$: the coefficient of the term $x^n$ in the expansion of $f^2$ is $\sum_{i=0}^{n} C_iC_{n-i}$, corresponding to all possible ways to multiply terms of $f$ to get an $x^n$ term: $$ C_0\cdot C_nx^n + C_1x\cdot C_{n-1}x^{n-1} + C_2x^2\cdot C_{n-2}x^{n-2} +\cdots+C_nx^n\cdot C_0. $$ Now we recognize this as precisely the sum that gives $C_{n+1}$, so $f^2 = \sum_{n=0}^\infty C_{n+1}x^n$. If we multiply this by $x$ and add 1 (which is $C_0$) we get exactly $f$ again, that is, $xf^2+1=f$ or $xf^2-f+1=0$; here 0 is the zero function, that is, $xf^2-f+1$ is 0 for all x. Using the quadratic formula, $$ f={1\pm\sqrt{1-4x}\over 2x}, $$ as long as $x\not=0$. It is not hard to see that as $x$ approaches 0, $$ {1+\sqrt{1-4x}\over 2x} $$ goes to infinity while $$ {1-\sqrt{1-4x}\over 2x} $$ goes to 1. Since we know $f(0)=C_0=1$, this is the $f$ we want.
Now by Newton's Binomial Theorem 3.1.1, we can expand $$ \sqrt{1-4x} = (1+(-4x))^{1/2} =\sum_{n=0}^\infty {1/2\choose n}(-4x)^n. $$ Then $$ {1-\sqrt{1-4x}\over 2x} = \sum_{n=1}^\infty -{1\over 2}{1/2\choose n}(-4)^nx^{n-1} = \sum_{n=0}^\infty -{1\over 2}{1/2\choose n+1}(-4)^{n+1}x^n. $$ Expanding the binomial coefficient $1/2\choose n+1$ and reorganizing the expression, we discover that $$ C_n = -{1\over 2}{1/2\choose n+1}(-4)^{n+1} = {1\over n+1}{2n\choose n}. $$
In exercise 7 in section 1.2, we saw that the number of properly matched sequences of parentheses of length $2n$ is ${2n\choose n}-{2n\choose n+1}$, and called this $C_n$. It is not difficult to see that $$ {2n\choose n}-{2n\choose n+1}={1\over n+1}{2n\choose n}, $$ so the formulas are in agreement.
Temporarily let $A_n$ be the number of properly matched sequences of parentheses of length $2n$, so from the exercise we know $A_n={2n\choose n}-{2n\choose n+1}$. It is possible to see directly that $A_0=A_1=1$ and that the numbers $A_n$ satisfy the same recurrence relation as do the $C_n$, which implies that $A_n=C_n$, 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.
Exercises 3.5
Ex 3.5.1 Show that $$ {2n\choose n}-{2n\choose n+1}={1\over n+1}{2n\choose n}. $$
Ex 3.5.2 Find a simple expression $f(n)$ so that $C_{n+1}=f(n)C_n$. Use this to compute $C_1,\ldots,C_6$ from $C_0$.
Ex 3.5.3 Show that if $A_n$ is the number of properly matched sequences of parentheses of length $2n$, then $$ A_n=\sum_{i=0}^{n-1} A_iA_{n-i-1}. $$ Do this in the same style that we used for the number of rooted binary trees: Given all the sequences of shorter length, explain how to combine them to produce the sequences of length $2n$, in such a way that the sum clearly counts the number of sequences. Hint: Prove the following lemma: If $s$ is a properly matched sequence of parentheses of length $2n$, $s$ may be written uniquely in the form $(s_1)s_2$, where $s_1$ and $s_2$ are properly matched sequences of parentheses whose lengths add to $2n-2$. For example, $(())()= ([()])[()]$ and $()(())=([\,])[(())]$, with the sequences $s_1$ and $s_2$ indicated by $[\,]$. Note that $s_1$ and $s_2$ are allowed to be empty sequences, with length 0.
Ex 3.5.4 Consider a "staircase'' as shown below. A path from $A$ to $B$ consists of a sequence of edges starting at $A$, ending at $B$, and proceeding only up or right; all paths are of length 6. One such path is indicated by arrows. The staircase shown is a "$3 \times 3$'' staircase. How many paths are there in an $n\times n$ staircase?
Ex 3.5.5 A convex polygon with $n\ge3$ sides can be divided into triangles by inserting $n-3$ non-intersecting diagonals. In how many different ways can this be done? The possibilities for $n=5$ are shown.
Ex 3.5.6 A partition of a set $S$ is a collection of non-empty subsets $A_i\subseteq S$, $1\le i\le k$ (the parts of the partition), such that $\bigcup_{i=1}^k A_i=S$ and for every $i\not=j$, $A_i\cap A_j=\emptyset$. For example, one partition of $\{1,2,3,4,5\}$ is $\{\{1,3\}$, $\{4\}$, $\{2,5\}\}$.
Suppose the integers $1,2,\ldots,n$ are arranged on a circle, in order around the circle. A partition of $\{1,2,\ldots,n\}$ is a non-crossing partition if it satisfies this additional property: If $w$ and $x$ are in some part $A_i$, and $y$ and $z$ are in a different part $A_j$, then the line joining $w$ to $x$ does not cross the line joining $y$ to $z$. The partition above, $\{1,3\}$, $\{4\}$, $\{2,5\}$, is not a non-crossing partition, as the the line 1–3 crosses the line 2–5.
Find the number of non-crossing partitions of $\{1,2,\ldots,n\}$.
Recall from section 1.4 that the Bell numbers count all of the partitions of $\{1,2,\ldots,n\}$. Hence, this exercise gives us a lower bound on the total number of partitions.
Ex 3.5.7 Consider a set of $2n$ people sitting around a table. In how many ways can we arrange for each person to shake hands with another person at the table such that no two handshakes cross?