Symmetrische 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.

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:
${\begin{pmatrix}1&2&3&4\\2&3&1&4\end{pmatrix}}nach{\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}$
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:
${\begin{pmatrix}1&2&3&4\\2&3&1&4\end{pmatrix}}nach{\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}={\begin{pmatrix}3&2&4&1\\1&3&4&2\end{pmatrix}}nach{\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}={\begin{pmatrix}1&2&3&4\\1&3&4&2\end{pmatrix}}$

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:
${\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}nach{\begin{pmatrix}3&2&4&1\\1&2&3&4\end{pmatrix}}={\begin{pmatrix}3&2&4&1\\1&2&3&4\end{pmatrix}}nach{\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}={\begin{pmatrix}1&2&3&4\\1&2&3&4\end{pmatrix}}$

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 ... )

Siehe auch