Catalan numbers

Definition

The Catalan numbers $C_n$, for natural numbers $n$, are defined by the recursion $$C_0 = 1, \qquad C_{n+1} = \sum_{i=0}^{n} C_i\, C_{n-i}.$$

Remarks

The first values, for $n = 0, 1, \dots, 7$, are $1, 1, 2, 5, 14, 42, 132, 429$. The closed formula is $C_n = \frac{1}{n+1} \binom{2n}{n}$. $C_n$ counts Dyck words of semilength $n$ and binary trees with $n$ nodes, and many other families.

Explanations

L1 human

Catalan numbers count many structures that split into a left part and a right part. For example, there are $C_3 = 5$ ways to put brackets on a product $abcd$ of four factors: $((ab)c)d$, $(a(bc))d$, $(ab)(cd)$, $a((bc)d)$ and $a(b(cd))$.