Partitionen/Stirling-Zahlen zweiter Art/Rekursion/Fakt/Beweis

Beweis

Es sei $M$ eine $(n + 1)$ -elementige Menge, $m \in M$ ein fixiertes Element und

N := M ∖ {m} .

Wir teilen die Partitionen von $M$ je nachdem auf, ob ${m}$ ein Block in der Partition ist oder nicht. Eine Partition von $M$ , bei der ${m}$ einen Einzelblock bildet, entspricht einer Partition von $N$ in $k - 1$ Blöcke, was den zweiten Summanden erklärt. Bei einer Partition von $M$ , bei der ${m}$ keinen Einzelblock bildet, gehört $m$ zu einem Block mit zumindest zwei Elementen. Wenn $B_{1}, \dots, B_{k}$ die Blöcke sind, so ist $B_{1} \cap N, \dots, B_{k} \cap N$ eine Partition von $N$ mit $k$ Blöcken. Deren Anzahl beträgt $S (n, k)$ . Eine jede solche Partition kann man auf $k$ verschiedene Weisen zu einer Partition auf $M$ fortsetzen, je nachdem, zu welchem Block man $m$ hinzuschlägt. Dies ergibt den ersten Summanden.

Zur bewiesenen Aussage