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 the formula:

\large\frac 1 {n+1}{_{2n}C_n}

and satisfy the recurrence relation

C_{0} =1

C_{n+1} = \large\frac{2(2n+1)}{n+2}\normalsize C_{n}

Among other things, the Catalan numbers describe

Polygons: the number of ways a polygon with $n+2$ sides can be cut into $n$ triangles.
Parentheses: the number of ways in which parentheses can be placed in a sequence of numbers to be multiplied, two at a time.
Trees: the number of rooted, trivalent trees with $n+1$ nodes.
Paths: the number of paths of length $2n$ through an $n \times n$ grid that do not rise above the main diagonal,
Stairs: the number of ways to decompose a staircase-shaped figure with $n$ steps into $n$ rectangles.

Polygons

4 sides, 2 ways:
catalan4

5 sides, 5 ways:
catalan5

6 sides, 14 ways:
catalan6

7 sides, 42 ways:
catalan7

8 sides, 132 ways:
catalan8

9 sides, 429 ways:
catalan9

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:

7 nodes:

8 nodes:

Path diagrams:

2 x 2 grid:
catalanpath2

3 x 3 grid:
catalanpath3

4 x 4 grid:
catalanpath4

5 x 5 grid:
catalanpath5

6 x 6 grid:
catalanpath6

Staircases:

n

= 2

n

= 3

n

= 4

n

= 5

Robert M Dickau, Heinz Klaus Strick

References (show)

B Hayes, A Question of Numbers, American Scientist, January-February 1996
S S Skiena, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Addison-Wesley, 1990
F S Roberts, Applied Combinatorics, Prentice-Hall, 1984
D E Knuth, Sorting and Searching (vol. 3 of The Art of Computer Programming), Addison-Wesley,
Martin Gardner, Time Travel and Other Mathematical Bewilderments, chapter 20, W. H. Freeman, 1988.
Ilan Vardi, Computational Recreations in Mathematica, chapter 9, Addison-Wesley, 1991.