Multinomialkoeffizient

Der Multinomialkoeffizient oder auch Polynomialkoeffizient ist eine Verallgemeinerung des Binomialkoeffizienten. Für nichtnegative ganze Zahlen ${\displaystyle k_{1},\dotsc ,k_{r}}${\displaystyle k_{1},\dotsc ,k_{r}} und ${\displaystyle n:=k_{1}+\dotsb +k_{r}}${\displaystyle n:=k_{1}+\dotsb +k_{r}} ist er definiert als

${\displaystyle {n \choose k_{1},\dotsc ,k_{r}}:={\frac {n!}{k_{1}!\dotsm k_{r}!}}.}${\displaystyle {n \choose k_{1},\dotsc ,k_{r}}:={\frac {n!}{k_{1}!\dotsm k_{r}!}}.}^[1]

Dabei ist ${\displaystyle n!=n\cdot (n-1)\dots 2\cdot 1}${\displaystyle n!=n\cdot (n-1)\dots 2\cdot 1} die Fakultät von ${\displaystyle n}${\displaystyle n} bzw. analog ${\displaystyle k_{i}!}${\displaystyle k_{i}!} die Fakultät von ${\displaystyle k_{i}}${\displaystyle k_{i}}.

Für ${\displaystyle r=2}${\displaystyle r=2} und ${\displaystyle k:=k_{1}}${\displaystyle k:=k_{1}} muss ${\displaystyle k_{2}=n-k}${\displaystyle k_{2}=n-k} sein und man erhält als Spezialfall den Binomialkoeffizienten ${\displaystyle {n \choose k}={n \choose k_{1},k_{2}}={\frac {n!}{k!(n-k)!}}}${\displaystyle {n \choose k}={n \choose k_{1},k_{2}}={\frac {n!}{k!(n-k)!}}}.

Multinomialkoeffizienten sind stets ganzzahlig.

Sie lassen sich aus verschiedene Arten darstellen, zum Beispiel auch mithilfe von Binomialkoeffizienten als

${\displaystyle {k_{1}+\cdots +k_{r} \choose k_{1},\ldots ,k_{r}}={k_{1} \choose k_{1}}{k_{1}+k_{2} \choose k_{2}}\cdots {k_{1}+k_{2}+\cdots +k_{r} \choose k_{r}}=\prod _{i=1}^{r}{\sum _{s=1}^{i}k_{s} \choose k_{i}}}${\displaystyle {k_{1}+\cdots +k_{r} \choose k_{1},\ldots ,k_{r}}={k_{1} \choose k_{1}}{k_{1}+k_{2} \choose k_{2}}\cdots {k_{1}+k_{2}+\cdots +k_{r} \choose k_{r}}=\prod _{i=1}^{r}{\sum _{s=1}^{i}k_{s} \choose k_{i}}}.

Multinomialkoeffizienen treten auf, wenn man ein Multinom, also eine Summe mit mehr als zwei Summanden potenziert. In Verallgemeinerung des binomischen Satzes gilt nämlich nach dem Multinomialtheorem (auch Polynomialsatz)

${\displaystyle (x_{1}+\dotsb +x_{r})^{n}=\sum _{k_{1}+\dotsb +k_{r}=n}{n \choose k_{1},\dotsc ,k_{r}}\cdot x_{1}^{k_{1}}\dotsm x_{r}^{k_{r}}}${\displaystyle (x_{1}+\dotsb +x_{r})^{n}=\sum _{k_{1}+\dotsb +k_{r}=n}{n \choose k_{1},\dotsc ,k_{r}}\cdot x_{1}^{k_{1}}\dotsm x_{r}^{k_{r}}}.

Hieraus folgt sofort:

${\displaystyle \forall r\in \mathbb {N} :r^{n}=\sum _{k_{1}+\dotsb +k_{r}=n}{n \choose k_{1},\dotsc ,k_{r}}\cdot 1^{k_{1}}\dotsm 1^{k_{r}}=\sum _{k_{1}+\dotsb +k_{r}=n}{n \choose k_{1},\dotsc ,k_{r}}.}${\displaystyle \forall r\in \mathbb {N} :r^{n}=\sum _{k_{1}+\dotsb +k_{r}=n}{n \choose k_{1},\dotsc ,k_{r}}\cdot 1^{k_{1}}\dotsm 1^{k_{r}}=\sum _{k_{1}+\dotsb +k_{r}=n}{n \choose k_{1},\dotsc ,k_{r}}.}

Anwendung finden jene Koeffizienten auch in der Multinomialverteilung

${\displaystyle P(X_{1}=k_{1},X_{2}=k_{2},\dotsc ,X_{r}=k_{r})\;=\;{n \choose k_{1},\dotsc ,k_{r}}\cdot p_{1}^{k_{1}}\cdot p_{2}^{k_{2}}\dotsm p_{r}^{k_{r}}}${\displaystyle P(X_{1}=k_{1},X_{2}=k_{2},\dotsc ,X_{r}=k_{r})\;=\;{n \choose k_{1},\dotsc ,k_{r}}\cdot p_{1}^{k_{1}}\cdot p_{2}^{k_{2}}\dotsm p_{r}^{k_{r}}},

einer Wahrscheinlichkeitsverteilung diskreter Zufallsvariablen.

Der Multinomialkoeffizient ${\displaystyle {\tbinom {n}{k_{1},\dotsc ,k_{r}}}}${\displaystyle {\tbinom {n}{k_{1},\dotsc ,k_{r}}}} gibt die Anzahl der Möglichkeiten an, ${\displaystyle n}${\displaystyle n} (unterscheidbare) Objekte in ${\displaystyle r}${\displaystyle r} Schachteln zu legen, wobei in die erste Schachtel genau ${\displaystyle k_{1}}${\displaystyle k_{1}} Objekte sollen, in die zweite Schachtel ${\displaystyle k_{2}}${\displaystyle k_{2}} Objekte usw.

Wie viele verschiedene Möglichkeiten gibt es, von den 32 Karten eines Skatspiels je 10 Karten den 3 Spielern sowie 2 Karten in den "Skat" zu geben, wenn die Reihenfolge der Karten nicht beachtet wird?

Da es sich um ${\displaystyle n=32}${\displaystyle n=32} Objekte handelt, die in ${\displaystyle r=4}${\displaystyle r=4} Schachteln aufzuteilen sind, wobei in die ersten drei Schachteln je ${\displaystyle k_{1}=k_{2}=k_{3}=10}${\displaystyle k_{1}=k_{2}=k_{3}=10} Objekte und in die vierte Schachtel ${\displaystyle k_{4}=2}${\displaystyle k_{4}=2} Objekte sollen, ist die Anzahl der Möglichkeiten durch folgenden Multinomialkoeffizienten gegeben:

${\displaystyle {32 \choose 10,,10,円,10,円,2円}={\frac {32!}{10!\cdot 10!\cdot 10!\cdot 2!}}=2.753.294.408.504.640}${\displaystyle {32 \choose 10,,10,円,10,円,2円}={\frac {32!}{10!\cdot 10!\cdot 10!\cdot 2!}}=2.753.294.408.504.640}

Der Multinomialkoeffizient ${\displaystyle {\tbinom {n}{k_{1},\dotsc ,k_{r}}}}${\displaystyle {\tbinom {n}{k_{1},\dotsc ,k_{r}}}} gibt außerdem die Anzahl der verschiedenen Anordnungen von ${\displaystyle n}${\displaystyle n} Objekten an, von denen ${\displaystyle k_{1},k_{2},\ldots ,k_{r}}${\displaystyle k_{1},k_{2},\ldots ,k_{r}} gleich sind.^[2]

Wie viele verschiedene „Wörter" lassen sich aus den Buchstaben MISSISSIPPI bilden?

Gesucht ist also die Anzahl der Möglichkeiten, elf Buchstaben (${\displaystyle n=11}${\displaystyle n=11}) anzuordnen, wobei das "M" einmal (${\displaystyle k_{1}=1}${\displaystyle k_{1}=1}), das "I" sowie das "S" jeweils viermal (${\displaystyle k_{2}=k_{3}=4}${\displaystyle k_{2}=k_{3}=4}) und das "P" zweimal (${\displaystyle k_{4}=2}${\displaystyle k_{4}=2}) vorkommt. Diese Anzahl beträgt

${\displaystyle {\binom {11}{1,4,4,2}}={\frac {11!}{1!\cdot 4!\cdot 4!\cdot 2!}}=34.650.}${\displaystyle {\binom {11}{1,4,4,2}}={\frac {11!}{1!\cdot 4!\cdot 4!\cdot 2!}}=34.650.}

Zum Vergleich: Die Anzahl der Möglichkeiten, elf paarweise verschiedene Objekte anzuordnen, ist mit 11! = 39.916.800 wesentlich höher.

Analog zum pascalschen Dreieck der Binomialkoeffizienten lassen sich auch die ${\displaystyle r}${\displaystyle r}-ten Multinomialkoeffizienten als geometrische Figuren (Simplizes) anordnen: Die Trinomialkoeffizienten führen zur pascalschen Pyramide, die weiteren zu ${\displaystyle r}${\displaystyle r}-dimensionalen pascalschen Simplizes.

• Eric W. Weisstein: Multinominal Coefficient. In: MathWorld (englisch).
• Norbert Henze: Multinomialkoeffizient und multinomialer Lehrsatz In: KIT-Bibliothek Medienportal

1. ↑ Tilo Arens et al.: Mathematik. 5. Auflage. Springer, Berlin 2022, ISBN 978-3-662-64388-4, S. 93. 
2. ↑ Karl Mosler, Friedrich Schmid: Wahrscheinlichkeitsrechnung und schließende Statistik. 2. Auflage. Springer, Berlin / Heidelberg 2006, ISBN 978-3-540-27787-3, S. 19. 

• Kombinatorik