Catalan numbers

Catalan numbers are a sequence of natural numbers that appear in many counting problems, often involving recursive structures. The $n$th Catalan number, usually written as $C_n$, counts things like the number of ways to correctly match $n$ pairs of parentheses, the number of ways to split a polygon with $n+2$ sides into triangles, or the number of non-crossing handshakes among $2n$ people sitting around a table.

Important properties

• The first few Catalan numbers are: $C_0 = 1$, $C_1 = 1$, $C_2 = 2$, $C_3 = 5$, $C_4 = 14$, $C_5 = 42$.

• Catalan numbers can be defined recursively: $C_0 = 1$, and for $n \geq 1$, $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$.

• Catalan numbers have a closed formula: $C_n = \frac{1}{n+1} \binom{2n}{n}$.

• They count many different combinatorial objects, such as valid bracket sequences, rooted binary trees, and non-crossing partitions.