Permutationen

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) \]

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.

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.