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


Geld sparen mit dem int. Studentenausweis

Studenten und Schüler sind meist knapp bei Kasse und daher wird jede Möglichkeit genutzt Geld zu sparen. Eine dieser Möglichkeiten ist der internationale Studenten- und Schülerausweis (ab 12 Jahren). Mit diesem könnt ihr in über 135 Ländern Vergünstigungen bekommen! Dafür müsst ihr nur 15€ für den Ausweis zahlen. Übrigens gibt es den Ausweis auch für Lehrer!

mehr lesen 0 Kommentare