Kommutativer Halbring/Multinomialsatz/Fakt/Beweis

Beweis

Bei einem Produkt von Summen in einem kommutativen Halbring muss jeder Summand mit jedem Summanden multipliziert werden. Betrachten wir also

${}{\left(x_{1}+\cdots +x_{k}\right)}^{n}={\left(x_{1}+\cdots +x_{k}\right)}\cdot {\left(x_{1}+\cdots +x_{k}\right)}\cdots {\left(x_{1}+\cdots +x_{k}\right)}\,$

mit ${}n$ Faktoren. In jedem Faktor wird jeweils ein Summand ${}x_{i}$ ausgewählt, dies ergibt stets ein Produkt der Form ${}x_{1}^{r_{1}}\cdots x_{k}^{r_{k}}$ mit

${}r_{1}+\cdots +r_{k}=n\,.$

Dabei ist ${}r_{j}$ die Anzahl, wie oft ${}x_{j}$ ausgewählt wurde. Somit ist die Gesamtpotenz eine Summe mit den Summanden ${}x_{1}^{r_{1}}\cdots x_{k}^{r_{k}}$, und wir müssen uns fragen, wie viele Möglichkeiten es gibt, ${}n$-fach aus der Menge ${}\{1,2,\ldots ,k\}$ Elemente zu ziehen, derart, dass die Zahl ${}j$ genau ${}r_{j}$-fach gezogen wird. Die Anzahl dieser Möglichkeiten wird aber durch die Multinomialkoeffizienten ${}{\binom {n}{r_{1},\dotsc ,r_{k}}}$ beschrieben.

Zur bewiesenen Aussage