Catalan number
The Catalan numbers are an integer sequence. They are named for Eugène Charles Catalan, who found the relationship between these numbers and parentheses. They were previously described by Mingantu in 1731 and Leonhard Euler in 1757.
The first ten Catalan numbers are
- 1, 1, 2, 5, 42, 132, 429, 1430, 4862, 16796... (sequence [{{fullurl:OEIS:{{{id}}}}} {{{id}}}] in OEIS)
Definition
The Catalan numbers can be written in terms of the binomial coefficient: [math]\displaystyle{ C_{n} = \frac{1}{2n+1} \binom{2n+1}{n} = \binom{2n}{n} - \binom{2n}{n+1} }[/math] They satisfy two significant recurrence relations, starting from [math]\displaystyle{ C_{0}=1 }[/math]: [math]\displaystyle{ C_{n+1}= \sum_{k=0}^{n} C_{k}C_{n-k} =\frac{2(2n+1)}{n+2} C_{n} }[/math]
Catalan Number Media
The C5 = 42 noncrossing partitions of a 5-element set (below, the other 10 of the 52 partitions)
Lattice of the 14 Dyck words of length 8 – ( and ) interpreted as up and down
Catalan 4 leaves binary tree example
The associahedron of order 4 with the C4=14 full binary trees with 5 leaves
Catalan number 4x4 grid example
The dark triangle is the root node, the light triangles correspond to internal nodes of the binary trees, and the green bars are the leaves.
Illustrating the fifth Catalan number.
Stairstep interpretation of Catalan numbers
Figure 1. The invalid portion of the path (dotted red) is flipped (solid red). Bad paths (after the flip) reach (n – 1, n + 1) instead of (n, n).
Figure 2. A path with exceedance 5.
