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.

Title	Catalan numbers
Canonical name	CatalanNumbers
Date of creation	2013-03-22 12:29:51
Last modified on	2013-03-22 12:29:51
Owner	bbukh (348)
Last modified by	bbukh (348)
Numerical id	11
Author	bbukh (348)
Entry type	Definition
Classification	msc 05A10
Synonym	Catalan sequence
Related topic	CentralBinomialCoefficient
Related topic	AsymptoticsOfCentralBinomialCoefficient