info prev up next book cdrom email home

Catalan Number

The Catalan numbers are an Integer Sequence $\{C_n\}$ which appears in Tree enumeration problems of the type, ``In how many ways can a regular $n$-gon be divided into $n-2$ Triangles if different orientations are counted separately?'' (Euler's Polygon Division Problem). The solution is the Catalan number $C_{n-2}$ (Dörrie 1965, Honsberger 1973), as graphically illustrated below (Dickau).

\begin{figure}\begin{center}\BoxedEPSF{CatalanPolygons.epsf scaled 700}\end{center}\end{figure}

The first few Catalan numbers are 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ... (Sloane's A000108). The only Odd Catalan numbers are those of the form $c_{2^k-1}$, and the last Digit is five for $k=9$ to 15. The only Prime Catalan numbers for $n\leq 2^{15}-1$ are $C_2=2$ and $C_3=5$.


The Catalan numbers turn up in many other related types of problems. For instance, the Catalan number $C_{n-1}$ gives the number of Binary Bracketings of $n$ letters (Catalan's Problem). The Catalan numbers also give the solution to the Ballot Problem, the number of trivalent Planted Planar Trees (Dickau),

\begin{figure}\begin{center}\BoxedEPSF{CatalanTrees.epsf scaled 700}\end{center}\end{figure}

the number of states possible in an $n$-Flexagon, the number of different diagonals possible in a Frieze Pattern with $n+1$ rows, the number of ways of forming an $n$-fold exponential, the number of rooted planar binary trees with $n$ internal nodes, the number of rooted plane bushes with $n$ Edges, the number of extended Binary Trees with $n$ internal nodes, the number of mountains which can be drawn with $n$ upstrokes and $n$ downstrokes, the number of noncrossing handshakes possible across a round table between $n$ pairs of people (Conway and Guy 1996), and the number of Sequences with Nonnegative Partial Sums which can be formed from $n$ 1s and $n$ $-1$s (Bailey 1996, Brualdi 1997)!


An explicit formula for $C_n$ is given by

\begin{displaymath}
C_n \equiv {1\over n+1}{2n\choose n} = {1\over n+1}{(2n)!\over n!^2}={(2n)!\over (n+1)!n!},
\end{displaymath} (1)

where ${2n\choose n}$ denotes a Binomial Coefficient and $n!$ is the usual Factorial. A Recurrence Relation for $C_n$ is obtained from
$\displaystyle {C_{n+1}\over C_n}$ $\textstyle =$ $\displaystyle {(2n+2)!\over (n+2)[(n+1)!]^2} {(n+1)(n!)^2\over (2n)!}$  
  $\textstyle =$ $\displaystyle {(2n+2)(2n+1)(n+1)\over (n+2)(n+1)^2}$  
  $\textstyle =$ $\displaystyle {2(2n+1)(n+1)^2\over (n+1)^2(n+2)} = {2(2n+1)\over n+2},$ (2)

so
\begin{displaymath}
C_{n+1}={2(2n+1)\over n+2} C_n.
\end{displaymath} (3)

Other forms include
$\displaystyle C_n$ $\textstyle =$ $\displaystyle {2\cdot 6\cdot 10\cdots (4n-2)\over (n+1)!}$ (4)
  $\textstyle =$ $\displaystyle {2^n(2n-1)!!\over (n+1)!}$ (5)
  $\textstyle =$ $\displaystyle {(2n)!\over n!(n+1)!}.$ (6)

Segner's Recurrence Formula, given by Segner in 1758, gives the solution to Euler's Polygon Division Problem
\begin{displaymath}
E_n=E_2E_{n-1}+E_3E_{n-2}+\ldots+E_{n-1}E_2.
\end{displaymath} (7)

With $E_1=E_2=1$, the above Recurrence Relation gives the Catalan number $C_{n-2}=E_n$.


The Generating Function for the Catalan numbers is given by

\begin{displaymath}
{1-\sqrt{1-4x}\over 2x}=\sum_{n=0}^\infty C_nx^n = 1+x+2x^2+5x^3+\ldots.
\end{displaymath} (8)

The asymptotic form for the Catalan numbers is
\begin{displaymath}
C_k\sim {4^k\over\sqrt{\pi}\,k^{3/2}}
\end{displaymath} (9)

(Vardi 1991, Graham et al. 1994).


A generalization of the Catalan numbers is defined by

\begin{displaymath}
{}_pd_k={1\over k}{pk\choose k-1}={1\over(p-1)k+1}{pk\choose k}
\end{displaymath} (10)

for $k\geq 1$ (Klarner 1970, Hilton and Pederson 1991). The usual Catalan numbers $C_k={}_2d_k$ are a special case with $p=2$. ${}_pd_k$ gives the number of $p$-ary Trees with $k$ source-nodes, the number of ways of associating $k$ applications of a given $p$-ary Operator, the number of ways of dividing a convex Polygon into $k$ disjoint $(p+1)$-gons with nonintersecting Diagonals, and the number of p-Good Path from (0, $-1$) to $(k, (p-1)k-1)$ (Hilton and Pederson 1991).


A further generalization is obtained as follows. Let $p$ be an Integer $>1$, let $P_k=(k,(p-1)k-1)$ with $k\geq
0$, and $q\leq p-1$. Then define ${}_pd_{q0}=1$ and let ${}_pd_{qk}$ be the number of p-Good Path from (1, $q-1$) to $P_k$ (Hilton and Pederson 1991). Formulas for ${}_pd_{qi}$ include the generalized Jonah Formula

\begin{displaymath}
{n-q\choose k-1}=\sum_{i=1}^k {}_pd_{qi}{n-pi\choose k-i}
\end{displaymath} (11)

and the explicit formula
\begin{displaymath}
{}_pd_{qk}={p-q\over pk-q}{pk-q\choose k-1}.
\end{displaymath} (12)

A Recurrence Relation is given by
\begin{displaymath}
{}_pd_{qk}=\sum_{i,j} {}_pd_{p-r,i}\, {}_pd_{q+r,j}
\end{displaymath} (13)

where $i,j, r\geq 1$, $k\geq 1$, $q<p-r$, and $i+j=k+1$ (Hilton and Pederson 1991).

See also Ballot Problem, Binary Bracketing, Binary Tree, Catalan's Problem, Catalan's Triangle, Delannoy Number, Euler's Polygon Division Problem, Flexagon, Frieze Pattern, Motzkin Number, p-Good Path, Planted Planar Tree, Schröder Number, Super Catalan Number


References

Alter, R. ``Some Remarks and Results on Catalan Numbers.'' Proc. 2nd Louisiana Conf. Comb., Graph Th., and Comput., 109-132, 1971.

Alter, R. and Kubota, K. K. ``Prime and Prime Power Divisibility of Catalan Numbers.'' J. Combin. Th. 15, 243-256, 1973.

Bailey, D. F. ``Counting Arrangements of 1's and $-1$'s.'' Math. Mag. 69, 128-131, 1996.

Brualdi, R. A. Introductory Combinatorics, 3rd ed. New York: Elsevier, 1997.

Campbell, D. ``The Computation of Catalan Numbers.'' Math. Mag. 57, 195-208, 1984.

Chorneyko, I. Z. and Mohanty, S. G. ``On the Enumeration of Certain Sets of Planted Trees.'' J. Combin. Th. Ser. B 18, 209-221, 1975.

Chu, W. ``A New Combinatorial Interpretation for Generalized Catalan Numbers.'' Disc. Math. 65, 91-94, 1987.

Conway, J. H. and Guy, R. K. In The Book of Numbers. New York: Springer-Verlag, pp. 96-106, 1996.

Dershowitz, N. and Zaks, S. ``Enumeration of Ordered Trees.'' Disc. Math. 31, 9-28, 1980.

Dickau, R. M. ``Catalan Numbers.'' http://forum.swarthmore.edu/advanced/robertd/catalan.html.

Dörrie, H. ``Euler's Problem of Polygon Division.'' §7 in 100 Great Problems of Elementary Mathematics: Their History and Solutions. New York: Dover, pp. 21-27, 1965.

Eggleton, R. B. and Guy, R. K. ``Catalan Strikes Again! How Likely is a Function to be Convex?'' Math. Mag. 61, 211-219, 1988.

Gardner, M. ``Catalan Numbers.'' Ch. 20 in Time Travel and Other Mathematical Bewilderments. New York: W. H. Freeman, 1988.

Gardner, M. ``Catalan Numbers: An Integer Sequence that Materializes in Unexpected Places.'' Sci. Amer. 234, 120-125, June 1976.

Gould, H. W. Bell & Catalan Numbers: Research Bibliography of Two Special Number Sequences, 6th ed. Morgantown, WV: Math Monongliae, 1985.

Graham, R. L.; Knuth, D. E.; and Patashnik, O. Exercise 9.8 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.

Guy, R. K. ``Dissecting a Polygon Into Triangles.'' Bull. Malayan Math. Soc. 5, 57-60, 1958.

Hilton, P. and Pederson, J. ``Catalan Numbers, Their Generalization, and Their Uses.'' Math. Int. 13, 64-75, 1991.

Honsberger, R. Mathematical Gems I. Washington, DC: Math. Assoc. Amer., pp. 130-134, 1973.

Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 146-150, 1985.

Klarner, D. A. ``Correspondences Between Plane Trees and Binary Sequences.'' J. Comb. Th. 9, 401-411, 1970.

Rogers, D. G. ``Pascal Triangles, Catalan Numbers and Renewal Arrays.'' Disc. Math. 22, 301-310, 1978.

Sands, A. D. ``On Generalized Catalan Numbers.'' Disc. Math. 21, 218-221, 1978.

Singmaster, D. ``An Elementary Evaluation of the Catalan Numbers.'' Amer. Math. Monthly 85, 366-368, 1978.

Sloane, N. J. A. A Handbook of Integer Sequences. Boston, MA: Academic Press, pp. 18-20, 1973.

Sloane, N. J. A. Sequence A000108/M1459 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and extended entry in Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Vardi, I. Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 187-188 and 198-199, 1991.

Wells, D. G. The Penguin Dictionary of Curious and Interesting Numbers. London: Penguin, pp. 121-122, 1986.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26