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{\left(\genfrac{}{}{0pt}{}{2n}{n}\right)}{n+1},$$ 
where $\left(\genfrac{}{}{0pt}{}{n}{r}\right)$ represents the binomial coefficient^{}. The first several Catalan numbers are $1$, $1$, $2$, $5$, $14$, $42$, $132$, $429$, $1430$, $4862$ ,…(see OEIS sequence^{} http://www.research.att.com/cgibin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000108A000108 for more terms). The Catalan numbers are also generated by the recurrence relation
$${C}_{0}=1,{C}_{n}=\sum _{i=0}^{n1}{C}_{i}{C}_{n1i}.$$ 
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}^{\mathrm{\infty}}{C}_{n}{z}^{n}=\frac{1\sqrt{14z}}{2z}.$$ 
Interpretations^{} of the $n$th Catalan number include:

1.
The number of ways to arrange $n$ pairs of matching parentheses, e.g.:
$$()$$ $$(())\text{}()()$$ $$((()))\text{}(()())\text{}()(())\text{}(())()\text{}()()()$$ 
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.
References
 1 Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics. AddisonWesley, 1998. http://www.emis.de/cgibin/zmen/ZMATH/en/quick.html?type=html&an=0836.00001Zbl 0836.00001.
Title  Catalan numbers 

Canonical name  CatalanNumbers 
Date of creation  20130322 12:29:51 
Last modified on  20130322 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 