# 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 fall below the main diagonal

The following figures show some of the interpretations—polygon divisions, binary trees, pairwise multiplication—combined. For n=2:

And n=3:

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:

3 rectangles, 5 ways (SVG version):

4 rectangles, 14 ways (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:

The Catalan interpretations can be partially ordered and arranged into a lattice called a Tamari lattice:

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” [dead link], 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; 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; R. P. Stanley, Enumerative Combinatorics, Volume 2, Cambridge: Cambridge University Press, 1999.

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.