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