Das Wichtigste in Kürze

Permutationen sind ein wichtiges Konzept der Kombinatorik. Sie sind die Vertauschungen der Reihenfolge aller Objekte, z.B. Buchstaben in einem Wort. Die Anzahl möglicher Permutationen von $n$ verschiedenen Objekten ist:

\[ ^nP = n! \]

Dabei ist $n!$ die Fakultät $n$, definiert als:

\[ n! = n \cdot (n-1) \cdot (n-2) \cdot … \cdot 3 \cdot 2 \cdot 1 \]

Die Anzahl möglicher Permutationen von $n$ Objekten, mit sich $k_j$-fach wiederholende Objekte, ist:

\[ ^nP_{(k_1,k_2,…,k_j)} = \frac{n!}{k_1! \cdot k_2! \cdot \;…\; \cdot k_j!} \]

Permutationen stellen einen Spezialfall der k-Permutationen (Variationen) dar, in welchem die Auswahl $k$ gleich der Grundmenge $n$ entspricht, d.h. $k=n$:

\[ ^nP = ^nP_n \]

Videos

In zwei Videos wird die Theorie erklärt und mit Beispielen illustriert.

Um die beiden Videos anzusehen, musst du einloggen
Noch kein Login? Hier registrieren

Permutationen unterschiedlicher Objekte

In der Mathematik sind $n$-Tupel eine Anordnung von $n$ mathematischen Objekten in einer bestimmten Reihenfolge, z.B. $(B,R,W)$ für die Kugeln blau, rot und weiss, genau in dieser Reihenfolge.

Ändern wir die Reihenfolge z.B. zu $(W,R,B)$, so erhalten wir ein anderes Tupel, eine sog. Permutation:

\[ (B,R,W) \neq (W,R,B) \]

Beispiel: Die drei Buchstaben $A$, $B$ und $C$ bilden 3-Tupel: $(A,B,C)$ und noch weitere 5 Permutationen davon:

\[ (A,B,C),\;\; (A,C,B),\;\; (B,A,C),\;\; (B,C,A),\;\; (C,A,B),\;\; (C,B,A) \]

Beachte, dass unter dem Begriff zyklische Permutation eine spezielle Permutation gemeint ist: Die verschiedenen Objekte sind auf einem Kreis angeordnet und können zum nächsten Wert in einer bestimmten Drehrichtung umgetauscht werden.

Wenn wir zyklisch permutieren, z.B. $A \rightarrow B \rightarrow C \rightarrow A$, so wird aus einem $(A,B,C)$ nur ein $(B,C,A)$. Wenn wir nochmals zyklisch permutieren, erhalten wir $(C,A,B)$.

\[ (A,B,C),\;\; \;\; (B,C,A),\;\; (C,A,B) \]

Hier gibt es nur 3 zyklische Permutationen. Die anderen 3 zyklischen Permutationen bilden eine andere Gruppe:

\[ (A,C,B),\;\; \;\; (B,A,C),\;\; (C,B,A) \]

Beispiel: Buchstaben-Permutationen

Wie viele Wörter können wir mit 8 verschiedenen Buchstaben bilden? Die Wörter müssen nicht unbedingt existrieren oder Sinn machen.

Wir betrachten die Aufgabenstellung wie ein Problem im Urnenmodell: Wir ziehen den ersten von 8 Buchstaben. Dafür gibt es 8 Möglichkeiten.

Würden wir einen Baum zeichnen, müssten wir jetzt 8 Äste zeichnen.

Für den zweiten Buchstaben gibt es 7 Möglichkeiten, da noch 7 Buchstaben in der Urne sind.

Dann gibt es beim dritten Buchstaben 6 Möglichkeiten, beim vierten Buchstaben 5 Möglichkeiten etc.

Wir ziehen alle Buchstaben nach einander und erhalten:

\[ ^8 P = 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 8! \]

\[ \underline{^8 P = 40’320} \]

Für $n$ Objekte können wir jetzt verallgemeinern:

\[ ^nP = n \cdot (n-1) \cdot (n-2) \cdot … \cdot 3 \cdot 2 \cdot 1 \]

Dazu gibt es eine verkürzte Schreibweise, die sich Fakultät $n$ nennt und mit einem Ausrufezeichen geschrieben wird:

\[ n! = n \cdot (n-1) \cdot (n-2) \cdot … \cdot 3 \cdot 2 \cdot 1 \]

Beachte: Permutationen müssen immer alle $n$ Objekte enthalten, ganz im Gegensatz zu den sog. k-Permutationen (Variationen), die nur $k<n$ Objekte enthalten.

“Wenn sich Objekte wiederholen können, gibt es dadurch weniger mögliche Vertauschungen (Permutationen)”

Permutationen mit sich wiederholenden Objekten

Sobald wir sich wiederholende Objekte haben, die nicht unterscheidbar sind, gibt es weniger mögliche Permutationen. Im vorigen Beispiel von 3 Buchstaben hatten wir 6 mögliche Permutationen:

\[ (A,B,C),\;\; (A,C,B),\;\; (B,A,C),\;\; (B,C,A),\;\; (C,A,B),\;\; (C,B,A) \]

Wenn zwei Buchstaben aber gleich sind, haben wir nur noch deren 3 Stück:

\[ (A,A,B),\;\; (A,B,A),\;\; (B,A,A) \]

Der Grund liegt darin, dass wenn aus $A$ ein $A_1$ machen und aus $C$ ein $A_2$ wird, können wir die folgenden Tupel nicht mehr unterscheiden:

\[ (A_1,A_2,B), \;\; (A_2,A_1,B) \quad \rightarrow \quad (A,A,B) \]

\[ (A_1,B,A_2), \;\;  (A_2,B,A_1) \quad \rightarrow \quad (A,B,A) \]

\[ (B,A_1,A_2), \;\; (B,A_2,A_1) \quad \rightarrow \quad (B,A,A) \]

Aus sechs Permutationen sind es jetzt nur noch drei!

Wie sieht das aus bei drei sich wiederholenden Objekten? Stellen wir die Frage andersrum: Wieviele Möglichkeiten gibt es, $A_1$, $A_2$ und $A_3$ anzuordnen? Es sind $3!=6$ Möglichkeiten:

\[ (A_1,A_2,A_3), \;\; (A_2,A_3,A_1), \;\; (A_3,A_1,A_2), \;\; (A_2,A_1,A_3), \;\; (A_1,A_3,A_2), \;\; (A_3,A_2,A_1) \quad \rightarrow \quad (A,A,A) \]

Wenn wir sie unterscheiden können, sind es

\[ ^3 P = 3! = 6 \]

Sobald wir sie aber nicht mehr unterscheiden können, gilt:

\[ ^3 P_(3) = \frac{3!}{3!} = 1 \]

Wir müssen durch die Anzahl Permutationen, die die sich wiederholenden Objekte ausgemacht haben. Für die drei $A_1$, $A_2$ und $A_3$ gab es natürlich auch wieder 6 Permutationen. Deshalb verschwinden diese 6 Permutationen und uns bleibt nur noch eine Anordnung übrig, nämlich $(A,A,A)$.

Wir verallgemeinern: Die Anzahl möglicher Permutationen von $n$ Objekten, wovon $k_i$ gleiche Objekte sind, ist:

\[ ^nP_{(k_1,k_2,…,k_j)} = \frac{n!}{k_1! \cdot k_2! \cdot \;…\; \cdot k_j!} \]

Im Zähler haben wir die Anzahl Möglichkeiten für unterschiedliche Objekte. Unten im Nenner dividieren wir diese Zahl mit der Anzahl Permutationen, die durch die gleichen Objekte wieder verloren gehen.

Beispiel: Buchstaben-Permutation

Wie viele Permutationen gibt es vom Wort $(R,A,D,A,R)$?

Der Buchstabe $R$ kommt zwei Mal vor. Der Buchstabe $A$ auch. Der Buchstabe $D$ hingegen nur einmal. Ohne Berücksichtigung der mehrfach vorkommenden Buchstaben, hätten wir $5!=120$ Möglichkeiten. Dabei würden wir aber zwischen $A_1,A_2$ und $A_2,A_1$ unterscheiden, also zwei Mal zu viele Möglichkeiten zählen. Auch würden wir $R_1,R_2$ und $R_2,R_1$ doppelt zählen, obwohl es nur einmal gezählt werden müsste. Damit haben wir für die Anzahl Möglichkeiten:

\[ ^5P_{(2,2)} = \frac{5!}{2! \cdot 2!} = \frac{120}{2 \cdot 2} = \underline{30} \]

Lernziele

  • Du weisst, wie eine Permutation definiert ist und dass dazu alle Objekte benutzt werden und beliebig in ihrer Anordnung vertauscht werden können.
  • Du kannst die Anzahl möglicher Permutationen sowohl bei ausschliesslich unterschiedlichen Objekten, wie für eine Menge sich teilweise wiederholender Objekte, berechnen.

Mini-Test

(zu diesem Thema gibt es noch keinen Mini-Test)

Weitere Links


Physik- und Mathe-Hacks lernen…

…im Hacker-Club!

Aufgabensammlung

  • Binomialkoeffizient und Kombinationen (5053) – Aufg. 7

    4 Teilaufgaben (pdf/Video-Lösung):
    Anspruchsvoll: Organisation Volleyball-Turnier (Textaufgabe)

  • Permutationen (5052) – Aufg. 1

    3 Teilaufgaben (pdf/Video-Lösung):
    Freunde treffen sich (Textaufgabe)

  • Permutationen (5052) – Aufg. 2

    4 Teilaufgaben (pdf/Video-Lösung):
    Buchstaben vertauschen

  • Permutationen (5052) – Aufg. 3

    3 Teilaufgaben (pdf/Video-Lösung):
    Zahlenkombinationen in Bytes (Textaufgabe)

  • Permutationen (5052) – Aufg. 6

    3 Teilaufgaben (pdf/Video-Lösung):
    Spielabend unter Freunden (Textaufgabe)