Catalan numbers

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 rooted, trivalent trees with n+1 nodes; 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)

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

(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)

(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)

3 nodes:

4 nodes:

5 nodes:

6 nodes:

7 nodes:

8 nodes:
(Tucked away in file cattree8.gif; around 17K.)

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 for the Apple Macintosh. 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.

Copyright © 1996 Robert M. Dickau

Back to Catalan

[ mail rmd ]