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:

Blog


NEU: Spickzettel A6

Die neuen Spickzettel A6 by Studimup sind da! Das sind Lernkarten mit knackigen und einfachen Erklärungen im praktischen DIN A6 Format. Sie ermöglichen es einfach Mathe zu lernen und zu wiederholen, egal wo man ist, ob im Bus, der Bahn oder in der Sonne auf dem Balkon. In drei Varianten nach Klassenstufen unterteilt, findet jeder seine passenden Lernkarten:

mehr lesen 0 Kommentare