The Catalan Numbers express the number of ways you can divide a polygon with N sides into triangles, using non-intersecting diagonals.

 no. of polygon sides 3 4 5 6 7 8 9 no. of ways to divide 1 2 5 14 42 132 429

These numbers are today called the Catalan numbers after the Belgian Eugène Charles Catalan, who however was not the first to solve the problem, since Segner had solved it in the 18th century and Euler and Binet also worked on simplifying the solution.

Seth Johnson writes that in 1838, Catalan "solved the problem of how many ways one can parenthesize a chain of N+1 letters using N pairs of parentheses such that there are either two letters, a parenthesized expression and a letter, or two parenthesized expressions within each pair of parentheses. The answer for any positive number N is the Nth Catalan Number."

The Catalan Numbers can be computed using this formula:

and 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 green).

 1 1 1 1 2 - 1 1 3 3 - 1 1 4 6 - 4 1 1 5 10 10 - 5 1 1 6 15 20 - 15 6 1 1 7 21 35 35 - 21 7 1 1 8 28 56 70 - 56 28 8 1 ... 126 126 - 84 ... ... 210 252 - 210 ... ... 462 462 - 330 ... ... 792 924 - 792 ...

References

1. Robert Dickau: Catalan Numbers
2. Brian Hayes: A Question of Numbers
3. Seth Johnson: The Catalan Numbers in Pascal's Triangle
4. Kevin Brown: The Meanings of Catalan Numbers