Multinomialkoeffizient - LinkFang.de





Multinomialkoeffizient


Der Multinomialkoeffizient oder auch Polynomialkoeffizient ist eine Erweiterung 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]

Dabei ist [math] x! [/math] die Fakultät von [math] x [/math].

Eigenschaften

Die Multinomialkoeffizienten sind stets ganze Zahlen.

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

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

Anwendungen und Interpretationen

Multinomialsatz

In Verallgemeinerung des binomischen Satzes gilt das sogenannte 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].

Aus dem Multinomialsatz 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 Kisten

Der Multinomialkoeffizient [math]\tbinom{n}{k_1,\dotsc,k_r}[/math] gibt die Anzahl der Möglichkeiten an, [math]n[/math] 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, 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 [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] Dingen an, wobei das erste [math]k_1[/math]-mal (ununterscheidbar) vorkommt, das zweite [math]k_2[/math]-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") [math]k_1=1[/math]-mal, das zweite ("I") [math]k_2=4[/math]-mal (ununterscheidbar) vorkommt, das dritte ("S") ebenso und das vierte ("P") [math]k_4=2[/math]-mal. Das ist also der Multinomialkoeffizient

[math]\binom{11}{1,4,4,2}=\frac{11!}{1!\cdot4!\cdot4!\cdot2!}=34.650[/math]

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 Binominalkoeffizienten 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


Kategorien: Kombinatorik

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Multinomialkoeffizient (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.