## 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

## Recent Activity

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

new problem: Problem: Show that phi(a^n-1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia

new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz

Mar 26

new correction: Misspelled name by DavidSteinsaltz

Mar 21

new correction: underline-typo by Filipe

Mar 19

new correction: cocycle pro cocyle by pahio

Mar 7

new image: plot W(t) = P(waiting time <= t) (2nd attempt) by robert_dodier

new image: expected waiting time by robert_dodier

new image: plot W(t) = P(waiting time <= t) by robert_dodier

## Attached Articles

## Corrections

sum recurrence relation is false by AxelBoldt ✓

article by igor ✓

OEIS by Wkbj79 ✓

asymptotic formula by rspuzio ✓