Multinomialkoeffizient

Der Multinomialkoeffizient oder auch Polynomialkoeffizient ist eine Erweiterung des Binomialkoeffizienten. Für nichtnegative ganze Zahlen $k_1,\dots ,k_r$ und $n:=k_1+\cdots +k_r$ ist er definiert als

$(\genfrac{}{}{0ex}{}{n}{k_1,\dots ,k_r}):=\frac{n!}{k_1!\cdots k_r!}$

Dabei ist $x!$ die Fakultät von $x$.

Eigenschaften

Die Multinomialkoeffizienten sind stets ganze Zahlen.

Die Multinomialkoeffizienten lassen sich auch mit den Binomialkoeffizienten ausdrücken als

$(\genfrac{}{}{0ex}{}{k_1+\cdots +k_r}{k_1,\dots ,k_r})=(\genfrac{}{}{0ex}{}{k_1}{k_1})(\genfrac{}{}{0ex}{}{k_1+k_2}{k_2})\cdots (\genfrac{}{}{0ex}{}{k_1+k_2+\cdots +k_r}{k_r})=\prod _{i=1}^r(\genfrac{}{}{0ex}{}{\sum _{s=1}^i{k}_s}{k_i})$.

Anwendungen und Interpretationen

Multinomialsatz

In Verallgemeinerung des binomischen Satzes gilt das sogenannte Multinomialtheorem (auch Multinomialsatz oder Polynomialsatz)

$(x_1+\cdots +x_r{)}^n=\sum _{k_1+\cdots +k_r=n}(\genfrac{}{}{0ex}{}{n}{k_1,\dots ,k_r})\cdot x_1^{k_1}\cdots x_r^{k_r}$.

Aus dem Multinomialsatz folgt sofort:

$\mathrm{\forall }r\in \mathbb{\mathbb{N}}:r^n=\sum _{k_1+\cdots +k_r=n}(\genfrac{}{}{0ex}{}{n}{k_1,\dots ,k_r})\cdot 1^{k_1}\cdots 1^{k_r}=\sum _{k_1+\cdots +k_r=n}(\genfrac{}{}{0ex}{}{n}{k_1,\dots ,k_r}).$

Multinomialverteilung

Anwendung finden jene Koeffizienten auch in der Multinomialverteilung

$P(X_1=k_1,X_2=k_2,\dots ,X_r=k_r)=(\genfrac{}{}{0ex}{}{n}{k_1,\dots ,k_r})\cdot p_1^{k_1}\cdot p_2^{k_2}\cdots p_r^{k_r}$,

einer Wahrscheinlichkeitsverteilung diskreter Zufallsvariablen.

Kombinatorische Deutungen

Objekte in Kisten

Der Multinomialkoeffizient $(\genfrac{}{}{0ex}{}{n}{k_1,\dots ,k_r})$ gibt die Anzahl der Möglichkeiten an, $n$ Objekte in $r$ Schachteln zu legen, wobei in die erste Schachtel genau $k_1$ Objekte sollen, in die zweite Schachtel $k_2$ Objekte usw.

Beispiel

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 $n=32$ Objekte handelt, die in $r=4$ Schachteln aufzuteilen sind, wobei in die ersten drei Schachteln je $k_1=k_2=k_3=10$ Objekte und in die vierte Schachtel $k_4=2$ Objekte sollen, ist die Anzahl der Möglichkeiten durch folgenden Multinomialkoeffizienten gegeben:

$(\genfrac{}{}{0ex}{}{32}{10,10,10,2})=\frac{32!}{10!\cdot 10!\cdot 10!\cdot 2!}=2.753.294.408.504.640$

Anordnung von Dingen

Der Multinomialkoeffizient $(\genfrac{}{}{0ex}{}{n}{k_1,\dots ,k_r})$ gibt außerdem die Anzahl der verschiedenen Anordnungen von $n$ Dingen an, wobei das erste $k_1$-mal (ununterscheidbar) vorkommt, das zweite $k_2$-mal usw.

Beispiel

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

Gesucht ist also die Anzahl der Möglichkeiten, 11 Dinge anzuordnen, wobei das erste ("M") $k_1=1$-mal, das zweite ("I") $k_2=4$-mal (ununterscheidbar) vorkommt, das dritte ("S") ebenso und das vierte ("P") $k_4=2$-mal. Das ist also der Multinomialkoeffizient $(\genfrac{}{}{0ex}{}{11}{1,4,4,2})=\frac{11!}{1!\cdot 4!\cdot 4!\cdot 2!}=34.650$

Zum Vergleich: Die Anzahl der Möglichkeiten, elf komplett verschiedene Dinge in Reihen anzuordnen, ist mit 11! = 39.916.800 wesentlich höher.

Pascalsche Simplizes

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