Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: The Meanings of Catalan Numbers
Replies: 3   Last Post: Jul 10, 1996 11:06 PM

 Messages: [ Previous | Next ]
 Kevin Brown Posts: 31 Registered: 12/12/04
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 (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.

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/
====================================================================

Date Subject Author
7/7/96 Kevin Brown
7/10/96 Bill Dubuque
7/10/96 Keith F. Lynch
7/10/96 Kevin Brown