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

Beweis

Wir verwenden durchgehend Fakt, das besagt, dass ${}k!S({n},{k})$ gleich der Anzahl der surjektiven Abbildungen einer ${}n$-elementigen Menge in eine ${}k$-elementige Menge ist.

1. Dies folgt aus Fakt.
2. Nach Fakt ist die Anzahl der surjektiven Abbildungen einer ${}n$-elementigen Menge in eine ${}k$-elementige Menge gleich

   $\sum _{(a_{1},\ldots ,a_{k}):\,a_{1}+a_{2}+\cdots +a_{k}=n,\,a_{j}\geq 1}1^{a_{1}}2^{a_{2}}\cdots k^{a_{k}}.$

   Wenn man diesen Ausdruck durch ${}k!$ dividiert, und überall ${}c_{j}=a_{j}-1$ ersetzt, so erhält man die Behauptung.

3. Dies ergibt sich aus Teil (2). Zu einem Tupel ${}(i_{1},\ldots ,i_{n-k})$ der Indexmenge aus Teil (3) definiert man

   ${}c_{j}:={\#\left({\left\{s\mid i_{s}=j\right\}}\right)}\,$

   für ${}j=1,\ldots ,k$. Umgekehrt definiert man zu einem Tupel ${}(c_{1},\ldots ,c_{k})$ der Indexmenge aus Teil (2) die Zahlen

   ${}i_{t}=j\,$

   für ${}t$ zwischen ausschließlich ${}c_{1}+\cdots +c_{j-1}$ und einschließlich ${}c_{1}+\cdots +c_{j-1}+c_{j}$. Diese Zuordnungen sind invers zueinander und die aufzusummierenden Produkte stimmen überein.

4. Dies folgt aus Fakt.

Zur bewiesenen Aussage