Die Kombination (Zusammenstellung) zählt die möglichen Zusammenstellungen von Elementen ohne Ansehen der Reihenfolge. Zusammenstellungen mit gleichen Elementen werden nur einmal gezählt.
Aufgabe:
Aus N Elementen der Grundmenge werden k Elemente ausgewählt. Die Reihenfolge ist unwichtig.
Fragestellung:
Wie viele Zusammenstellungen (Kombinationen) von k Elementen aus der Grundmenge gibt es?
Kombination ohne Wiederholung
Geltungsbereich:
1. Alle N Elemente der Ausgangsmenge sind unterscheidbar.
2. Es werden k Elemente ausgewählt.
3. Die Reihenfolge ist unwichtig.
4. Elemente können nicht mehrfach ausgewählt werden.
Fragestellung:
Wie viele unterschiedliche Kombinationen von k aus N Elementen gibt es?
\( C_N^k = \frac{ {N!} }{ {(N - k)! \cdot k!} } \) Gl. 75
Gl. 75 berücksichtigt, dass die Anzahl aller möglichen Anordnungen (Permutation) um die Zahl der Anordnungen mit gleichen Elementen vermindert wird. Dies ist wieder anhand der Baumstruktur nachvollziehbar.
Erläuterung
Insgesamt sind von N Elementen N! prinzipiell verschiedene Anordnungen möglich. Nun werden aber nur k Elemente gezogen. Es gibt daher (N-k)! Permutationen der Restmenge und k! Permutationen der gezogenen Menge. Die Permutationen der Restmenge sind uninteressant und auch die Reihenfolge der Elemente der gezogenen Menge ist uninteressant. Daher reduziert sich die Gesamtzahl von Permutationen um die Anzahlen von Permutationen der Restmenge und der gezogenen Menge.
Beispiel:
Beim Gewinnspiel 6 aus 49 werden 6 Kugeln aus 49 durchnummerierten Kugeln gezogen. Keine der gezogenen Kugeln wird in das Spielgerät zurückgelegt. Wie groß ist die Wahrscheinlichkeit für einen Hauptgewinn?
Lösung:
C = 49!/(43!·6!) = 13.983.816. Die Wahrscheinlichkeit liegt also unter 10-5 %.
Kombination mit Wiederholung
Geltungsbereich:
1. Alle N Elemente der Ausgangsmenge sind unterscheidbar.
2. Es werden k Elemente ausgewählt.
3. Die Reihenfolge ist unwichtig.
4. Elemente können mehrfach ausgewählt werden.
Fragestellung:
Wie viele unterschiedliche Kombinationen gibt es?
\( C_N^k = \frac{ {(N + k - 1)!} }{ {(N - 1)! \cdot k!} } \) Gl. 76
Die Baumstruktur zeigt die Auswahl von k = 2 Elementen aus N = 3 Elementen:
Erläuterung
In einer Urne befinden sich N unterscheidbare Elemente. Es werden k Elemente eins nach dem anderen gezogen. Nach der Ziehung wird der Wert des Elementes notiert und in die Urne zurückgelegt, dann wird das nächste Element gezogen, dessen Wert notiert und wieder zurückgelegt. Dies wird für jedes der k Elemente getan. Indem nach jeder Ziehung das gezogene Element sofort zurückgelegt wird, können einzelne Elemente mehrfach gezogen werden.
Weil Elemente mehrfach gezogen werden können, erhöht sich die Anzahl der prinzipiell möglichen Permutationen auf (N+k-1). (k-1) weil es für k=1 keine Fallunterscheidung zwischen Kombination mit und ohne Wiederholung geben darf.
Die Anzahl der Permutationen der Restmenge beträgt (N-1)!, da stets nur ein Element aus der Urne entnommen wird. In der gezogenen Menge gibt es wieder k! Permutationen, da die Reihenfolge (auch wenn Elemente mehrfach vorkommen) unerheblich ist.
Beispiel:
Ein Losverkäufer bietet rote, grüne, gelbe und blaue Lose zu je 1 € zum Verkauf an. Wie viele Loskombinationen können bei einem Budget von 3 € erworben werden?
Lösung:
C = (4+3-1)!/(4-1)!·3! = 6!/(3!·3!) = 20.