Satz - Rekursive Formel der Catalan-Zahlen

Für die Anzahl $B_{n}$ der Binärbäume mit $n$ Knoten gilt:

B_{0} = 1

und für $n > 0$

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

Beweis per Induktion über $n$ .

$n = 0$ .

Es gibt genau einen Binärbaum mit $0$ Knoten.

Wir nehmen an, dass die Aussage für alle $j < n$ schon bewiesen ist.

Ein Binärbaum mit $n$ Knoten besteht aus:

Dabei gilt:

ℓ + 1 + r = n

also

r = n - (ℓ + 1) .

Weiterhin gilt:

0 \leq ℓ \leq n - 1.

Nach Induktionsvoraussetzung gibt es:

Also gilt:

B_{n} = \sum_{ℓ = 0}^{n - 1} B_{ℓ} \cdot B_{n - (ℓ + 1)} .

Mit der Substitution

k := ℓ + 1

erhalten wir:

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