Satz - Rekursion der Stirling-Zahlen erster Art

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

s_{n, k} = s_{n - 1, k - 1} + (n - 1) s_{n - 1, k} .

Sei

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

Wir zählen die Permutationen in zwei Fällen.

$a_{n}$ ist ein Fixpunkt, also ein eigener Zyklus $(a_{n})$ .

Dann gibt es:

s_{n - 1, k - 1}

Möglichkeiten.

$a_{n}$ liegt in einem Zyklus der Länge größer als $1$ .

Dann gibt es:

s_{n - 1, k}

Permutationen der übrigen Elemente.

Das Element $a_{n}$ kann an

n - 1

verschiedenen Stellen in bestehende Zyklen eingefügt werden.

Also gibt es:

(n - 1) s_{n - 1, k}

Möglichkeiten.

Insgesamt:

s_{n, k} = s_{n - 1, k - 1} + (n - 1) s_{n - 1, k} .