Catalan numbers

The Catalan numbers, or Catalan sequence, have many interesting applications in combinatorics.

The $n$th Catalan number is given by:

$$C_n=\frac{\left(\genfrac{}{}{0pt}{}{2n}{n}\right)}{n+1},$$

where $\left(\genfrac{}{}{0pt}{}{n}{r}\right)$ represents the binomial coefficient. The first several Catalan numbers are $1$, $1$, $2$, $5$, $14$, $42$, $132$, $429$, $1430$, $4862$ ,…(see OEIS sequence http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000108A000108 for more terms). The Catalan numbers are also generated by the recurrence relation

$$C_0=1,C_n=\sum _{i=0}^{n-1}{C}_i{C}_{n-1-i}.$$

For example, $C_3=1\cdot 2+1\cdot 1+2\cdot 1=5$, $C_4=1\cdot 5+1\cdot 2+2\cdot 1+5\cdot 1=14$, etc.

The ordinary generating function for the Catalan numbers is

$$\sum _{n=0}^{\mathrm{\infty }}{C}_n{z}^n=\frac{1-\sqrt{1-4z}}{2z}.$$

Interpretations of the $n$th Catalan number include:

1. The number of ways to arrange $n$ pairs of matching parentheses, e.g.:

   $$()$$

   $$(())()()$$

   $$((()))(()())()(())(())()()()()$$

2. The number of ways a convex polygon of $n+2$ sides can be split into $n$ triangles.

3. The number of rooted binary trees with exactly $n+1$ leaves.

The Catalan sequence is named for Eugène Charles Catalan, but it was discovered in 1751 by Euler when he was trying to solve the problem of subdividing polygons into triangles.