Kombination

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.

Abbildung 23 Anzahl möglicher Anordnungen (Permutation) um gleiche Elemente vermindert
Abbildung 23: Anzahl möglicher Anordnungen (Permutation) um gleiche Elemente vermindert

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.

Abbildung 24 Permutationen und Ziehung Urne
Abbildung 24: Permutationen und Ziehung Urne

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:

Abbildung 25 Baumstruktur Möglichkeiten Auswahl
Abbildung 25: Baumstruktur Möglichkeiten Auswahl

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.

Abbildung 26 Anzahl der Permutationen der Restmenge (Reihenfolge unerheblich)
Abbildung 26: Anzahl der Permutationen der Restmenge (Reihenfolge unerheblich)

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.