Permutation

Ist X eine Menge, so bildet die Menge Sym(X) aller bijektiven (also invertierbaren) Abbildungen von X in sich eine Gruppe unter der Verkettung von Abbildungen als Verknüpfung.

Definition: Sei n ≥ 0. Die Gruppe Sn = Sym({1,...,n}) der invertierbaren Abbildungen von {1,...,n} nach {1,...,n} nennt man die symmetrische Gruppe über n Elementen (nennt man so da es von einer Menge in die selbe Menge abbildet). Ein Element σ∈Sn nennt man eine Permutation. Es ist also einfach eine Abbildung die invertierbar ist und von einer Menge in die selbe abbildet.

 

Beispiel:

Im Fall n = 0 suchen wir Bijektionen von der leeren Menge in sich. Natürlich gibt es nur eine solche Abbildung, also ist S0 die triviale Gruppe. Auch im Fall n = 1 gibt es nur eine einzige Bijektion {1} → {1}, und S1 ist ebenfalls die triviale Gruppe. Im Fall n = 2 gibt es zwei Bijektionen von {1,2} nach {1,2}, nämlich die Identität und die Vertauschung 1 ↦ 2 und 2↦1. Also ist S2 die Gruppe mit 2 Elementen. Im Fall n = 3 ist die Abbildung 1↦ 3, 2↦ 2 und 3↦ 1 ein Element in S3, die Abbildung 1↦3, 2↦2 und 3↦2 aber nicht.

 

Es gibt eine handliche Schreibweise für Permutationen:

Dabei sieht man oben das Element und darunter die Abbildung von diesem Element. Hier ein Beispiel zu dieser Schreibweise:

die Abbildung von {1,2,3,4} in sich, die die 1 abbildet auf 3, 2 auf 2, 3 auf 4 und 4 auf 1.

Transposition

Eine Permutation σ, die zwei verschiedene Elemente in {1,...,n} vertauscht, die restlichen aber unverändert lässt, heißt Transposition.

Fehlstand

Sei σ∈Sn eine Permutation. Ein Fehlstand von σ ist ein Paar (i, j) mit 1≤i < j≤n und σ(i) > σ(j). Die Anzahl l(σ) der Fehlstände von σ heißt die Länge von σ. Das Signum von σ ist definiert durch sgn(σ) = (−1)l(σ).

Es ist also immer ein Fehlstand, wenn eine kleinere Zahl, im Vergleich zu einer Größeren, auf eine größere Zahl abgebildet wird.

 

Beispiel:

Die Permutation von vorhin

hat die Fehlstände (1,2), (1,4), (2,4) und (3,4), also l(σ) = 4 und damit ist sgn(σ) = 1.

 

Wie man auf die Fehlstände kommt:

  • (1,2) -> Denn die 1 wird auf die 3 abgebildet und die 2 auf die 2. Da 1<2 ist und die kleinere Zahl (1) auf die größere Zahl abgebildet wird (3>2), ist es ein Fehlstand. Also 1->3 und 2->2, es wird also im Vergleich der beiden die kleinere Zahl auf eine größere Zahl abgebildet und die größere Zahl auf die kleinere. Daher ist es ein Fehlstand.
  • (1,4) -> 1<4 aber die kleinere Zahl der beiden (1) wird auf die größere Abgebildet (3>1). Also ein Fehlstand.
  • (2,4) -> 2<4 aber die 2 wird auf die 2 abgebildet und die 4 auf die 1. Daher wird die kleinere Zahl auf die größere abgebildet, also ein Fehlstand.
  • (3,4) -> 3<4 aber die 3 wird auf die 4 abgebildet und die 4 auf die 1, also die kleinere Zahl wird auf die größere abgebildet. Daher ist es ein Fehlstand.

 

Die Formel zum berechnen des Signums sieht dann so aus: