Catalan numbers
The Catalan numbers, or Catalan sequence, have many interesting applications in combinatorics.
The th Catalan number is given by:
where represents the binomial coefficient. The first several Catalan numbers are , , , , , , , , , ,…(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
For example, , , etc.
The ordinary generating function for the Catalan numbers is
Interpretations of the th Catalan number include:
- 1.
-
2.
The number of ways a convex polygon of sides can be split into triangles.
-
3.
The number of rooted binary trees with exactly 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 |