|
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
\begin{equation*} C_0=1,\qquad C_n=\sum_{i=0}^{n-1} C_i C_{n-1-i}. \end{equation*}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 \begin{equation*} \sum_{n=0}^\infty C_n z^n=\frac{1-\sqrt{1-4z}}{2z}. \end{equation*} Interpretations of the $n$ th Catalan number include:
- The number of ways to arrange $n$ pairs of matching parentheses, e.g.: $$()$$ $$(())\text{ } ()()$$ $$((()))\text{ } (()())\text{ } ()(())\text{ } (())()\text{ } ()()()$$
- The number of ways a convex polygon of $n+2$ sides can be split into $n$ triangles.
- 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.
- 1
- Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.
Concrete Mathematics.
Addison-Wesley, 1998.
Zbl 0836.00001.
|
