next up previous contents
Next: Bell numbers Up: Special Sequences of Integers Previous: Second Method   Contents

Catalan numbers

A binary tree is a tree where each vertex has a left child or a right child or both or neither. The Catalan number $ C_n$ is the number of binary trees on $ n$ vertices.

Lemma 8.6.11  

$\displaystyle C_n = \sum_{0 \le k \le n-1} C_k C_{n-1-k}
$

Proof. On removing the root we get a left subtree of size $ k$ and a right subtree of size $ n-1-k$ for $ 0 \le k \le n-1$. Summing over $ k$ gives the result. $ \qedsymbol$

This looks like a convolution. In fact, it is $ [z^{n-1}]C(z)^2$ where

$\displaystyle C(z) = \sum_{n \ge 0} C_n z^n.
$

We observe that therefore $ C(z) = z C(z)^2 + 1$, where the multiplication by $ z$ shifts the coefficients up by $ 1$ and then $ +1$ adjusts for $ C_0$. This equation can be solved for $ C(z)$ to get

$\displaystyle C(z) = \frac{1 \pm \sqrt{1-4 z}}{2 z}.
$

Since $ C(0) = 1$ we must have the $ -$ sign. From the binomial theorem

$\displaystyle (1-4z)^{\frac{1}{2}} = \sum_{k \ge 0} \binom{\frac{1}{2}}{k} (-4)^k z^k.
$

Thus $ C_n = - \frac{1}{2} \binom{\frac{1}{2}}{n+1} (-4)^{n+1}$. Simplifying this we obtain $ C_n = \frac{1}{n+1} \binom{2 n}{n}$ and note the corollary that $ (n+1) \mid \binom{2 n}{n}$. Other possible definitions for $ C_n$ are:
next up previous contents
Next: Bell numbers Up: Special Sequences of Integers Previous: Second Method   Contents
root 2002-06-10