Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



The Meanings of Catalan Numbers
Posted:
Jul 7, 1996 4:20 PM


In how many different contexts do the Catalan numbers appear? Here is a short list of some of the better known (taken from a paper by Roger Eggleton and Richard Guy in Mathematics Magazine, Oct 1988):
(1) The number of ways of parenthesizing a (nonassociative) product of n+1 factors. (2) The quotient when the middle binomial coefficient (2n!)/(n!)^2 is divided by n+1. (3) The number of ways of chopping an (irregular) (n+2)gon into n triangles by n1 nonintersecting diagonals. (4) The selfconvolving sequence, c[0]=1, c[n+1] = c[0]c[n] + c[1]c[n1] + ... + c[n]c[0] (5) The number of (plane) binary trees with n internal (trivalent) nodes. (6) The number of plane rooted trees with n edges. (7) The coefficients in the power series expansion of the generating function (1sqrt(14x))/2x. (8) The number of mountain ranges you can draw, using n upstrokes and n downstrokes. (9) The number of single mountains (cols (?) between peaks are no longer allowed to be as low as sea level) you can draw with n+1 upstrokes and n+1 downstrokes. (10) The number of paths from (0,0) to (n,n) (resp. (n+1,n+1)) increasing just one coordinate by one at each step, without crossing (resp. meeting) the diagonal x=y at any point between (a thin disguise of 8 and 9). (11) Another disguise is the number of ways n votes can come in for each of two candidates A and B in an election, with A never behind B. (12) The recurring sequence c[0]=1, (n+2)c[n+1] = (4n+2)c[n], (n>=0). (13) The number of different frieze patterns with n+1 rows (see Conway & Coxeter, Math Gaz. 57, 1973). (14) The number of ways 2n people, seated round a table, can shake hands in n pairs, without their arms crossing. (15) The number of Murasaki diagrams of n colored incense sticks which do not involve crossings.
Eggleton and Guy then added another interpretation. If you randomly select the n+1 values v0, v1,...vn from the interval [0,1], what is the probability that the piecewise linear function
(0,v0),(1,v1),...,(n,vn)
is convex? A function is convex provided any three of its values vi,vj,vk (i<j<k) satisfy the inequality
(vivj)/(ij) <= (vjvk)/(jk)
E&G show that the answer is c[n]/(n!)^2.
So here we have 16 different interpretations of the Catalan numbers. Sloane's Encyclopedia of Integer Sequences says there are "dozens" of interpretations. Can anyone supply any others?
==================================================================== MathPages at > http://www.seanet.com/~ksbrown/ ====================================================================



