10 Recursions and generating functions 10.2 Two-variable examples 10.4 Product Structures

10.3 Catalan numbers

The sequence $\frac{1}{n}\binom{2n-2}{n-1}$ is known as Catalan numbers and arises in many combinatorial problems. We mention a few here.

Example 10.8.

Consider a set $S$ with a non-associative product operation. Let $u_{n}$ be the number of ways to multiply $n$ terms. Say how do we multiply $x_{1}\ldots x_{n}$ . Trivially $u_{1}=u_{2}=1$ . Say $n=3$ , then $(a(bc)),((ab)c)$ are the only choices and so $u_{3}=2$ . The outer bracket of $n$ terms is divided into two brackets of $m$ terms and $n-m$ terms i.e., $(x_{1}\ldots x_{n})=((x_{1}\ldots x_{m})(x_{m+1}\ldots x_{n}))$ . So,

u_{n}=\sum_{m=1}^{n-1}u_{m}u_{n-m}.

Let $f(x)=\sum_{n=1}u_{n}x^{n}.$ Set $u_{0}=0$ . Recursion implies that

f(x)=x+\sum_{n=2}\sum_{m=1}^{n-1}u_{m}u_{n-m}x^{n}=x+\sum_{n=2}\sum_{m=1}^{n-1% }u_{m}x^{m}u_{n-m}x^{n-m}=x+f(x)^{2}.

f(x)=\frac{1-\sqrt{1-4x}}{2},

and from fractional binomial series, we have that $u_{n}=\frac{1}{n}\binom{2n-2}{n-1}$ .

Other examples of Catalan numbers

•

Number of walks with diagonal-up and diagonal-down moves of length $2n$ that does not hit $x$ -axis.
•

A plane tree is a tree drawn on a plane and with a distinguished vertex called the root. We say it is planted if the root has degree $1$ . $u_{n}$ is the number of planted plane trees with $n$ vertices.
•

$u_{n}=$ number of planted binary plane trees with $n$ leaves.