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


Hilfe bei Matheproblemen - die fb Gruppe

Es gibt nun eine Facebook-Gruppe von Studimup, auf welcher ihr Hilfe bei Matheproblemen bekommt. Dies funktioniert so:

  1. Ihr stellt eure Frage als Post in die Gruppe.
  2. Wenn jemand die Antwort weiß, kann er sie in den Kommentaren beantworten. 

Wenn ihr also mal Schwierigkeiten bei einer bestimmten Aufgabe oder einem Thema habt, dann könnt ihr eure Frage in die Gruppe posten. Ebenso könnt ihr anderen Personen bei ihren Problemen helfen und so selbst das Thema üben und vertiefen. Mit der Gruppe soll es möglich sein, möglichst schnell antworten auf ein Problem zu bekommen (z.B. bei einer Hausaufgabe). Je mehr Leute mitmachen, desto besser funktioniert dieses System. 

mehr lesen 0 Kommentare