Kombination mit Wiederholung
In diesem Kapitel beschäftigen wir uns mit der Kombination ohne Wiederholung.
Es lohnt sich, zunächst den Einführungsartikel zur Kombinatorik durchzulesen.
Bei einer Kombination mit Wiederholung werden \(k\) aus \(n\) Objekten ohne Beachtung der Reihenfolge ausgewählt, wobei Objekte auch mehrfach ausgewählt werden können.
\[{n+k-1 \choose k}\]
Der einzige Unterschied zwischen einer Kombination ohne Wiederholung und einer Kombination mit Wiederholung ist die Tatsache, dass bei der Kombination mit Wiederholung die Objekte auch mehrmals ausgewählt werden können.
Die Formel für die Kombination ohne Wiederholung kennen wir bereits
\[\frac{n!}{(n-k)! \cdot k!} = {n \choose k}\]
Durch eine kleine Modifikation des Zählers und des Nenners gelangen wir schließlich zur Formel für eine Kombination mit Wiederholung
\[\frac{(n+k-1)!}{(n-1)! \cdot k!} = {n+k-1 \choose k}\]
Kombination mit Wiederholung - Beispiele
Aufgabe 1
In einer Urne befinden sich fünf verschiedenfarbige Kugeln. Es sollen drei Kugeln mit Zurücklegen (= mit Wiederholung) und ohne Beachtung der Reihenfolge gezogen werden. Wie viele Möglichkeiten gibt es?
Lösung zur Aufgabe 1
\[{5+3-1 \choose 3} = {7 \choose 3} = 35\]
Antwort: Es gibt 35 Möglichkeiten 3 aus 5 Kugeln mit Zurücklegen ohne Beachtung der Reihenfolge zu ziehen.
Aufgabe 2
Franziska hat vier kleine (nicht unterscheidbare) Welpen. Wenn sie aufgeschreckt werden, sucht sich jeder einen Platz unter einem der sechs Esszimmerstühle. Wie viele unterschiedliche Verteilungen der vier Welpen kann Franziska beobachten?
Hinweis: Diese Aufgabe ist "mit Wiederholung", weil sich auch alle Hunde unter nur einem Stuhl verkriechen könnten. Außerdem ist selbstverständlich die Reihenfolge der Hunde unter einem Stuhl irrelevant.
Lösung zur Aufgabe 2
\[{6+4-1 \choose 4} = {9 \choose 4} = 126\]
Antwort: Es gibt 126 Möglichkeiten, wie sich die Hunde unter den Stühlen verstecken können.
Mehr zur abzählenden Kombinatorik
Die Kombination mit Wiederholung gehört zur abzählenden Kombinatorik. Dabei handelt es sich um den Teilbereich der Kombinatorik, der sich mit der Bestimmung der Anzahl möglicher Anordnungen (Permutationen) oder Auswahlen (Variationen, Kombinationen) beschäftigt.
|
Menge |
Reihenfolge |
||
| Permutation ohne Wiederholung | \(n!\) | \(n\) aus \(n\) | wird beachtet |
| Permutation mit Wiederholung | \(\frac{n!}{k_1! \cdot k_2! \cdot \text{...} \cdot k_s!}\) | \(n\) aus \(n\) | wird beachtet |
| Variation ohne Wiederholung | \(\frac{n!}{(n-k)!}\) | \(k\) aus \(n\) | wird beachtet |
| Variation mit Wiederholung | \(n^k\) | \(k\) aus \(n\) | wird beachtet |
| Kombination ohne Wiederholung | \({n \choose k}\) | \(k\) aus \(n\) | wird nicht beachtet |
| Kombination mit Wiederholung | \({n+k-1 \choose k}\) | \(k\) aus \(n\) | wird nicht beachtet |
Sind die Objekte untereinander unterscheidbar, so spricht man von einer Permutation/Variation/Kombination "ohne Wiederholung" (derselben Objekte). Falls die Objekte jedoch nicht unterscheidbar sind, spricht man von einer Permutation/Variation/Kombination "mit Wiederholung". Im Urnenmodell sagt man statt "ohne Wiederholung" einfach "ohne Zurücklegen" und zu "mit Wiederholung" entsprechend "mit Zurücklegen".