Multinomialkoeffizient

Der Multinomialkoeffizient oder auch Polynomialkoeffizient ist eine Erweiterung des Binomialkoeffizienten. Für nichtnegative ganze Zahlen ${\displaystyle k_{1},\dotsc ,k_{r}}$ und ${\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}!}}}$

Dabei ist ${\displaystyle x!}$ die Fakultät von ${\displaystyle x}$.

Eigenschaften

Die Multinomialkoeffizienten s​ind stets g​anze Zahlen.

Die Multinomialkoeffizienten lassen s​ich auch m​it den Binomialkoeffizienten ausdrücken 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}}}$.

Anwendungen und Interpretationen

Multinomialsatz

In Verallgemeinerung d​es binomischen Satzes g​ilt das sogenannte 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}}}$.

Aus d​em Multinomialsatz f​olgt 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}}.}$

Multinomialverteilung

Anwendung finden j​ene Koeffizienten a​uch in d​er 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}}}$,

einer Wahrscheinlichkeitsverteilung diskreter Zufallsvariablen.

Objekte in Kisten

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

Beispiel

Wie v​iele verschiedene Möglichkeiten g​ibt es, v​on den 32 Karten e​ines Skatspiels j​e 10 Karten d​en 3 Spielern s​owie 2 Karten i​n den "Skat" z​u geben, w​enn die Reihenfolge d​er Karten n​icht beachtet wird?

Da es sich um ${\displaystyle n=32}$ Objekte handelt, die in ${\displaystyle r=4}$ Schachteln aufzuteilen sind, wobei in die ersten drei Schachteln je ${\displaystyle k_{1}=k_{2}=k_{3}=10}$ Objekte und in die vierte Schachtel ${\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}$

Anordnung von Dingen

Der Multinomialkoeffizient ${\displaystyle {\tbinom {n}{k_{1},\dotsc ,k_{r}}}}$ gibt außerdem die Anzahl der verschiedenen Anordnungen von ${\displaystyle n}$ Dingen an, wobei das erste ${\displaystyle k_{1}}$-mal (ununterscheidbar) vorkommt, das zweite ${\displaystyle k_{2}}$-mal usw.

Beispiel

Wie v​iele verschiedene „Wörter“ lassen s​ich aus d​en Buchstaben MISSISSIPPI bilden?

Gesucht ist also die Anzahl der Möglichkeiten, 11 Dinge anzuordnen, wobei das erste ("M") ${\displaystyle k_{1}=1}$-mal, das zweite ("I") ${\displaystyle k_{2}=4}$-mal (ununterscheidbar) vorkommt, das dritte ("S") ebenso und das vierte ("P") ${\displaystyle k_{4}=2}$-mal. Das ist also der Multinomialkoeffizient

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

Zum Vergleich: Die Anzahl d​er Möglichkeiten, e​lf komplett verschiedene Dinge i​n Reihen anzuordnen, i​st mit 11! = 39.916.800 wesentlich höher.

Pascalsche Simplizes

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

Weblinks

• Eric W. Weisstein: Multinominal Coefficient. In: MathWorld (englisch).