Catalan Number

The Catalan numbers on nonnegative integers  are a set of numbers that arise in tree enumeration problems of the type, "In how many ways can a regular -gon be divided into  triangles if different orientations are counted separately?" (Euler's polygon division problem). The solution is the Catalan number  (Pólya 1956; Dörrie 1965; Honsberger 1973; Borwein and Bailey 2003, pp. 21-22), as graphically illustrated above (Dickau).

Catalan numbers are commonly denoted  (Graham et al. 1994; Stanley 1999b, p. 219; Pemmaraju and Skiena 2003, p. 169; this work) or  (Goulden and Jackson 1983, p. 111), and less commonly  (van Lint and Wilson 1992, p. 136).

Catalan numbers are implemented in the Wolfram Language as CatalanNumber[n].

The first few Catalan numbers for , 2, ... are 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ... (OEIS A000108).

Explicit formulas for  include

			(1)
			(2)
			(3)
			(4)
			(5)
			(6)
			(7)

where  is a binomial coefficient,  is a factorial,  is a double factorial,  is the gamma function, and  is a hypergeometric function.

The Catalan numbers may be generalized to the complex plane, as illustrated above.

Sums giving  include

			(8)
			(9)
			(10)
			(11)
			(12)

where  is the floor function, and a product for  is given by

(13)

Sums involving  include the generating function

			(14)
			(15)

(OEIS A000108), exponential generating function

			(16)
			(17)

(OEIS A144186 and A144187), where  is a modified Bessel function of the first kind, as well as

			(18)
			(19)

The asymptotic form for the Catalan numbers is

(20)

(Vardi 1991, Graham et al. 1994).

The numbers of decimal digits in  for , 1, ... are 1, 5, 57, 598, 6015, 60199, 602051, 6020590, ... (OEIS A114466). The digits converge to the digits in the decimal expansion of  (OEIS A114493).

A recurrence relation for  is obtained from

(21)

so

(22)

Segner's recurrence formula, given by Segner in 1758, gives the solution to Euler's polygon division problem

(23)

With , the above recurrence relation gives the Catalan number .

From the definition of the Catalan number, every prime divisor of  is less than . On the other hand,  for . Therefore,  is the largest Catalan prime, making  and  the only Catalan primes. (Of course, much more than this can be said about the factorization of .)

The only odd Catalan numbers are those of the form . The first few are therefore 1, 5, 429, 9694845, 14544636039226909, ... (OEIS A038003).

The odd Catalan numbers  end in 5 unless the base-5 expansion of  uses only the digits 0, 1, 2, so it would be extremely rare for a long sequence of essentially random base-5 digits to contain only in 0, 1, and 2. In fact, the last digits of the odd Catalan numbers are 1, 5, 9, 5, 9, 5, 9, 7, 5, 5, 5, 5, 5, ... (OEIS A094389), so 5 is the last digit for all  up to at least  with the exception of 1, 3, 5, 7, and 8.

The Catalan numbers turn up in many other related types of problems. The Catalan number  also gives the number of binary bracketings of  letters (Catalan's problem), the solution to the ballot problem, the number of trivalent planted planar trees (Dickau; illustrated above), the number of states possible in an -flexagon, the number of different diagonals possible in a frieze pattern with  rows, the number of Dyck paths with  strokes, the number of ways of forming an -fold exponential, the number of rooted planar binary trees with  internal nodes, the number of rooted plane bushes with  graph edges, the number of extended binary trees with  internal nodes, and the number of mountains which can be drawn with  upstrokes and  downstrokes, the number of noncrossing handshakes possible across a round table between  pairs of people (Conway and Guy 1996)!

A generalization of the Catalan numbers is defined by

			(24)
			(25)

for  (Klarner 1970, Hilton and Pedersen 1991). The usual Catalan numbers  are a special case with .  gives the number of -ary trees with  source-nodes, the number of ways of associating  applications of a given -ary operator, the number of ways of dividing a convex polygon into  disjoint -gons with nonintersecting polygon diagonals, and the number of p-good paths from (0, ) to  (Hilton and Pedersen 1991).

A further generalization is obtained as follows. Let  be an integer , let  with , and . Then define  and let  be the number of p-good paths from (1, ) to  (Hilton and Pedersen 1991). Formulas for  include the generalized Jonah formula

(26)

and the explicit formula

(27)

A recurrence relation is given by

(28)

where , , , and  (Hilton and Pedersen 1991).

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. A 15, 243-256, 1973.

Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, 2003.

Brualdi, R. A. Introductory Combinatorics, 4th 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." https://mathforum.org/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, pp. 253-266, 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.

Goulden, I. P. and Jackson, D. M. Combinatorial Enumeration. New York: Wiley, 1983.

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 Pedersen, 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.

Mays, M. E. and Wojciechowski, J. "A Determinant Property of Catalan Numbers." Disc. Math. 211, 125-133, 2000.

Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, 2003.

Pólya, G. "On Picture-Writing." Amer. Math. Monthly 63, 689-697, 1956.

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. Sequences A000108/M1459, A038003, A094389, A114466, A114493, A144186, and A144187 in "The On-Line Encyclopedia of Integer Sequences."

Sloane, N. J. A. and Plouffe, S. Figure M1459 in The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Stanley, R. P. Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, 1999a.

Stanley, R. P. Enumerative Combinatorics, Vol. 2. Cambridge, England: Cambridge University Press, pp. 219-229, 1999b.

Stanley, R. P. "Catalan Addendum." 19 Nov. 2003. https://www-math.mit.edu/~rstan/ec/catadd.ps.gz.

van Lint, J. H. and Wilson, R. M. A Course in Combinatorics. New York: Cambridge University Press, 1992.

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.