Eugène Charles Catalan (born: 30 May 1814 in Bruges, Belgium - died: 14 Feb 1894 in Liège, Belgium ) defined the numbers, called today the Catalan numbers, while considering the solution of the problem of dissecting a polygon into triangles by means of non-intersecting diagonals. Catalan was not the first to solve the problem, however, since Segner had solved it in the 18 th century, although his solution was not as elegant as Catalan's. Euler had worked on simplifying the solution to the problem as did Binet at almost the same time as Catalan, around 1838.
The Catalan Numbers are a sequence of numbers which show up in many contexts. They were discovered by Leonhard Euler when he was attempting to find a general formula to express the number of ways to divide a polygon with N sides into triangles using non-intersecting diagonals . The Catalan Numbers' correspondence to the division of polygons is shown below:

Number of sides	3	4	5	6	7	8	9
Number of way to partition it into triangles	1	2	5	14	42	132	429

The first few Catalan numbers for n = 1, 2, ... are 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ... (Sloane's A000108).

An explicit formula for is given by

(1)

where denotes a central binomial coefficient and is the usual factorial. A recurrence relation for is obtained from

(2)

so

(3)

There are at least two ways they can be found in Pascal's triangle, one in the middle column going down the center, subtracting the element immediately adjacent (see numbers in red),

and another one row above, taking the Nth term over and subtracting the term immediately to the right (numbers in blue).

See the next examples:

and:

You can see in next Pascal Triangle that each Catalan number is the sum of specific Pascal numbers.(© Dirk Laureyssens, 2004)

	See Also: Pascal Triangle - History     Pascal Triangle    Fibonacci Numbers and the Pascal Triangle    Lucas Numbers and the Pascal Triangle    Fibonacci polynomial and the Pascal Triangle    Chebyshev polynomial and the Pascal Triangle    Pascal Triangle of the Second Kind and Catalan Numbers             Back to contents   Back to main page
2001-2005 Radoslav Jovanovic                 updated: November 2004.