Multinomialkoeffizient

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

{n \choose k_1, \dotsc, k_r} := \frac{n!}{k_1!\dotsm k_r!}

Dabei ist  x! die Fakultät von  x .

Eigenschaften[Bearbeiten]

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}\dotsm{k_1+k_2+\dotsb+k_r\choose k_r} = \prod_{i=1}^r {\sum_{s=1}^i k_s \choose k_i}

Anwendungen und Interpretationen[Bearbeiten]

Multinomialsatz[Bearbeiten]

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

(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 dem Multinomialsatz folgt sofort:

\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[Bearbeiten]

Anwendung finden jene Koeffizienten auch in der Multinomialverteilung

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.

Kombinatorische Deutungen[Bearbeiten]

Objekte in Kisten[Bearbeiten]

Der Multinomialkoeffizient \tbinom{n}{k_1,\dotsc,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[Bearbeiten]

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_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:

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

Anordnung von Dingen[Bearbeiten]

Der Multinomialkoeffizient \tbinom{n}{k_1,\dotsc,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[Bearbeiten]

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

\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 Simplizes[Bearbeiten]

Analog zum pascalschen Dreieck der Binominalkoeffizienten 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.

Weblinks[Bearbeiten]