Endliche Mengen/Abbildung/Faseranzahl/Multinomialkoeffizienten/Fakt/Beweis

Beweis

Für die Faser über ${}1$ gibt es ${}{\binom {n}{r_{1}}}$ Möglichkeiten, man muss ja die ${}r_{1}$ Elemente auswählen, die auf die ${}1$ gehen sollen. Wenn dies festgelegt ist, so gibt es für die Faser über ${}2$ genau ${}{\binom {n-r_{1}}{r_{2}}}$ Möglichkeiten. In diesem Sinne gibt es für die Faser über ${}j$ genau ${}{\binom {n-r_{1}-\cdots -r_{j-1}}{r_{j}}}$ Möglichkeiten. Wenn man diese Zahlen miteinander multipliziert, so ergibt sich

${}{\begin{aligned}&\,\,\,\,\,\,\,{\binom {n}{r_{1}}}{\binom {n-r_{1}}{r_{2}}}\cdots {\binom {n-r_{1}-\cdots -r_{k-2}}{r_{k-1}}}\cdot {\binom {n-r_{1}-\cdots -r_{k-1}}{r_{k}}}\\&={\frac {n\cdots (n-r_{1}+1)}{r_{1}!}}\cdot {\frac {(n-r_{1})\cdots (n-r_{1}-r_{2}+1)}{r_{2}!}}\cdots {\frac {(n-r_{1}-\cdots -r_{k-2})\cdots (n-r_{1}-\cdots -r_{k-2}-r_{k-1}+1)}{r_{k-1}!}}\cdot {\frac {(n-r_{1}-\cdots -r_{k-2}-r_{k-1})\cdots 1}{r_{k}!}}\\&={\frac {n!}{r_{1}!r_{2}!\cdots r_{k}!}},\,\end{aligned}}$

also der Multinomialkoeffizient.

Zur bewiesenen Aussage