Permutation 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 Permutation mit Wiederholung an, die folgende Frage beantwortet:
Wie viele Möglichkeiten gibt es, nicht voneinander unterscheidbare Kugeln in einer Reihe anzuordnen?
Erforderliches Vorwissen
Definition
Eine Permutation mit Wiederholung ist eine Anordnung von $n$ Objekten, von denen manche nicht unterscheidbar sind.
Formel
Es gibt
$$ \frac{n!}{k_1! \cdot k_2! \cdot \ldots \cdot k_s!} $$
Möglichkeiten, $n$ Objekte, die sich in $s$ Gruppen mit jeweils $k_1, \dots, k_s$ identischen Objekten einteilen lassen, anzuordnen.
Herleitung
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. Folglich 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,\dots,k_s$ identischen Objekten so lautet die Formel
$$ \frac{n!}{k_1! \cdot k_2! \cdot \dots \cdot k_s!} $$
Beispiele
In einer Urne befinden sich drei blaue und zwei rote Kugeln.
Wie viele Möglichkeiten gibt es, die Kugeln in einer Reihe anzuordnen?
$$ \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 $$
Es gibt 10 Möglichkeiten drei blaue und zwei rote Kugeln in einer Reihe anzuordnen.
Wie viele verschiedene sechsziffrige Zahlen gibt es, die zweimal die 1, dreimal die 2 und einmal die 4 enthalten?
$$ \frac{6!}{2! \cdot 3! \cdot 1!} = 60 $$
Es gibt 60 verschiedene Zahlen, die zweimal die 1, dreimal die 2 und einmal die 4 enthalten.
