The Meanings of Catalan Numbers

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 (non-associative)
     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 n-1 non-intersecting diagonals.
 (4) The self-convolving sequence, c[0]=1,
          c[n+1] = c[0]c[n] + c[1]c[n-1] + ... + 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 (1-sqrt(1-4x))/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 piece-wise 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 

                 (vi-vj)/(i-j) <= (vj-vk)/(j-k)

E&G show that the answer is c[n]/(n!)^2.

In addition, I've noticed that if A[2k] denotes the average (2k)th
power of distance between two randomly chosen points inside a
spherical ball, then A[2k] = c[k+1]/(k+1).

So here we have 17 different interpretations of the Catalan numbers.
Sloane's Encyclopedia of Integer Sequences says there are "dozens"
of interpretations.  Can anyone supply any others?

Return to MathPages Main Menu
Сайт управляется системой uCoz