Mathematik: Wahrscheinlichkeitstheorie: DW: K2: Kombinatorische Wahrscheinlichkeitsrechnung

←  zurück   -  zum Inhaltsverzeichnis   -  weiter  →

K2: Kombinatorische Wahrscheinlichkeitsrechnung

Diskrete Wahrscheinlichkeitsrechnung

2. Symmetrische Wahrscheinlichkeitsräume

2.2 Kombinatorische Wahrscheinlichkeitsrechnung

Viele Probleme in der Wahrscheinlichkeitsrechnung können gelöst werden mit Hilfe des Symmetrieprinzips, also mit Laplace-Wahrscheinlichkeiten. Das Berechnen der Wahrscheinlichkeiten bedeutet dann das Zählen von Ergebnissen. Es ist klar, dass die Theorie des Zählens, die Kombinatorik, dabei ein wichtiges Hilfsmittel ist. In diesem Kapitel wiederholen wir einige wichtige Ergebnisse der Kombinatorik und wenden sie in der Wahrscheinlichkeitsrechnung an.

Es zeigt sich immer wieder, dass richtiges Zählen nicht so einfach ist, wie man oft denkt. Die erste Schwierigkeit stellt sich heraus, wenn es irgendeine Zerlegung der Situation gibt, und wir uns fragen, ob wir die Gesamtanzahl der Ergebnisse erhalten durch Addieren oder Multiplizieren der Anzahl der Elemente in den einzelnen Teilmengen. Die Antwort ist - selbstverständlich - es kommt auf die Art der Zerlegung an. Die beiden nächsten Sätze sind dabei entscheidend.

Satz 2.2.1 (spezieller Additionssatz)

Für die Vereinigung einer Kollektion disjunkter Mengen A₁,A₂,...,A_n gilt:

|A₁∪A₂∪...∪A_n| = |A₁|+|A₂|+...+|A_n|.

Wenn wir die Anzahl der Elemente jedes A_i gezählt haben und keine zwei der Mengen A_i haben gemeinsame Elemente, brauchen wir nicht aufs Neue zu zählen, um die Gesamtanzahl der Elemente zu bestimmen, aber wir können einfach die Anzahlen addieren. Also können wir sagen, wir sollen addieren, wenn die unterschiedlichen Möglichkeiten sich gegenseitig ausschließen, also entweder die eine oder die andere.

Der spezielle Additionssatz ist eine Quelle vieler Fehler. Mann übersieht leicht die Bedingung, dass die Mengen disjunkt sein müssen. Ist dass nicht der Fall, sollen wir den allgemeinen Additionssatz benutzen. Für zwei Mengen lautet er:

Satz 2.2.2 (allgemeiner Additionssatz)

Für zwei Mengen A und B gilt:

|A∪B| = |A| + |B| − |AB|

Die Gesamtanzahl der Elemente in A und B bekommen wir, indem wir die einzelnen Anzahlen addieren und die Summe verringern durch die Anzahl der gemeinsamen Elemente; die gemeinsamen Elemente würden sonst doppelt gezählt.

Der allgemeine Additionssatz kann, wie der übereinstimmende Additionssatz für Wahrscheinlichkeiten, erweitert werden für mehr als zwei Mengen. Wir zeigen nur ein Beispiel.

Beispiel 1 (NIEDERDORFF (Fortsetzung))

In NIEDERDORFF gibt es drei Theatervereine: A mit 42 Mitgliedern, B mit 30 Mitgliedern und C mit 57 Mitgliedern. Wie viele Niederdorffer sind Mitglied eines Theatervereins? Das sind nicht 42+30+57 Einwohner, denn 10 sind Mitglied von sowohl A als auch von B, 12 sind Mitglied von sowohl A als auch von C, 9 von sowohl B als auch von C und 8 sind sogar Mitglied von allen drei Vereinen. Also ist:

|A∪B∪C| = |A| + |B| + |C| − |AB| − |AC| − |BC| + |ABC| = 106.

Beispiel 2

Wir werfen dreimal einen ehrlichen Würfel. Für den Ergebnisraum S gilt #S = 6³ = 216. Es sei A das Ereignis, dass wir wenigstens einmal sechs werfen. Dann ist A = A₁∪A₂∪A₃, mit A_i das Ereignis der i. Wurf zeigt sechs (i=1,2,3). Weil die Ereignisse A₁, A₂ und A₃ nicht disjunkt sind, dürfen wir nicht den speziellen Additionssatz anwenden. Wohl aber können wir diesen Satz anwenden auf eine Partition von A. Dazu teilen wir A auf in disjunkte Teile:

$A=A_{1}A_{2}^{c}A_{3}^{c}\cup A_{1}^{c}A_{2}A_{3}^{c}\cup A_{1}^{c}A_{2}^{c}A_{3}\cup A_{1}A_{2}A_{3}^{c}\cup A_{1}A_{2}^{c}A_{3}\cup A_{1}^{c}A_{2}A_{3}\cup A_{1}A_{2}A_{3}$.

Dann folgt:

$|A|=|A_{1}A_{2}^{c}A_{3}^{c}|+|A_{1}^{c}A_{2}A_{3}^{c}|+|A_{1}^{c}A_{2}^{c}A_{3}|+|A_{1}A_{2}A_{3}^{c}|+|A_{1}A_{2}^{c}A_{3}|+|A_{1}^{c}A_{2}A_{3}|+|A_{1}A_{2}A_{3}|=$

$\,=25+25+25+5+5+5+1=91$.

Diese Antwort bekommen wir auch auf andere Art, wenn wir A auffassen als das Komplementärereignis, dass es keine Sechs gibt bei den drei Würfen. Dann ist also |A^c| = 5³ = 125 und

|A| = |S| − |A^c| = 216 − 125 = 91.

Auch können wir |A| bestimmen durch Anwendung des allgemeinen Additionssatzes:

$|A|=|A_{1}|+|A_{2}|+|A_{3}|-|A_{1}A_{2}|-|A_{1}A_{3}|-|A_{2}A_{3}|+|A_{1}A_{2}A_{3}|=$

$=36+36+36-6-6-6+1=91$.

Wenn ein Experiment daraus besteht, dass n Teilexperimente nach einander durchgeführt werden, und die Anzahl der möglichen Ergebnisse jedes Teilexperiments unabhängig von den Ergebnissen der sonstigen Teilexperimente sein soll, dann wird die Gesamtanzahl der möglichen Ergebnisse berechnet als Produkt der einzelnen Anzahlen. Wir sollen multiplizieren, wenn die unterschiedlichen Möglichkeiten zur gleichen Zeit eintreten sollen, also die Eine und die Andere.

Es wäre auch möglich, dass wir zwar nicht jede Möglichkeit des einen Experiments kombinieren können mit allen Möglichkeiten eines anderen, aber wohl immer mit einer gleichen Anzahl Möglichkeiten des anderen Experiments. Auch dann bekommen wir die Gesamtanzahl der Möglichkeiten durch Multiplizieren. Der Multiplikationssatz besagt:

Satz 2.2.3 (Multiplikationssatz)

Wenn jeder der n₁ Ergebnisse eines ersten Experiments kombiniert werden kann mit einer gleichen Anzahl Ergebnisse n₂ eines zweites Experiments und jede dieser Kombinationen wieder mit einer gleichen Anzahl Ergebnisse n₃ eines dritten usw., dann ist die Gesamtzahl der Ergebnisse das Produkt n₁× n₂× n₃×... dieser einzelne Anzahlen.

Eine Anwendung des Multiplikationssatzes ist:

Satz 2.2.4

Laut des Multiplikationssatzes gilt für das Kartesische Produkt der Mengen A₁, A₂, ...,A_n:

|A₁× A₂×...× A_n| = |A₁|× |A₂|× ... × |A_n|.

Beispiel 3

Auf einer Menükarte stehen 3 Vorspeisen, 5 Hauptgerichte und 4 Nachspeisen. Wie viele 3-Gänge-Menüs von der Karte können wir zusammensetzen? Der Multiplikationssatz besagt, dass es 3 × 5 × 4 = 60 mögliche Menüs gibt.

Beispiel 4

Jede der 3 Vorspeisen auf die Menükarte lässt sich kombinieren mit 4 der 5 Hauptgerichte und jede dieser Kombinationen mit nur 2 der 4 Nachspeisen. Der Multiplikationssatz besagt, dass dann noch 3×4×2 = 24 3-Gänge-Menüs möglich sind.

Der Multiplikationssatz ermöglicht es zu bestimmen, wie viel unterschiedene Anordnungen einer Anzahl unterscheidbarer Objekte es gibt. Eine Anordnung heißt Permutation und die Anzahl der Permutationen von n Objekten ist, wie der Produktsatz zeigt, gleich n! (n Fakultät, das Produkt der Zahlen 1 bis n).

Definition 2.2.1

Eine Permutation von n unterscheidbare Objekten ist eine Anordnung dieser Objekte.

Beispiel 5

Die Permutationen der Ziffern 1, 2 und 3 sind: 123, 132, 213, 231, 312 und 321.

Satz 2.2.5

Es gibt n! Permutationen von n verschiedenen Objekten.

Beispiel 5 (Erweiterung)

Tatsächlich gibt es 3! = 6 Permutationen der 3 Ziffern 1, 2 und 3.

Stichproben

Wir besprechen nun ein klassisches und charakteristisches kombinatorisches Problem:

Wie viel verschiedene Ergebnisse gibt es, wenn man aus einer Menge von n unterscheidbaren Elementen k mal eines auswählt?

Die Antwort hängt einerseits von der Art und Weise ab, wie man die Ziehungen einrichtet, und zwar, ob man ohne oder mit Zurücklegen vorgeht, und andererseits von der Art, wie man das Ergebnis betrachtet, namentlich geordnet oder ungeordnet. Im Bild 2.1 wird dies schematisch gezeigt. Zuerst zeigen wir einige Beispiele der unterschiedlichen Möglichkeiten.

Beispiel 6

Aus den 100 Mitgliedern des Vereins KOMBI soll ein dreiköpfiger Vorstand gewählt werden. Der Vorstand besteht aus dem Vorsitzenden, dem Schatzmeister und dem Schriftführer. Eine Person kann nur einen Posten besetzen. Die 3 Ziehungen werden also ohne Zurücklegen durchgeführt und das Ergebnis soll geordnet sein. Wie viele Vorstände sind möglich? Wir haben 100 Möglichkeiten, den Vorsitzenden zu wählen, danach noch 99 Möglichkeiten für den Schatzmeister und schließlich noch 98 Möglichkeiten für den Schriftführer. Also gibt es insgesamt 100×99×98 = 100!/(100-3)! verschiedene Vorstände. Einen möglichen Vorstand beschreiben wir durch Auflisten der drei Namen der Vorstandsmitglieder in der Reihenfolge ihrer Funktionen. Eine derartige Anordnung heißt eine Variation.

Beispiel 7

Für das Jubiläumsfest nächstes Jahr braucht KOMBI ein Festkomitee von 3 Mitgliedern. Die Mitglieder des Festkomitees haben keine unterschiedlichen Aufgaben. Deshalb ziehen wir zwar wieder ohne Zurücklegen, aber das Ergebnis soll ungeordnet sein. Gleich wie im vorigen Beispiel können wir auf 100!/97! eine geordnete Dreiergruppe wählen; die Anordnung ist aber in diesem Fall nicht erforderlich, so dass jede der 3! Anordnungen von 3 Personen das gleiche Komitee ergibt. Es gibt also

${\frac {100!}{3!\ 97!}}={100 \choose 3}$

mögliche Komitees. Ein mögliches Komitee beschreiben wir durch Auflisten der drei Namen der Mitglieder des Komitees, die Reihenfolge der Namen hat keine Bedeutung. Eine derartige Anordnung heißt eine Kombination.

Beispiel 8

Bei KOMBI sollen 3 verschiedene Arbeiten gemacht werden. Der Vorstand bittet die Mitglieder um Freiwillige. Weil ein Mitglied auch mehr als eine Arbeit machen kann, sollen wir nun ziehen mit Zurücklegen. Das Ergebnis soll aber geordnet sein, weil die Arbeiten unterschiedlich sind. Wir wählen dreimal nacheinander ein Mitglied aus allen 100 für jede der Arbeiten. Es gibt also 100×100×100 = 100³ Möglichkeiten. Eine Möglichkeit bezeichnen wir durch die Arbeitsaufgabe und den gewählten Namen. Die erwähnten Namen brauchen nun nicht verschieden zu sein. Eine Möglichkeit heißt hier eine Variation mit Wiederholung.

Beispiel 9

Für das Jubiläumsfest von KOMBI müssen 3 Bierfässer gestrichen werden. Das Festkomitee bittet die Mitglieder um Freiwillige. Diesmal sind die Arbeiten nicht unterschieden, also soll das Ergebnis nicht geordnet sein. Wir wollen aber wieder mit Zurücklegen ziehen. Wir können eine Möglichkeit eindeutig beschreiben, damit wir für jedes der 100 Mitglieder auflisten, wie viele Bierfässer er streichen soll. Wir machen dies schematisch: Wir bezeichnen ein Bierfass mit einer o und platzieren die 3 Bierfässer vor den aufgereihten Mitgliedern. Zwischen die Mitglieder setzen wir einen Strich |. Eine Möglichkeit wäre dann:

1

2

3

4

5

$\cdots$

100

$\mid$

$\mid$

$\circ$

$\mid$

$\mid$

$\circ \circ$

$\mid$

$\cdots$

$\mid$

Sie bedeutet, dass Mitglied 1 kein Fass streicht, wie auch Mitglied 2. Nummer 3 streicht ein Fass, Nummer 4 wieder keins. Mitglied 5 streicht 2 Bierfässer und die Übrigen keins. Jede Möglichkeit kann beschrieben werden als eine Folge von 3 Nullen (die Bierfässer) und 99 (= 100 − 1) Einsen (die Separationsstriche). Es gibt

${100-1+3 \choose 3}={102 \choose 3}$

solche Folgen. Hier heißt eine Möglichkeit eine Kombination mit Wiederholung.

Urnenmodell

Die oben erwähnten Beispiele beschreiben wir oft mit einem Urnenmodell. Wir zogen drie Mal aus einer Urne mit 100 nummerierten Kugeln, mal mit Zurücklegen und mal ohne. In zwei Fällen betrachteten wir geordnete Dreiergruppen als Ergebnis, in zwei anderen Fällen ungeordnete Dreiergruppen. Im nächsten Bild ist dies schematisch dargestellt.

Bild 2.1. Ziehungen aus einer Urne.

In den Beispielen begegneten wir den unten stehenden Begriffen und Sätzen.

Definition 2.2.2

Eine Variation von k aus n (unterscheidbare Objekte) ist das Ergebnis einer geordneten Ziehung ohne Zurücklegen von k dieser n Objekte.

Satz 2.2.6

Die Anzahl der Variationen von k aus n ist

${\frac {n!}{(n-k)!}}.$

Definition 2.2.3

Eine Kombination von k aus n (unterscheidbare Objekte) ist das Ergebnis einer ungeordneten Ziehung ohne Zurücklegen von k dieser n Objekte.

Satz 2.2.7

Die Anzahl der Kombinationen von k aus n ist:

${n \choose k}={\frac {n!}{k!(n-k)!}}$.

Definition 2.2.4

Eine Variation mit Wiederholung von k aus n (unterscheidbare Objekte) ist das Ergebnis einer geordneten Ziehung mit Zurücklegen von k dieser n Objekte.

Satz 2.2.8

Die Anzahl der Variationen mit Wiederholung von k aus n ist:

$n^{k}\!.$

Definition 2.2.5

Eine Kombination mit Wiederholung von k aus n (unterscheidbare Objekte) ist das Ergebnis einer ungeordneten Ziehung mit Zurücklegen von k dieser n Objekte.

Satz 2.2.9

Die Anzahl der Kombinationen mit Wiederholung von k aus n ist:

${n-1+k \choose k}$.

Untenstehendes Schema gibt eine Übersicht der Ziehung von k Objekten aus einer Menge (Urne) mit n unterscheidbaren Objekten (Kugeln).

Ergebnis	Ziehung
	ohne Zurücklegen	mit Zurücklegen
geordnet	Variation	Variation mit Wiederholung
ungeordnet	Kombination	Kombination mit Wiederholung

Im nächsten Beispiel ist der Fall n=4 und k=3 ganz ausgeschrieben.

Beispiel 10

123 132 213 231 312 321	124 142 214 241 412 421	134 143 314 341 413 431	234 243 324 342 423 432|	24 Variationen (Folgen) 4 Kombinationen (Kästchen)									64 Variationen mit Wiederholung (Folgen) 20 Kombinationen mit Wiederholung (Kästchen)
112 121 211	113 131 311	114 141 411	221 212 122	223 232 322	224 242 422	331 313 133	332 323 233	334 343 433	441 414 144	442 424 244	443 434 344
111	222	333	444

Zufallsstichprobe

Im Urnenmodell denken wir uns die Ziehungen immer zufällig, beliebig ausgeführt, d.h. bei jeder Ziehung ist die Wahrscheinlichkeit gewählt zu werden für alle restlichen Kugeln gleich. Praktisch gestalten wir eine Zufallsstichprobe so, dass wir die Urne tüchtig schütteln und dann zufällig, ohne hinzuschauen, eine Kugel herausnehmen.

Definition 2.2.6

Eine Zufallsstichprobe aus einer Grundgesamtheit ist ein symmetrisches Experiment mit der Grundgesamtheit als Ergebnisraum.

Zufallsstichproben führen in den Fällen von Variationen, Kombinationen und Variationen mit Wiederholung zu symmetrischen Wahrscheinlichkeitsräumen. Wir werden erst in einem späteren Kapitel den Grund dafür richtig verstehen, nachdem wir den Begriff der bedingten Wahrscheinlichkeit eingeführt haben. Vorläufig, und das ist auch im Einklang mit diesem Kapitel, werden wir die Symmetrie der Situation benutzen. Im Fall von Kombinationen mit Wiederholung gibt es keine Symmetrie trotz zufälligen Ziehens!

Satz 2.2.10

Eine Zufallsstichprobe von k Ziehungen aus einer Menge von n unterscheidbaren Elemente führt zu einem symmetrischen Wahrscheinlichkeitsraum in den Fällen:

(a) Ziehen ohne Zurücklegen und geordnete Ergebnisse:

S = {Variationen},

$|S|={\frac {n!}{(n-k)!}}$;

(b) Ziehen ohne Zurücklegen und ungeordnete Ergebnisse:

S = {Kombinationen},

$|S|={n \choose k}={\frac {n!}{k!(n-k)!}}$;

(c) Ziehen mit Zurücklegen und geordnete Ergebnisse:

S = {Variationen mit Wiederholung},

$\!\;|S|=n^{k}$;

Der Wahrscheinlichkeitsraum ist nicht symmetrisch im Fall:

(d) Ziehen mit Zurücklegen und ungeordnete Ergebnisse.

Beweis

Die Fälle a, b und c folgen wegen der Symmetrie in den Ergebnissen. Im Fall d betrachten wir die Ergebnisse als Ereignisse im Wahrscheinlichkeitsraum der Variationen mit Wiederholung. Das Ergebnis (k,0,...,0), d.h. k mal ist das Objekt mit Nummer 1 gezogen worden, stimmt überein mit dem Ereignis {(1,1,...,1)} bei den Variationen mit Wiederholung und hat also die Eintrittswahrscheinlichkeit 1/n^k. Das Ergebnis (k-1,1,0,...,0), d.h. k-1 Mal ist das Objekt mit Nummer 1 gezogen worden und 1 Mal die Nummer 2, stimmt überein mit dem Ereignis {(1,1,...,1,2),(1,1,...,1,2,1),...,(2,1,...,1)} und enthält k Elemente, und zwar alle Variationen mit Wiederholung mit k-1 mal 1 und 1 mal 2. Die Wahrscheinlichkeit zum Eintreten dieses Ereignisses ist k/n^k.

Anwendungen

Beispiel 11

Wir ziehen zufällig hintereinander (also als geordnetes Ergebnis) ohne Zurücklegen k Kugeln aus einer Urne mit n nummerierten Kugeln (Nummern 1 bis n). Was ist die Wahrscheinlichkeit, dass die erste gezogene Kugel die Nummer i hat? Die Ergebnisse sind Variationen und der Wahrscheinlichkeitsraum ist symmetrisch; |S| = n!/(n–k)!. Das Ereignis, dass die erste Kugel die Nummer i hat, nennen wir A; A enthält alle Variationen, die an der 1. Stelle die Nummer i aufweisen. Die Ergebnisse in A können wir bekommen durch als erste Kugel die Nummer i zu nehmen und demnächsten noch k-1 andere; also noch eine Variation von k–1 aus n–1. A enthält also (n–1)!/(n–k)! Ergebnisse. Die erlangte Wahrscheinlichkeit ist: P(A) = |A|/|S| = 1/n, was uns bestimmt nicht erstaunen wird.

Wie groß ist die Wahrscheinlichkeit, dass die zweite gezogene Kugel die Nummer i hat? Auf gleicher Weise finden wir dass dieses Ereignis, wir nennen es B, die Variationen enthält mit an der 2. Stelle die Nummer i. Das sind gleich viel wie in A: stelle die Nummer i schon an der 2. Stelle und ergänze die übrige Plätze mit eine Variation von k–1 aus n–1. Also finden wir: P(B) = P(A) = 1/n.

Die Wahrscheinlichkeit, dass die j. gezogene Kugel die Nummer i hat, beträgt, wie wir analog berechnen, immer 1/n.

Die Wahrscheinlichkeit, dass die Kugel mit der Nummer i (überhaupt) gezogen wird, ist:

P("Nummer i") = P("Nummer i als 1." oder "als 2." oder ... oder "als k.") =

= P("als 1.") + P("als 2.") + ... + P("als k.") = k/n.

Beispiel 12

Wir ziehen beliebig ohne auf die Reihenfolge zu achten und ohne Zurücklegen k Kugeln aus einer Urne mit n nummerierte Kugeln (Nummern 1 bis n). Die Ergebnisse sind Kombinationen und der Wahrscheinlichkeitsraum ist symmetrisch:

$|S|={n \choose k}$.

Die Wahrscheinlichkeit dass der Kugel mit der Nummer i gezogen wird, ist:

P("Nummer i") = ${\frac {n-1 \choose k-1}{n \choose k}}={\frac {k}{n}}$,

denn das erlangte Ereignis enthält die Kombinationen worin die Nummer i sich befindet. Wir bekommen diese Kombinationen durch zuerst die Kugel mit der Nummer i zu nehmen und die Kombination zu ergänzen mit einer Kombination von k-1 aus die übrige n-1. Bemerke dass diese Wahrscheinlichkeit derselbe ist wie im vorigen Beispiel.

Beispiel 13

Wir ziehen beliebig 10 Karten aus einem gut gemischten Spiel. Wir ziehen ohne Zurücklegen und ohne auf die Reihenfolge zu achten. Die Ergebnisse sind Kombinationen und der Wahrscheinlichkeitsraum ist symmetrisch. Was ist die Wahrscheinlichkeit bei der gezogenen 10 Karten sind 2 Asse und 3 Könige? In einem Schema sieht es so aus:

	As	König	Rest	insgesamt
Grundmasse	4	4	44	52
Stichprobe	2	3	5	10

Insgesamt gibt es ${\tbinom {52}{10}}$ mögliche Ergebnisse (Kombinationen) und das erwähnte Ereignis kann auf ${\tbinom {4}{2}}{\tbinom {4}{3}}{\tbinom {44}{5}}$ Weisen entstehen. Die erlangte Wahrscheinlichkeit ist also:

${\frac {{4 \choose 2}{4 \choose 3}{44 \choose 5}}{52 \choose 10}}=0{,}0016$.

Beispiel 14 ("matching problem")

Auf einer Party gibt es n Ehepaare. Zum nächsten Tanz wird jedem Ehemann beliebig eine Frau als Tanzpartner zugeteilt. Was ist die Wahrscheinlichkeit p_n dass kein Ehepaar zusammen tanzt?

Bezeichne A_i als das Ereignis dass der Mann mit dem Nummer i seine eigene Frau zugeteilt bekommt. Die erlangte Wahrscheinlichkeit ist dann:

$p_{n}=P({\overline {A_{1}}}\cap {\overline {A_{2}}}\cap ...\cap {\overline {A_{n}}})=P({\overline {A_{1}\cup A_{2}\cup ...\cup A_{n}}})=1-P(A_{1}\cup A_{2}\cup ...\cup A_{n})=$

$=1-\left\{\sum P(A_{i})-\sum P(A_{i}A_{j})+\sum P(A_{i}A_{j}A_{k})-....\pm P(A_{1}A_{2}...A_{n})\right\}=$

$=1-{\tbinom {n}{1}}n+{\tbinom {n}{2}}n(n-1)-{\tbinom {n}{3}}n(n-1)(n-2)+...\pm {\tbinom {n}{n}}n!=$

$=1-\{1!-2!+...\pm n!\}\approx {\frac {1}{e}}=0{,}368$.

Die Wahrscheinlichkeit p_n ändert sich kaum mehr ab n = 6 à 7; 1/e ist dann schon eine gute Annäherung.

In einer Tabelle:

$n$	1	2	3	4	5	6	7	...
$p_{n}$	0	0,500	0,333	0,375	0,367	0,365	0,365	...

Dieses Problem begegnet man auch in andere Formen:

• Eine Sekretärin tippt n Briefe und die zugehörige Umschläge, und steckt die Briefe beliebig in einem Umschlag.
• Nach einem Abend trinken, verlassen n Männer die Kneipe, und setzen beliebig einen Hut auf.

Das Ziehen ohne zurücklegen und ohne auf die Reihenfolge zu achten von k Kugeln aus einer Urne mit n Kugeln, können wir auch beschreiben als das Aufteilen der n Kugeln in der Urne in zwei Gruppen mit Größen k und n–k, nämlich die k Gezogene und die n–k nicht Gezogene. Wir verallgemeinern dieses Experiment damit wir die n Kugeln aufteilen in m Gruppen mit Größen n₁,n₂,...,n_m, wofür also gilt: n₁+ n₂+...+ n_m = n. Wir veranstalten ein solcher Aufteilung durch von eine Anordnung der n Kugeln, wovon es n! Verschiedene gibt, die erste n₁in der Gruppe 1 einzuteilen, die nächste n₂ in der Gruppe 2, usw. Weil die Anordnung der n₁ Kugeln in der Gruppe 1, es gibt n₁! Anordnungen, keine Bedeutung hat, und gleichfalls für die anderen Gruppen, gibt es insgesamt:

${\frac {n!}{n_{1}!n_{2}!\cdots n_{m}!}}$

Aufteilungen in m Gruppen. Man nennt dieser Anzahl der Multinomialkoeffizient.

Definition 2.2.7

Der Multinomialkoeffizient:

${n \choose n_{1},n_{2},...,n_{m}}$

ist der Anzahl Möglichkeiten um n unterschiedliche Objekte aufzuteilen in m Gruppen mit Größen n₁,n₂,...,n_m, wofür gilt: n₁+ n₂+...+ n_m = n.

Satz 2.2.11

Für den Multinomialkoeffizient gilt:

${n \choose n_{1},n_{2},...,n_{m}}={\frac {n!}{n_{1}!n_{2}!\cdots n_{m}!}}=$

$={n \choose n_{1}}{n-n_{1} \choose n_{2}}{n-n_{1}-n_{2} \choose n_{3}}\cdots {n-n_{1}-\dots -n_{m-2} \choose n_{m-1}}{n_{m} \choose n_{m}}$

Die letzte Form der Multinomialkoeffizient in diesem Satz zeigt dass wir die richtige Anzahl auch bekommen, wenn wir die Gruppen nach einander füllen mit der erlangte Anzahl Kugeln.

Beispiel 15

Wie viel Möglichkeiten gibt es 30 Personen aufzuteilen in 4 Gruppen mit bzw. 6, 7, 8 und 9 Personen? Die Anzahl ist

${30 \choose 6,7,8,9}={\frac {30!}{6!7!8!9!}}={30 \choose 6}{24 \choose 7}{17 \choose 8}{9 \choose 9}$

Die zweite Vorstellung zeigt wie die 4 Gruppen nach einander gefüllt werden. Wir können dafür auch schreiben:

${30 \choose 24}{24 \choose 17}{17 \choose 9}{9 \choose 0},$

womit wir zeigen die erwünschte Aufteilung zu bewirken, damit wir immer den restlichen Personen wegnehmen.