Catalan Numbers

Here is a simple problem to try out. Draw a 4x4 array of dots. Now construct all the paths possible from the bottom left to the upper right corners by moving only upward or to the right, (think of rook moves on a chess board). Go ahead, there are not that many (only 6 choose 3). Now draw the diagonal from the start corner to the stop corner. How many of the paths never cross the line? You can touch it, but not cross. Now generalize the answer, what if the array was nxn. AFTER you have tried this, read on..

Catalan Numbers first appeared in disguise in a problem Euler first proposed to Christian Goldbach in 1751. The problem is now called "Euler's Polygon Division Problem", and asks, in how many ways may
a plane convex polygon of n+2 sides be divided into triangles by diagonals. Euler gave a solution that looked like The numbers in the sequence are now called Catalan Numbers

The numbers in the Catalan sequence also answer questions such as the one at the top of the page. In how many paths can you move from the origin of a coordinate axis to the point (n,n) if each move consists of either an upward move or a move to the right one unit between two lattice points and you cannot cross the line y=x . Another application (or the same application viewed differently) answers the question in how many ways can 2N beans (for an application, think votes) be divided into two containers if one container can never have less than the second?

The sequence of numbers is given by 1,2,5,14,42,132 ... or
in general by the function . It may seem hard to figure out where the 1/(n+1) comes from in the formula. I found a really nice explanation with graphics at this Wikipedia page(go down to the third proof).

The numbers also can be found from Pascal's triangle by taking (2n Choose n) - (2n Choose n+1). These are two adjacent numbers in each even numbered row

The function is named for Eugene Catalan of Belgium (1814-1894).