Multinomialkoeffizient

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

<math>{n \choose k_1, \dotsc, k_r} := \frac{n!}{k_1!\dotsm k_r!}.

</math><ref></ref>

Dabei ist <math> n! = n\cdot(n-1)\dots 2 \cdot 1 </math> die Fakultät von <math> n </math> bzw. analog <math> k_i! </math> die Fakultät von <math>k_i</math>.

Für <math> r=2 </math> und <math> k := k_1 </math> muss <math> k_2 = n - k </math> sein und man erhält als Spezialfall den Binomialkoeffizienten <math> {n \choose k} = {n \choose k_1, k_2} = \frac{n!}{k! (n-k)!} </math>.

Eigenschaften

Multinomialkoeffizienten sind stets ganzzahlig.

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

<math>{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}</math>.

Anwendungen und Interpretationen

Multinomialsatz

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)

<math>(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}</math>.

Hieraus folgt sofort:

<math>\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}.</math>

Multinomialverteilung

Anwendung finden jene Koeffizienten auch in der Multinomialverteilung

<math>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}

</math>,

einer Wahrscheinlichkeitsverteilung diskreter Zufallsvariablen.

Kombinatorische Deutungen

Objekte in Schachteln

Der Multinomialkoeffizient <math>\tbinom{n}{k_1,\dotsc,k_r}</math> gibt die Anzahl der Möglichkeiten an, <math>n</math> (unterscheidbare) Objekte in <math>r</math> Schachteln zu legen, wobei in die erste Schachtel genau <math>k_1</math> Objekte sollen, in die zweite Schachtel <math>k_2</math> 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 <math>n=32</math> Objekte handelt, die in <math>r=4</math> Schachteln aufzuteilen sind, wobei in die ersten drei Schachteln je <math>k_1=k_2=k_3=10</math> Objekte und in die vierte Schachtel <math>k_4=2</math> Objekte sollen, ist die Anzahl der Möglichkeiten durch folgenden Multinomialkoeffizienten gegeben:

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

</math>

Anordnung von Dingen

Der Multinomialkoeffizient <math>\tbinom{n}{k_1,\dotsc,k_r}</math> gibt außerdem die Anzahl der verschiedenen Anordnungen von <math>n</math> Objekten an, von denen <math>k_1, k_2, \ldots, k_r</math> gleich sind.<ref></ref>

Beispiel

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

Gesucht ist also die Anzahl der Möglichkeiten, elf Buchstaben (<math>n=11</math>) anzuordnen, wobei das "M" einmal (<math>k_1=1</math>), das "I" sowie das "S" jeweils viermal (<math>k_2=k_3=4</math>) und das "P" zweimal (<math>k_4=2</math>) vorkommt. Diese Anzahl beträgt

<math>\binom{11}{1,4,4,2}=\frac{11!}{1!\cdot4!\cdot4!\cdot2!}=34.650.</math>

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

Pascalsche Simplizes

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

Weblinks

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

Einzelnachweise

<references />