Symmetrische Gruppe

siehe auch:   Gruppentheorie || endliche Gruppe

Die symmetrische Gruppe Sym_n oder S_n besteht aus allen

Permutationen einer Menge mit n Elementen, Gruppenoperation ist die

Verkettung der Permutationen.

Sym_n besitzt n! ( n Fakultät ) Elemente.

Für n > 2 ist Sym_n nicht kommutativ.

Permutationen

In der Gruppentheorie versteht man unter einer n-stelligen Permutation die bijektive Abbildung einer Menge mit n Elementen auf sich selber. Da die "Namen" der Mengenelemente für die folgende Theorie ohne Bedeutung sind, benutzt man als Mengenelemente in der Regel die Zahlen von 1 bis n als "Namen".

Matrixdarstellung

In der ausführlichen Darstellung einer Permutation schreibt man diese als zweizeilige Matrix,in jeder Spalte der Matrix steht unter einer Zahl deren Funktionswert.

Beispiel:

besagt, dass p die Zahl 1 auf die 3 abbildet, p (2) = 2, p (4) = 1 und p (3) = 4.

Vektordarstellung

Die Reihenfolge, in der die einzelnen Spalten in der Matrix dargestellt werden ist ohne Bedeutung,man kann beliebige Spalten der Darstellung vertauschen, ohne dabei die Permutation selbst zu verändern.

Als Spezialfall kann man die Spalten so anordnen, dass in der oberen Zeile die Zahlen in aufsteigender Folge dargestellt werden. Die obere Zeile enthält nun keine praktische Information mehr und kann deshalb in einer verkürzten Darstellung einfach weggelassen werden.

Beispiel:

Verkettung

Die Verkettung zweier n-stelliger Permutationen p2 ◊ p1 besagt, dass die Permutation p2 nach p1 ausgeführt wird, d.h. p2 wird auf das Ergebnis von p1 ausgeführt. Das Ergebnis der Verkettung ist erneut eine n-stellige Permutation.

Beispiel:

Zunächst bildet die "rechte" Permutation die 4 auf die 1 ab,anschließend bildet die "linke" Permutation die 1 auf die 2 ab.

Die gesamte Verkettung bildet also die 4 auf die 2 ab.

Rechenschema

Das Ergebnis einer Verkettung lässt sich u.a. nach folgendem Schema ermitteln:

• Ordnen der Spalten der linken Permutation, so dass die obere Zeile der linken Permutation gleich der unteren Zeile der rechten Permutation ist.
• Das Ergebnis der Verkettung besteht nun aus der oberen Zeile der rechten und der unteren Zeile der linken Permutation.

Beispiel:

Gruppeneigenschaften

Verkettungen sind generell assoziativ

Für jede n-stellige Permutation p gilt: p ◊ id = id ◊ p = p,wobei id die identische Permutation ( 1 2 3 ... n ) bezeichnet.

Zu jeder n-stelligen Permutation p gibt es eine Permutation p^-1

mit p ◊ p^-1 = p^-1 ◊ p = id.

p^-1 lässt sich aus p generieren, indem obere und untere Zeile vertauscht werden.

Beispiel:

Für n > 2 ist die symmetrische Gruppe Sym_n nicht kommutativ:

• ( 2 3 1..._ ) ◊ ( 2 1 3..._ ) = ( 3 2 1..._ )
• ( 2 1 3..._ ) ◊ ( 2 3 1..._ ) = ( 1 3 2..._ )