Multinomialkoeffizient

Der Multinomialkoeffizient oder auch Polynomialkoeffizient ist eine Erweiterung des Binomialkoeffizienten. Für nichtnegative ganze Zahlen k₁,...,k_r und n: = k₁ + ... + k_r ist er definiert als

${n \choose k_1, \dots , k_r} := \frac{n!}{k_1!\cdot \dots \cdot 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

${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 des binomischen Satzes gilt das sogenannte Multinomialtheorem (auch Polynomialsatz)

$(x_1+\ldots+x_r)^n=\sum_{k_1+\ldots+k_r=n}{n\choose k_1,\ldots,k_r}\cdot x_1^{k_1}\cdots x_r^{k_r}.$

Aus dem Multinomialsatz folgt sofort:

$\forall r\in\mathbb{N}: r^n=\sum_{k_1+\ldots+k_r=n}{n\choose k_1,\ldots,k_r}\cdot 1^{k_1}\cdots 1^{k_r}=\sum_{k_1+\ldots+k_r=n}{n\choose k_1,\ldots,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) \;=\; {n \choose k_1, \dots , k_r}\cdot p_1^{k_1} \cdot p_2^{k_2} \cdot ... \cdot p_r^{k_r},$

einer Wahrscheinlichkeitsverteilung diskreter Zufallsvariablen.

Kombinatorische Deutungen

Objekte in Kisten

Der Multinomialkoeffizient $\tbinom{n}{k_1,...,k_r}$ gibt die Anzahl der Möglichkeiten an, n Objekte in r Schachteln zu legen, wobei in die erste Schachtel genau k₁ Objekte sollen, in die zweite Schachtel k₂ Objekte, usw.

Beispiel

Wie viele verschiedene Möglichkeiten gibt es, die 32 Karten eines Skatspiels zu je 10 Karten an die 3 Spieler sowie zu 2 Restkarten in den "Skat" zu legen?

Da es sich um n = 32 Objekte handelt, die in r = 4 Schachteln aufzuteilen sind, wobei in die ersten drei Schachteln je k₁ = k₂ = k₃ = 10 Objekte und in die vierte Schachtel k₄ = 2 Objekte sollen, ist die Anzahl der Möglichkeiten durch folgenden Multinomialkoeffizienten gegeben:

${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 $\tbinom{n}{k_1,...,k_r}$ gibt außerdem die Anzahl der verschiedenen Anordnungen von n Dingen an, wobei das erste k₁-mal (ununterscheidbar) vorkommt, das zweite k₂-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, wobei das erste ("M") k₁ = 1-mal, das zweite ("I") k₂ = 4-mal (ununterscheidbar) vorkommt, das dritte ("S") ebenso und das vierte ("P") k₄ = 2-mal. Das ist also der Polynomialkoeffizient

$\binom{11}{1,4,4,2}=\frac{11!}{1!\cdot4!\cdot4!\cdot2!}=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 Simplexe

Analog zum pascalschen Dreieck der Binominalkoeffizienten lassen sich auch die r-ten Multinomialkoeffizienten als geometrische Figuren (Simplexe) anordnen: die Trinomialkoeffizienten führen zur Pascalschen Pyramide, die weiteren zu r-dimensionalen Pascalschen Simplexen.

Weblinks

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