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:

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 in which parentheses can be placed in a sequence of numbers to be multiplied, two at a time;
• the number of planar binary trees trees with n+1 leaves; and
• the number of paths of length 2n through an n-by-n grid that do not rise above the main diagonal.

Polygon diagrams

(code hidden for your protection)

4 sides, 2 ways:

5 sides, 5 ways:

6 sides, 14 ways:

7 sides, 42 ways:

8 sides, 132 ways:

9 sides, 429 ways:
(Hidden in file catalan9.gif; around 29K.)

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:

4 nodes:

5 nodes:

6 nodes:

Path diagrams

2 x 2 grid:

3 x 3 grid:

4 x 4 grid:

5 x 5 grid:

6 x 6 grid:
(Out of the way in file catalanpath6.gif; around 24K.)

Designed and rendered using Mathematica 3.0. 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-2005 The Math Forum
http://mathforum.org/