Catalan numbersCatalanNumbers2002-02-27 02:43:582007-12-11 16:56:57Definition% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here\PMlinkescapeword{Interpretations}
\PMlinkescapeword{represents}
\PMlinkescapeword{matching}
The \emph{Catalan numbers}, or \emph{Catalan sequence}, have many interesting applications in combinatorics.
The $n$th Catalan number is given by:
$$C_n = \frac{\binom{2n}{n}}{n+1},$$
%Unnecessary...
%or, recursively,
%$$C_n = C_{n-1}\frac{(2n)(2n-1)}{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$ ,\dots (see OEIS sequence \PMlinkexternal{A000108}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000108} for more terms). The Catalan numbers are also generated by the recurrence relation
%$$C_1 = 1$$
%$$C_2 = 2$$
%$$C_3 = 5$$
%$$C_n = \sum_{i=1}^{n-1} C_iC_{n-i}$$
\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:
\begin{enumerate}
\item The number of ways to arrange $n$ pairs of matching parentheses, e.g.:
$$()$$
$$(())\text{ } ()()$$
$$((()))\text{ } (()())\text{ } ()(())\text{ } (())()\text{ } ()()()$$
\item The number of ways a convex polygon of $n+2$ sides can be split into $n$ triangles.
\item The number of rooted binary trees with exactly $n+1$ leaves.
\end{enumerate}
%The first few Catalan numbers are:
%$$C_1 = 1$$
%$$C_2 = 2$$
%$$C_3 = 5$$
%$$C_4 = 14$$
%$$C_5 = 42$$
%$$C_6 = 132$$
%$$C_7 = 429$$
%$$C_8 = 1430$$
%$$C_9 = 4862$$
%$$C_{10} = 16796$$
%$$C_{11} = 58786$$
%$$C_{12} = 208012$$
%$$C_{13} = 742900$$
%$$C_{14} = 2674440$$
%$$C_{15} = 9694845$$
%$$C_{16} = 35357670$$
%$$C_{17} = 129644790$$
%$$C_{18} = 477638700$$
%$$C_{19} = 1767263190$$
The Catalan sequence is named for Eug\`ene Charles Catalan, but it was discovered in~1751 by Euler when he was trying to solve the problem of subdividing polygons into triangles.
\begin{thebibliography}{1}
\bibitem{cite:knuth_concmath}
Ronald~L. Graham, Donald~E. Knuth, and Oren Patashnik.
\newblock {\em Concrete Mathematics}.
\newblock Addison-Wesley, 1998.
\newblock \PMlinkexternal{Zbl
0836.00001}{http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0836.00001}.
\end{thebibliography}
%@BOOK{cite:knuth_concmath,
% author = {Ronald L. Graham and Donald E. Knuth and Oren Patashnik},
% title = "Concrete Mathematics",
% year = 1998,
% publisher = {Addison-Wesley},
% note = {\PMlinkexternal{Zbl %0836.00001}{http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0836.00001}}
%}