Kommutativer Halbring/Multinomialsatz/Fakt/Beweis/Aufgabe/Lösung

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

${\displaystyle {}{\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 ${\displaystyle {}n}$ Faktoren. In jedem Faktor wird jeweils ein Summand ${\displaystyle {}x_{i}}$ ausgewählt, dies ergibt stets ein Produkt der Form ${\displaystyle {}x_{1}^{r_{1}}\cdots x_{k}^{r_{k}}}$ mit

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

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

${\displaystyle {}{\binom {n}{r_{1},\dotsc ,r_{k}}}}$