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).

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),

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

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

where ${2n\choose n}$ denotes a Binomial Coefficient and $n!$ is the usual Factorial. A Recurrence Relation for $C_n$ is obtained from

$${C_{n+1}\over C_n} = {(2n+2)!\over (n+2)[(n+1)!]^2} {(n+1)(n!)^2\over (2n)!}$$

$$= {(2n+2)(2n+1)(n+1)\over (n+2)(n+1)^2}$$

$$= {2(2n+1)(n+1)^2\over (n+1)^2(n+2)} = {2(2n+1)\over n+2},$$ (2)

so

$$C_{n+1}={2(2n+1)\over n+2} C_n.$$ (3)

Other forms include

$$C_n = {2\cdot 6\cdot 10\cdots (4n-2)\over (n+1)!}$$ (4)

$$= {2^n(2n-1)!!\over (n+1)!}$$ (5)

$$= {(2n)!\over n!(n+1)!}.$$ (6)

Segner's Recurrence Formula, given by Segner in 1758, gives the solution to Euler's Polygon Division Problem

$$E_n=E_2E_{n-1}+E_3E_{n-2}+\ldots+E_{n-1}E_2.$$ (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

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

The asymptotic form for the Catalan numbers is

$$C_k\sim {4^k\over\sqrt{\pi}\,k^{3/2}}$$ (9)

(Vardi 1991, Graham et al. 1994).

A generalization of the Catalan numbers is defined by

$${}_pd_k={1\over k}{pk\choose k-1}={1\over(p-1)k+1}{pk\choose k}$$ (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

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

and the explicit formula

$${}_pd_{qk}={p-q\over pk-q}{pk-q\choose k-1}.$$ (12)

A Recurrence Relation is given by

$${}_pd_{qk}=\sum_{i,j} {}_pd_{p-r,i}\, {}_pd_{q+r,j}$$ (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.