PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (37)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Low Entry average rating: Very high
Catalan numbers (Definition)

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

The $ n$th Catalan number is given by:

$\displaystyle 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

$\displaystyle 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

$\displaystyle \sum_{n=0}^\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.:
    $\displaystyle ()$
    $\displaystyle (())$ $\displaystyle ()()$
    $\displaystyle ((()))$ $\displaystyle (()())$ $\displaystyle ()(())$ $\displaystyle (())()$ $\displaystyle ()()()$
  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.

Bibliography

1
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.
Concrete Mathematics.
Addison-Wesley, 1998.
Zbl 0836.00001.



"Catalan numbers" is owned by bbukh. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

See Also: central binomial coefficient, asymptotics of central binomial coefficient

Other names:  Catalan sequence

Attachments:
generating function for the Catalan numbers (Derivation) by rm50
things counted by the Catalan numbers (Example) by rm50
Log in to rate this entry.
(view current ratings)

Cross-references: Euler, binary trees, triangles, sides, polygon, convex, interpretations, generating function for the Catalan numbers, recurrence relation, generated by, terms, sequence, OEIS, binomial coefficient
There are 10 references to this entry.

This is version 8 of Catalan numbers, born on 2002-02-27, modified 2007-12-11.
Object id is 2724, canonical name is CatalanNumbers.
Accessed 14454 times total.

Classification:
AMS MSC: 05A10 (Combinatorics :: Enumerative combinatorics :: Factorials, binomial coefficients, combinatorial functions)
Pending Errata and Addenda
None.
[ View all 5 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)