Permutation mit Wiederholung
In diesem Kapitel beschäftigen wir uns mit der Permutation mit Wiederholung.
Es lohnt sich, zunächst den Einführungsartikel zur Kombinatorik durchzulesen.
Eine Permutation mit Wiederholung ist eine Anordnung von \(n\) Objekten, von denen manche nicht unterscheidbar sind.
Gibt es \(s\) Gruppen, mit jeweils \(k_1,\text{...},k_s\) identischen Objekten, so lautet die Formel
\[\frac{n!}{k_1! \cdot k_2! \cdot \text{...} \cdot k_s!}\]
Herleitung der Formel
Im Kapitel zur Permutation ohne Wiederholung haben wir gelernt, dass es \(n!\) Möglichkeiten gibt, um \(n\) unterscheidbare (!) Objekte auf \(n\) Plätze zu verteilen.
Sind jedoch \(k\) Objekte identisch, dann sind diese auf ihren Plätzen vertauschbar, ohne dass sich dabei eine neue Reihenfolge ergibt. Auf diese Weise sind genau \(k!\) Anordnungen gleich.
Die Anzahl der Permutationen von \(n\) Objekten, von denen \(k\) identisch sind, berechnet sich zu
\[\frac{n!}{k!}\]
Gibt es nicht nur eine, sondern \(s\) Gruppen, mit jeweils \(k_1,\text{...},k_s\) identischen Objekten, so lautet die Formel
\[\frac{n!}{k_1! \cdot k_2! \cdot \text{...} \cdot k_s!}\]
Permutation mit Wiederholung - Beispiele
Aufgabe 1
In einer Urne befinden sich drei blaue und zwei rote Kugeln. Wie viele Möglichkeiten gibt es, die Kugeln in einer Reihe anzuordnen?
Lösung zur Aufgabe 1
\[\frac{5!}{3! \cdot 2!} = \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{(3 \cdot 2 \cdot 1) \cdot (2 \cdot 1)}=10\]
Antwort: Es gibt 10 Möglichkeiten drei blaue und zwei rote Kugeln in einer Reihe anzuordnen.
Aufgabe 2
Wie viele verschiedene sechsziffrige Zahlen gibt es, die zweimal die 1, dreimal die 2 und einmal die 4 enthalten?
Lösung zur Aufgabe 2
\[\frac{6!}{2! \cdot 3! \cdot 1!} = 60\]
Antwort: Es gibt 60 verschiedene Zahlen, die zweimal die 1, dreimal die 2 und einmal die 4 enthalten.
Aufgabe 3 (Mississippi-Problem)
Auf wie viele Arten kann man die Buchstaben des Wortes MISSISSIPPI anordnen?
(1x M / 4x I / 4x S / 2x P)
Lösung zur Aufgabe 3
\[\frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = 34650\]
Antwort: Es gibt 34.650 Möglichkeiten, die Buchstaben des Wortes MISSISSIPPI anzuordnen.
Mehr zur abzählenden Kombinatorik
Die Permutation 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".
Hat dir meine Erklärung geholfen?
Für Lob, Kritik und Anregungen habe ich immer ein offenes Ohr.
Weiterhin viel Erfolg beim Lernen!
Andreas Schneider