05A10-CatalanNumbers.tex

\documentclass[12pt]{article}
\usepackage{pmmeta}
\pmcanonicalname{CatalanNumbers}
\pmcreated{2013-03-22 12:29:51}
\pmmodified{2013-03-22 12:29:51}
\pmowner{bbukh}{348}
\pmmodifier{bbukh}{348}
\pmtitle{Catalan numbers}
\pmrecord{11}{32724}
\pmprivacy{1}
\pmauthor{bbukh}{348}
\pmtype{Definition}
\pmcomment{trigger rebuild}
\pmclassification{msc}{05A10}
\pmsynonym{Catalan sequence}{CatalanNumbers}
\pmrelated{CentralBinomialCoefficient}
\pmrelated{AsymptoticsOfCentralBinomialCoefficient}

\endmetadata

% 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
\begin{document}
\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}}
%}
%%%%%
%%%%%
\end{document}