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

Beweis

Es sei eine -elementige Menge, ein fixiertes Element und

Wir teilen die Partitionen von auf je nachdem, ob ein Block in der Partition ist oder nicht. Eine Partition von , bei der einen Einzelblock bildet, entspricht einer Partition von in Blöcke, was den zweiten Summanden erklärt. Bei einer Partition von , bei der keinen Einzelblock bildet, gehört zu einem Block mit zumindest zwei Elementen. Wenn die Blöcke sind, so ist eine Partition von mit Blöcken. Deren Anzahl beträgt . Eine jede solche Partition kann man auf verschiedene Weisen zu einer Partition auf fortsetzen, je nachdem, zu welchem Block man hinzuschlägt. Dies ergibt den ersten Summanden.