Permutationen

Definition

Eine Permutation ist eine bijektive Abbildung einer endlichen Menge X in sich selbst.
Um die Sache etwas anschaulicher zu machen, setzen wir von nun an X gleich der Menge der natürlichen Zahlen von 1 bis n, d.h. X = {1,2,...,n}. Dann ist eine Permutation also eine Abbildung, die die Zahlen 1 bis n bijektiv auf sich selbst abbildet.
Um eine Permutation aufzuschreiben wählt man meist eine Matrixschreibweise mit zwei Zeilen und n Spalten, bei der man in der oberen Zeile die Zahlen 1 bis n einträgt und in der unteren Zeile die jeweils der obigen Zahl zugeordnete Zahl. Man bezeichnet Permutationen in der Regel mit π oder τ (τ eher bei Transpositionen, s.u.).

Beispiele

Die Identitätsabbildung ist eine Permutation, nämlich diejenige, welche jeder Zahl von 1 bis n die Zahl selbst zuordnet.
Eine Permutation, welche nur zwei Elemente vertauscht und bei den übrigen die Identitätsabbildung anwendet, heißt Transposition.
Eine Permutation auf X = {1,2,3,4,5,6}:

Bemerkungen

Die Menge aller Permutationen der Menge X = {1,2,...,n} wird die symmetrische Gruppe auf n Elementen genannt und mit S(n) bezeichnet.
Es handelt sich hierbei auch wirklich um eine Gruppe, indem man die Hintereinanderausführung von Permutationen als Multiplikation definiert.
Es ist leicht zu sehen, dass die Hintereinanderausführung zweier Permutationen von n Elementen wieder eine solche Permutation ist. Das neutrale Element ist natürlich die Identität und auch das Inverse zu einer gegebenen Permutation sollte klar sein.

Beispiel:

Beachte, dass die Multiplikation von Permutationen als Verknüpfung von Funktionen von rechts nach links gelesen und ausgeführt werden muss.

Ein Element, welches bei einer Permutation festgehalten wird, d.h. π(i) = i , wird Fixpunkt von π genannt.

Beispiel:

In diesem Beispiel ist die 3 ein Fixpunkt der Permutation.

Eine Permutation wird Zyklus (oder zyklische Permutation) genannt, falls die Elemente, welche keine Fixpunkte sind zyklisch vertauscht werden.
Ordentlich definiert heißt das Folgendes:
Eine Permutation heißt zyklisch, falls es ein i aus X und eine natürliche Zahl k gibt, so dass die folgenden drei Bedingungen erfüllt sind:
(i) π^k(i) = i,
(ii) die Elemente i, π(i), π²(i),..., π^k-1 sind paarweise verschieden,
(iii) jedes Element, das verschieden von i, π(i), π²(i),..., π^k-1(i), π^k(i)=i ist, ist ein Fixpunkt von π.

Fehlstände einer Permutaion:
Als Fehlstände einer Permutation werden die Zahlenpaare (i,j) bezeichnet, für die gilt: i < j und π(i) > π(j).
Beispiel:

In diesem Beispiel gibt es die Fehlstände (1,3), (2,3), (2,4).
Eine Permutation wird dann gerade bzw. ungerade genannt, wenn die Anzahl der Fehlstände der Permutation gerade bzw. ungerade ist. Obiges Beispiel ist also eine ungerade Permutation.
Über diese Eigenschaft wird dann auch die Signumfunktion für Permutationen definiert.
Die Menge der geraden Permutationen wird auch als alternierende Gruppe A(n) bezeichnet.

Eigenschaften

Die Anzahl der Permutationen von n Elementen, somit die Anzahl der Elemente von S(n) beträgt genau n! (n Fakultät).
Jede Permutation kann als das Produkt zyklischer Permutationen dargestellt werden.
Man kann jede Permutation als Produkt von Transpositionen, sogar von Nachbartranspositionen (d.h. die beiden vertauschten Elemente folgen direkt aufeinander) darstellen.

Links

Leider konnten wir keine interessanten Seiten zu diesem Thema finden. Sie haben eine Seite zum Thema? Schreiben Sie uns! (mail[at]mathematik.de)