Catalan numbers

_____________________________________
Back to Robert's Math Figures
_____________________________________

The Catalan numbers (1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ...), named after Eugène Charles Catalan (1814–1894), arise in a number of problems in combinatorics. They can be computed using this formula:

C(2n, n)/(n + 1)

Among other things, the Catalan numbers describe:

  • the number of ways a polygon with n+2 sides can be cut into n triangles
  • the number of ways to use n rectangles to tile a stairstep shape (1, 2, ..., n−1, n).
  • the number of ways in which parentheses can be placed in a sequence of numbers to be multiplied, two at a time
  • the number of planar binary trees with n+1 leaves
  • the number of paths of length 2n through an n-by-n grid that do not rise above the main diagonal

Polygon diagrams:

4 sides, 2 ways:
[ Catalan 4 -- sorry: not much to see without graphics ]

5 sides, 5 ways:

6 sides, 14 ways:

7 sides, 42 ways:

8 sides, 132 ways:

9 sides, 429 ways:
(Hidden in file catalan9.png.)

Step diagrams:

2 rectangles, 2 ways:

3 rectangles, 5 ways:

4 rectangles, 14 ways:

5 rectangles, 42 ways:

6 rectangles, 132 ways:

Multiplication diagrams:

3 numbers:

(1 (2 3))   ((1 2) 3)

4 numbers:

(1 (2 (3 4)))   (1 ((2 3) 4))
((1 2) (3 4))   ((1 (2 3)) 4)
(((1 2) 3) 4)

5 numbers:

(1 (2 (3 (4 5))))   (1 (2 ((3 4) 5)))
(1 ((2 3) (4 5)))   (1 ((2 (3 4)) 5))
(1 (((2 3) 4) 5))   ((1 2) (3 (4 5)))
((1 2) ((3 4) 5))   ((1 (2 3)) (4 5))
((1 (2 (3 4))) 5)   ((1 ((2 3) 4)) 5)
(((1 2) 3) (4 5))   (((1 2) (3 4)) 5)
(((1 (2 3)) 4) 5)   ((((1 2) 3) 4) 5)

6 numbers:

(1 (2 (3 (4 (5 6)))))   (1 (2 (3 ((4 5) 6))))
(1 (2 ((3 4) (5 6))))   (1 (2 ((3 (4 5)) 6)))
(1 (2 (((3 4) 5) 6)))   (1 ((2 3) (4 (5 6))))
(1 ((2 3) ((4 5) 6)))   (1 ((2 (3 4)) (5 6)))
(1 ((2 (3 (4 5))) 6))   (1 ((2 ((3 4) 5)) 6))
(1 (((2 3) 4) (5 6)))   (1 (((2 3) (4 5)) 6))
(1 (((2 (3 4)) 5) 6))   (1 ((((2 3) 4) 5) 6))
((1 2) (3 (4 (5 6))))   ((1 2) (3 ((4 5) 6)))
((1 2) ((3 4) (5 6)))   ((1 2) ((3 (4 5)) 6))
((1 2) (((3 4) 5) 6))   ((1 (2 3)) (4 (5 6)))
((1 (2 3)) ((4 5) 6))   ((1 (2 (3 4))) (5 6))
((1 (2 (3 (4 5)))) 6)   ((1 (2 ((3 4) 5))) 6)
((1 ((2 3) 4)) (5 6))   ((1 ((2 3) (4 5))) 6)
((1 ((2 (3 4)) 5)) 6)   ((1 (((2 3) 4) 5)) 6)
(((1 2) 3) (4 (5 6)))   (((1 2) 3) ((4 5) 6))
(((1 2) (3 4)) (5 6))   (((1 2) (3 (4 5))) 6)
(((1 2) ((3 4) 5)) 6)   (((1 (2 3)) 4) (5 6))
(((1 (2 3)) (4 5)) 6)   (((1 (2 (3 4))) 5) 6)
(((1 ((2 3) 4)) 5) 6)   ((((1 2) 3) 4) (5 6))
((((1 2) 3) (4 5)) 6)   ((((1 2) (3 4)) 5) 6)
((((1 (2 3)) 4) 5) 6)   (((((1 2) 3) 4) 5) 6)

Tree diagrams:

3 nodes:
[ again, not much without pictures -- sorry ]

4 nodes:

5 nodes:

6 nodes:

Path diagrams:

2 × 2 grid:
[ Again, a picture speaks a thousand etc. ]

3 × 3 grid:

4 × 4 grid:

5 × 5 grid:

6 × 6 grid:
(Out of the way in file catpath6.png.)

Originally designed and rendered using Mathematica 3.0 for the Apple Macintosh. PNG conversions performed with an old version of ImageMagick.

Inspiration and facts (though not figures) by Brian Hayes, "A Question of Numbers", American Scientist, January–February 1996; Steven S. Skiena, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Addison-Wesley, 1990; Fred S. Roberts, Applied Combinatorics, Prentice-Hall, 1984; and D. E. Knuth, Sorting and Searching (vol. 3 of The Art of Computer Programming), Addison-Wesley, 1973. Catalan dates from Florian Cajori, A History of Mathematics, The Macmillan Company, 1922.

See also Martin Gardner, Time Travel and Other Mathematical Bewilderments, Chapter 20, W. H. Freeman, 1988; and Ilan Vardi, Computational Recreations in Mathematica, Chapter 9, Addison-Wesley, 1991.

[Privacy Policy] [Terms of Use]

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

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

Copyright © 1996-2008 Robert M. Dickau