Catalan numbers

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 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 (see also SVG version):

5 sides, 5 ways (SVG version):

6 sides, 14 ways (SVG version):

7 sides, 42 ways (SVG version):

8 sides, 132 ways:

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

Step diagrams:

2 rectangles, 2 ways (see also SVG version):

3 rectangles, 5 ways (SVG version):

4 rectangles, 14 ways (SVG version):

5 rectangles, 42 ways (see also SVG version):

6 rectangles, 132 ways (see also SVG version):

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 × 2 grid:

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. SVG graphics created by hand with the help of some Ruby scripts.

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.

[ home ] || [ 080331 ]