Satz - Rekursion der Stirling-Zahlen zweiter Art

Für alle $k, n \in N$ mit $n \geq k$ gilt:

S_{n, k} = S_{n - 1, k - 1} + k S_{n - 1, k} .

Wir betrachten die k-Partitionen der Menge

A = {a_{1}, \dots, a_{n}} .

$a_{n}$ liegt alleine in einer Partition.

Dann müssen die übrigen $n - 1$ Elemente auf die restlichen $k - 1$ Partitionen verteilt werden.

Davon gibt es:

S_{n - 1, k - 1}

viele.

$a_{n}$ liegt nicht alleine in einer Partition.

Dann gibt es:

S_{n - 1, k}

Partitionen der übrigen Elemente.

Das Element $a_{n}$ kann in jede der $k$ Partitionen eingefügt werden.

Also gibt es:

k S_{n - 1, k}

Möglichkeiten.

Insgesamt:

S_{n, k} = S_{n - 1, k - 1} + k S_{n - 1, k} .