Permutation (Kombinatorik)

Grundbegriffe

Permutation

Jede Zusammenstellung, in der alle $n$ gegebenen Elemente in irgendeiner Anordnung stehen, heißt eine Permutation (lat. Vertauschung, Austausch, Umstellung).

Dies impliziert, dass sich Permutationen durch die unterschiedliche Anordnung der $n$ Elemente ergeben.

Es können 2 Varianten von Permutationen unterschieden werden:

1. Permutation mit Wiederholung
2. Permutation ohne Wiederholung

Permutation ohne Wiederholung

Bei der Permutation ohne Wiederholung wird davon ausgegangen, dass alle $n$ Elemente verschieden sind, also jedes Element nur einmal vorkommt.

Die Anzahl der möglichen Permutationen von $n$ Elementen ohne Wiederholung, symbolisiert mit $P(n)$, ist:

$P(n)=1\cdot 2\cdot 3\cdot \ldots \cdot n=n\,!$

Permutation mit Wiederholung

Bei der Permutation mit Wiederholung wird davon ausgegangen, dass unter den $n$ gegebenen Elementen mehrere Elemente identisch sind.

Es existiert also eine Gruppe von gleichen Elementen.

Die Anzahl der möglichen Permutationen aus $n$ Elementen mit Wiederholung, symbolisiert mit $P(n;g)$, ist:

$P(n;g)={\frac {n\,!}{g\,!}}\qquad g\leq n,$

wobei $g$ die Anzahl der Elemente ist, die gleich sind (Größe der Gruppe).

Weiterhin gibt es Permutationen, bei welchen unter den $n$ gegebenen Elementen mehrere Gruppen gleicher Elemente existieren.

Die Anzahl der möglichen Permutationen ist für $r$ Gruppen:

$P(n;g_{1},\dots ,g_{r})={\frac {n\,!}{g_{1}\,!\cdot g_{2}\,!\cdot \dots \cdot g_{r}\,!}}$

wobei $g_{i}$ die Größe der $i$-ten Gruppe ist und $g_{1}+g_{2}+g_{3}+\dots +g_{r}\leq n$ gelten muss.

Beispiele

Permutationen ohne Wiederholung

• Für 2 verschiedene Elemente ($a$ und $b$) ist die Anzahl der möglichen Permutationen $P(2)=1\cdot 2=2\,!=2$.

Die beiden Permutationen sind logischerweise:

$ab$ und $ba$

• Für 3 verschiedene Elemente ($a$, $b$ und $c$) ist die Anzahl der möglichen Permutationen $P(3)=1\cdot 2\cdot 3=3\,!=6$.

Die sechs möglichen Permutationen sind:

$abc$ $acb$ $bac$ $bca$ $cab$ $cba$

Permutationen mit Wiederholung

• Zuerst wird wieder der Fall zweier Elemente betrachtet.

Für zwei verschiedene Elemente ($a$ und $b$) ist die Anzahl der möglichen Permutationen $P(2)=2\,!/1\,!=2$ (wie bei der Permutation ohne Wiederholung):

$aa$ $ba$

Für zwei identische Elemente (:$a$ und $a$) ist die Anzahl der möglichen Permutationen $P(2;2)=2!/2!=1$.

Die einzig mögliche Permutation ist:

$aa$

• Für genau 3 Elemente kann $g=1$ (wie bei der Permutation ohne Wiederholung) oder $g=2$ (zwei identische Elemente und ein drittes verschiedenes) oder $g=3$ (alle Elemente sind identisch) sein:

• Wenn $g=1$ ($a$, $b$ und $c$) ist, so ist die Anzahl der möglichen Permutationen $P(3)=3!/1!=6$. Die sechs möglichen Permutationen sind:

$abc$ $acb$ $bac$ $bca$ $cab$ $cba$

• Wenn $g=2$ ($a$, $a$ und $b$), ist, so ist die Anzahl der möglichen Permutationen $P(3;2)=3!/2!=3$. Die drei möglichen Permutationen sind:

$aac$ $aca$ $caa$

• Wenn $g=3$ ($a$, $a$ und $a$), ist, so ist die Anzahl der möglichen Permutationen $P(3;3)=3!/3!=1$. Die einzig mögliche Permutation ist:

$aaa$

Wie man sehen kann, ist die Permutation ohne Wiederholung ein Spezialfall der Permutation mit Wiederholung. Die Permutation mit Wiederholung einer Gruppe gleicher Elemente ist wiederum ein Spezialfall der Permutation mit Wiederholung mehrerer Gruppen gleicher Elemente.

Schönheitswettbewerb

An einem Schönheitswettbewerb nehmen 14 Bewerber teil. Jeder der anwesenden Juroren soll seine persönliche Rangliste der 14 Bewerber zusammenzustellen.

Wenn jeder der Juroren einen anderen Geschmack bezüglich der Platzierung hat, wieviele Juroren werden dann gebraucht, um alle möglichen (voneinander verschiedenen) Ranglisten der 14 Bewerber zu erhalten?

Da es sich in diesem Fall um eine Zusammenstellung aller $n$ Elemente (hier die Bewerber) handelt, liegt eine Permutation vor.

Zu entscheiden ist jetzt noch, welche der zwei möglichen Permutationen - Permutation mit Wiederholung oder Permutation ohne Wiederholung - die richtige ist.

Da jeder Bewerber in einer Rangliste nur einmal platziert sein kann, liegt eine Permutation ohne Wiederholung vor.

$P(n)=1\cdot 2\cdot 3\cdot \dots \cdot n=n!$

$P(14)=1\cdot 2\cdot 3\cdot \dots \cdot 14=14!=87\;178\;291\;200$

Es werden mehr als 87 Milliarden Juroren gebraucht. Die aufzutreiben dürfte bei einer Erdbevölkerung von ca. 7,2 Milliarden (Jan. 2014) ein Problem werden.