# 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{\binom{2n}{n}}{n+1},$

where $\binom{n}{r}$ 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,\qquad 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}^{\infty}C_{n}z^{n}=\frac{1-\sqrt{1-4z}}{2z}.$

Interpretations of the $n$th Catalan number include:

1. 1.

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

 $()$
 $(())\text{ }()()$
 $((()))\text{ }(()())\text{ }()(())\text{ }(())()\text{ }()()()$
2. 2.

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

3. 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.

## References

• 1 Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Addison-Wesley, 1998. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0836.00001Zbl 0836.00001.
Title Catalan numbers CatalanNumbers 2013-03-22 12:29:51 2013-03-22 12:29:51 bbukh (348) bbukh (348) 11 bbukh (348) Definition msc 05A10 Catalan sequence CentralBinomialCoefficient AsymptoticsOfCentralBinomialCoefficient