Multinomialkoeffizient


Multinomialkoeffizient

Der Multinomialkoeffizient oder auch Polynomialkoeffizient ist eine Erweiterung des Binomialkoeffizienten. Für nichtnegative ganze Zahlen k1,...,kr und n: = k1 + ... + kr 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.

Inhaltsverzeichnis

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 k1 Objekte sollen, in die zweite Schachtel k2 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 k1 = k2 = k3 = 10 Objekte und in die vierte Schachtel k4 = 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 k1-mal (ununterscheidbar) vorkommt, das zweite k2-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") k1 = 1-mal, das zweite ("I") k2 = 4-mal (ununterscheidbar) vorkommt, das dritte ("S") ebenso und das vierte ("P") k4 = 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


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Polynomialkoeffizient — Der Polynomialkoeffizient (oder Multinomialkoeffizient) ist eine Erweiterung des Binomialkoeffizienten. Für nichtnegative ganze Zahlen n,k1,...,kr mit k1 + ... + kr = n ist er definiert als Dieser ist stets eine natürliche Zahl. Dabei ist x! die… …   Deutsch Wikipedia

  • Formel von Faà di Bruno — Die Formel von Faà di Bruno ist eine Formel der Analysis, die vom italienischen Mathematiker Francesco Faà di Bruno (1825–1888) publiziert wurde. Mit ihr lassen sich höhere Ableitungen von komponierten Funktionen bestimmen, sie verallgemeinert… …   Deutsch Wikipedia

  • Multinomialverteilung — Die Multinomialverteilung oder Polynomialverteilung ist eine diskrete Wahrscheinlichkeitsverteilung. Man kann sie als multivariate Verallgemeinerung der Binomialverteilung auffassen. Definition und Modell Seien und mit p1 + ... + pk = 1. Dann ist …   Deutsch Wikipedia

  • Multinomialtheorem — In der Mathematik stellt das Multinomialtheorem (auch Multinomialformel oder Multinomialsatz) oder Polynomialtheorem eine Verallgemeinerung der Binomischen Formel auf die Summe beliebig vieler Koeffizienten dar, indem es die Binomialkoeffizienten …   Deutsch Wikipedia