Permutation
Inhaltsverzeichnis
[Verbergen]Mit der Permutation (Vertauschung) wird die Anzahl aller möglichen Anordnungen der Elemente einer Grundmenge berechnet. Unterscheidungsmerkmal ist also die Reihenfolge der Elemente.
Aufgabe:
Alle N Elemente der Grundmenge werden in eine bestimmte Reihenfolge gebracht.
Fragestellung:
Wie viele Anordnungen (Permutationen) der Grundmenge gibt es?
Permutation ohne Wiederholung
Geltungsbereich:
1. Alle N Elemente der Ausgangsmenge sind unterscheidbar.
2. Es werden alle Elemente ausgewählt.
3. Die Reihenfolge ist wichtig.
4. Elemente können nicht mehrfach ausgewählt werden.
Fragestellung:
Wie viele unterschiedliche Permutationen gibt es?
Die Anzahl der Permutationen ohne Wiederholung errechnet sich nach
\( {P_N} = N! \quad \text{ mit } n! = 1 \cdot 2 \cdot 3 \cdot 4... \cdot n \) Gl. 73
Anhand der sog. Baumstruktur kann Gl. 73 für kleine Mengen (hier: 3 Elemente) überprüft werden:
Jedes Element der Grundmenge wird mit allen verbleibenden Elementen angeordnet. Jede Anordnung wird gezählt, d.h. die Reihenfolge ist wichtig.
Beispiel:
Bei einem Pferderennen wird auf den Einlauf in einer bestimmten Reihenfolge gewettet. 8 Pferde gehen an den Start. Wie groß ist die Wahrscheinlichkeit für die Platzierung 1-2-3-4-5-6-7-8?
Lösung:
\( \frac{1}{8!} ≈ 0,0025 \% \)
Permutation mit Wiederholung
Geltungsbereich:
1. Die N Elemente der Ausgangsmenge sind nicht alle unterscheidbar.
2. Es werden alle Elemente ausgewählt.
3. Die Reihenfolge ist wichtig.
4. Individuen können nicht mehrfach ausgewählt werden, Elemente schon.
Fragestellung:
Wie viele unterschiedliche Anordnungen (Permutationen) gibt es?
Die Anzahl der Permutationen mit Wiederholung errechnet sich nach
\( P_N^{ {k_1},{k_2},{k_3}...} = \frac{ {N!} }{ { {k_1}! · {k_2}! · {k_3}!...{k_n}!} } \) Gl. 74
Weil bestimmte Elemente mehrfach vorkommen, ist die Zahl der unterscheidbaren Anordnungen um die jeweiligen Permutationen der mehrfach vorkommenden Elemente geringer.
Zwischenbetrachtung – das Urnenmodell
Im Urnenmodell werden alle zu betrachtenden Elemente für den Ziehungsleiter unsichtbar in einer Urne untergebracht. Die Aufgabe besteht nun darin, stets alle Elemente aus der Urne zu entnehmen, deren Reihenfolge zu registrieren und
anschließend wieder in die Urne zurück zu legen. Dies wird sooft wiederholt, bis alle möglichen unterscheidbaren Kombinationen gefunden worden sind.
Zwischenbetrachtung – das Baummodell
Die Baumstruktur für 3 Elemente, von denen zwei Elemente doppelt vorkommen:
Beispiel 1:
Würde die ehemals sehr beliebte Pop-Gruppe ABBA ihren Namen als Grundlage für eine Komposition nehmen, wobei jedem Buchstaben der entsprechende Tonwert zuzuordnen ist, so ist die Frage wie viele unterschiedliche Klangfolgen sind aus den Buchstaben A (2x) und B (2x) ableitbar?
Lösung:
P=4!/(2!·2!) = 6 verschiedene Klangfolgen können aus A B B A erzeugt werden:
ABBA, BAAB, AABB, BBAA, ABAB, BABA
Aus diesem Beispiel wird klar, warum es sich hier um eine Permutation mit Wiederholung handelt: die Buchstaben A und B kommen wiederholt vor. Aber auch das folgende Beispiel fällt in diese Kategorie, auch wenn nicht auf den ersten Blick zu sehen ist, worin die Wiederholung besteht.
Beispiel 2:
Ein Skat-Spiel besteht aus 32 (unterscheidbaren) Karten. Nach dem Mischen erhalten die drei Spieler je 10 Karten und 2 Karten verbleiben im Skat. Wie viele unterschiedliche Kartenzusammensetzungen für ein Spiel gibt es?
Lösung:
P=32!/(10!·10!·10!·2!)= 2,75·1015 verschiedene Kartenkombinationen sind möglich, d.h. die Wahrscheinlichkeit für das Auftreten von zwei gleichen Spielen ist äußerst gering!
Die Anwendung der Permutation mit Wiederholung ist im Beispiel 2 darauf zurückzuführen, dass es für das Spiel unbedeutend ist, in welcher Reihenfolge die jeweils 10 Karten der Spieler oder der 2 Karten des Skats gegeben wurden. Die Anzahl dieser Permutationen vermindert die Anzahl der Gesamtpermutationen.
Beispiel 3:
Wie viele mögliche Kartenverteilungen im Skat gibt es?
Lösung:
P = 32!/(30!·2!) = 32·31/2 = 496