Catalan numbers


The Catalan numbersDlmfMathworldPlanetmath, or Catalan sequence, have many interesting applications in combinatoricsDlmfMathworld.

The nth Catalan number is given by:

Cn=(2nn)n+1,

where (nr) represents the binomial coefficientDlmfDlmfMathworldPlanetmath. The first several Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862 ,…(see OEIS sequenceMathworldPlanetmath 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

C0=1,Cn=i=0n-1CiCn-1-i.

For example, C3=12+11+21=5, C4=15+12+21+51=14, etc.

The ordinary generating function for the Catalan numbers is

n=0Cnzn=1-1-4z2z.

InterpretationsMathworldPlanetmathPlanetmath of the nth Catalan number include:

  1. 1.

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

    ()
    (()) ()()
    ((())) (()()) ()(()) (())() ()()()
  2. 2.

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

  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. Concrete Mathematics. Addison-Wesley, 1998. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0836.00001Zbl 0836.00001.
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