Multinomial-Koeffizienten

Die Fakultäts-Brüche, die wir bei der Untersuchung des vierten Urnenmodells entdeckt haben, tauchen in kombinatorischen Überlegungen an verschiedenen Stellen auf. Wir definieren hierzu:

Definition (Multinomialkoeffizienten)

Für n ≥ 0, r ≥ 1 und k₁, …, k_r  ∈  { 0, …, n } mit k₁ + … + k_r = n setzen wir

$( \binom{n}{k_{1}, …, k_{r}} )$ _mult = ^n!_{k₁! … k_r!}(Multinomialkoeffizient k₁, …, k_r aus n)

Für r > 1 lassen wir den Zusatz „mult“ weg, da dann durch die Kommata keine Verwechslung mit den Binomialkoeffizienten möglich ist. Wir erlauben den Fall r = 1 aus technischen Gründen, um Induktionen zu vereinfachen.

Die Multinomialkoeffizienten sind uns oben mit n = k und r = n begegnet. Wir ändern die Namen der Variablen, um eine Analogie zur üblichen Form „k aus n“ der Binomialkoeffizienten zu erreichen. In der Tat verallgemeinern die Multinomialkoeffizienten die Binomialkoeffizienten, denn für r = 2 und k₁ + k₂ = n gilt

$( \binom{n}{k_{1}, k_{2}} )$ = $( \binom{n}{k_{1}} )$ = $( \binom{n}{k_{2}} )$ .

Um die kombinatorische Bedeutung der Multinomialkoeffizienten weiter zu klären, ist folgender Zerlegungsbegriff nützlich:

Definition (geordnete Zerlegung einer Menge)

Seien M endlich und r ≥ 1. Ein Tupel (M₁, …, M_r) von Teilmengen von M heißt eine (geordnete) Zerlegung von M (in r nummerierte Teile), falls gilt:

(i)	M_i ∩ M_j = ∅ für alle 1 ≤ i < j ≤ r,

(ii)	M₁ ∪ … ∪ M_r = M.

Ist k_i = |M_i| für alle i, so heißt die Zerlegung eine (k₁, …, k_r)-Zerlegung von M.

Für jede (k₁, …, k_r)-Zerlegung von M gilt k₁ + … + k_r = |M|. Dabei ist k_i = 0 möglich, da einzelne Teile M_i der Zerlegung leer sein können.

Beispiele

Sei M = { 1, …, 8 }. Dann ist

({ 1, 2, 4 }, { 3, 5, 6, 7, 8 })	eine (3, 5)-Zerlegung von M,
({ 1, 2, 3 }, { }, { 4, 5, 6, 7, 8 }, { })	eine (3, 0, 5, 0)-Zerlegung von M,
( { }, …, { }, M)	eine (0, …, 0, 8)-Zerlegung von M.

Wir sammeln nun Zerlegungen eines bestimmten Typs auf:

Definition (Zerlegungen mit vorgegebener Größe)

Sei M eine endliche Menge, und sei n = |M|. Weiter seien r ≥ 1 und k₁, …, k_r  ∈  { 0, …, n } mit k₁ + … + k_r = n. Dann setzen wir

[ M ]^{k₁, …, k_r} = { (M₁, …, M_r) | (M₁, …, M_r) ist (k₁, …, k_r)-Zerlegung von M }.

Die Multinomialkoeffizienten geben die Mächtigkeiten dieser Zerlegungsmengen an:

Satz (Multinomialkoeffizienten und Zerlegungen)

Mit den Objekten wie in der letzten Definition gilt:

|[ M ]^{k₁, …, k_r}| = $( \binom{n}{k_{1}, …, k_{r}} )$ .

Der folgende Beweis des Satzes ist eine formalere Version der oben im lockeren kombinatorischen Jargon durchgeführten Zählung für T₃. Wer kein Bedürfnis danach verspürt, kann den Beweis überschlagen.

Beweis

Wir zeigen die Aussage durch Induktion nach r ≥ 1.

Induktionsanfang r = 1:

Für r = 1 ist k₁ = |M| = n und (M) die eindeutige (k₁)-Zerlegung von M. Der (degenerierte) Multinomialkoeffizient berechnet sich zu

$( \binom{n}{k_{1}} )$ _mult = $( \binom{n}{n} )$ _mult = ^n!_n! = 1 = |[ M ]^k₁|.

Induktionsschritt von r nach r + 1:

Eine (k₁, …, k_r + 1)-Zerlegung von M ist bestimmt durch:

(a)	ein M_r + 1 ⊆ M mit \|M_r + 1\| = k_r + 1,

(b)	eine (k₁, …, k_r)-Zerlegung von M − M_r + 1.

Da es genau „k_r + 1 aus n“ k_r + 1-elementige Teilmengen von M gibt, ergibt sich

\|[ M ]^{k₁, …, k_r + 1}\|	= $( \binom{n}{k_{r + 1}} )$ \|[ M ]^{k₁, …, k_r}\|
	=_I. V. $( \binom{n}{k_{r + 1}} )$ $( \binom{n - k_{r + 1}}{k_{1}, …, k_{r}} )$
	= ^n!_{k_r + 1! (n − k_r + 1)!} ^{(n − k_r + 1)!}_{k₁! · … · k_r!}
	= $( \binom{n}{k_{1}, …, k_{r + 1}} )$ .

Wir diskutieren nun noch verschiedene Interpretationen dieses Ergebnisses. Hierzu sei

z = $( \binom{n}{k_{1}, …, k_{r}} )$ mit fest gewählten n ≥ 0, r ≥ 1, k₁ + … + k_r = n.

Der Satz liefert:

Interpretation I der Multinomialkoeffizienten

Die Zahl z ist die Anzahl der Möglichkeiten, die Zahlen 1, …, n so in nummerierte oder benannte Teile M₁, … M_r aufzuteilen, dass die Teile der Reihe nach die vorgegebenen Größen k₁, …, k_r besitzen.

Den Binomialkoeffizienten entspricht eine Aufteilung in zwei benannte Teile. Bei den Urnenmodellen betrachten wir die Aufteilung „gezogen/nicht gezogen“ bzw. „ausgewählt/nicht ausgewählt“.

Beispiel

Bei drei Spielern A, B, C und einem Skat mit zwei Karten ist

$( \binom{32}{10, 10, 10, 2} )$ = ^32!_{10! 10! 10! 2!} = 2753294408504640

die Anzahl der Skatspiele.

Sehr nützlich ist folgende uns schon bekannte Interpretation:

Interpretation II der Multinomialkoeffizienten

Die Zahl z ist die Anzahl der n-Tupel mit Einträgen in { 1, …, r }, die genau k₁ oft den Eintrag 1, genau k₂ oft den Eintrag 2, …, genau k_r oft den Eintrag r besitzen.

Zur Übersetzung der beiden Interpretationen ordnen wir einer (k₁, …, k_r)-Zerlegung (M₁, …, M_r) von { 1, …, n } das Lokalisierungs-Tupel (a₁, …, a_n) mit Einträgen in { 1, … r } zu vermöge

a_m = „das eindeutige i mit m  ∈  M_i“ für alle 1 ≤ m ≤ n.

Diese Zuordnung definiert eine Bijektion zwischen [ { 1, …, n } ]^{k₁, …, k_r} und den in der Interpretation genannten n-Tupeln mit Einträgen in { 1, …, r }. Lesen wir das Tupel (a₁, …, a_n) als Funktion auf { 1, …, n }, so liefert diese Funktion für alle m die Antwort auf die Frage: „In welchem Teil der Zerlegung befindet sich m?“

Eine anschauliche Variante der zweiten Interpretation ist:

Interpretation III der Multinomialkoeffizienten

Die Zahl z ist die Anzahl der möglichen Färbungen der Zahlen 1, …, n mit Farben 1, …, r derart, dass für jede Farbe i genau k_i Zahlen mit der Farbe i gefärbt werden.

Die Zerlegung (M₁, M₂, M₃) von M = { 1, …, 8 } mit

M₁ = { 3, 5, 6 }, M₂ = { 1, 4 }, M₃ = { 2, 7, 8 }

Darstellung der Zerlegung als Tupel (2, 3, 1, 2, 1, 1, 3, 3)  ∈  T₁(8, 3) (Interpretation II) und als Färbung von { 1, …, 8 } mit drei Farben blau, gelb, grün (Interpretation 3)