Catalan-Zahlen

Die Zahlen $B_{n}$ der Binärbäume mit $n$ Knoten heißen Catalan-Zahlen.
Es gilt:

B_{0} = 1

und für $n > 0$

B_{n} = \sum_{k = 1}^{n} B_{k - 1} B_{n - k} .

Außerdem gilt:

B_{n} = \frac{1}{n + 1} (\binom{2 n}{n}) .