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?