Kombination mit Wiederholung
Die Kombinatorik hilft bei der Bestimmung der Anzahl möglicher Anordnungen (Permutationen) oder Auswahlen (Variationen oder Kombinationen) von Objekten.
In diesem Kapitel schauen wir uns die Kombination mit Wiederholung an, die folgende Frage beantwortet:
Wie viele Möglichkeiten gibt es,
$\boldsymbol{k}$ Kugeln aus einer Urne mit $\boldsymbol{n}$ Kugeln ohne Beachtung der Reihenfolge und mit Zurücklegen zu ziehen?
Erforderliches Vorwissen
Definition
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.
Formel
$$ {n+k-1 \choose k} $$
Herleitung
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} $$
Eine kleine Modifikation des Zählers und des Nenners führt uns schließlich zur Formel für eine Kombination mit Wiederholung
$$ \frac{(n+k-1)!}{(n-1)! \cdot k!} = {n+k-1 \choose k} $$
Beispiele
In einer Urne befinden sich fünf verschiedenfarbige Kugeln. Es sollen drei Kugeln ohne Beachtung der Reihenfolge und mit Zurücklegen gezogen werden.
Wie viele Möglichkeiten gibt es?
$$ {5+3-1 \choose 3} = {7 \choose 3} = 35 $$
Es gibt 35 Möglichkeiten 3 aus 5 Kugeln ohne Beachtung der Reihenfolge und mit Zurücklegen zu ziehen.
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 die Reihenfolge der Hunde unter einem Stuhl selbstverständlich irrelevant.
$$ {6+4-1 \choose 4} = {9 \choose 4} = 126 $$
Es gibt 126 Möglichkeiten, wie sich die Hunde unter den Stühlen verstecken können.
