_____________________________________
Exploring Pascal || Student Center || Teachers' Place
_____________________________________

        

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


[Pascal Web Unit]
[Web Links] [Lessons] [Standards]
[Teacher Reference] [Number Patterns]


[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.