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\setminus \{m\}\,.$

Wir teilen die Partitionen von ${}M$ auf je nachdem, 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},\ldots ,B_{k}$ die Blöcke sind, so ist ${}B_{1}\cap N,\ldots ,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