Catalan number

1, 2, 5, 14, 42...

they describe the number of ways to legally place n parentheses, number of ways to triangulate a polygon with n+2 sides and plenty of other combinatorics problems...

C_n = (2n)!/n!(n+1)!

can also be computed by a Pascal-like triangle:

1
1 1
1 2 2
1 3 5 5
1 4 9 14 14

where the catalan numbers are on the diagonal and each number is the sum of the number above it and to its left. named after Eugene Charles Catalan (1814-1894).

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, October 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?

Source: http://www.mathpages.com/