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".

Autor: Andreas Schneider
Seit 2010 beschäftigt er sich mit dem Thema "Mathematik online lernen". Die Lernvideos auf seinem YouTube-Kanal NachhilfeTV wurden bereits über 2 Millionen Mal aufgerufen.
Über das Kontaktformular kannst du mit dem Autor direkt in Verbindung treten.