## You are here

HomeCatalan numbers

## Primary tabs

# 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 A000108 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. 2. 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. Concrete Mathematics. Addison-Wesley, 1998. Zbl 0836.00001.

## Mathematics Subject Classification

05A10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Attached Articles

## Corrections

sum recurrence relation is false by AxelBoldt ✓

article by igor ✓

OEIS by Wkbj79 ✓

asymptotic formula by rspuzio ✓