Symmetrische Gruppe
aus Freepedia, der freien Wissensdatenbank
Die symmetrische Gruppe Symn oder Sn besteht aus allen Permutationen einer Menge mit n Elementen, Gruppenoperation ist die Verkettung der Permutationen.
Symn besitzt n! ( n Fakultät ) Elemente. Für n > 2 ist Symn nicht kommutativ.
Inhaltsverzeichnis |
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:
<math>
\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}</math>
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:
<math>
\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}</math>
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.
Man kann per vollständiger Induktion zeigen dass man jede Permutation als Produkt von Zyklen der Länge 2 darstellen kann. Dieser Satz spielt eine theoretische Rolle in der Informatik. Er sagt aus, dass man lediglich durch sukzessives Vertauschen von je 2 Elementen eine unsortierte Folge von Elementen sortieren kann.
Beispiele
<math>\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}</math>
Für n > 2 ist die symmetrische Gruppe Symn nicht kommutativ:
- ( 2 3 1 ... ) ○ ( 2 1 3 ... ) = ( 3 2 1 ... )
- ( 2 1 3 ... ) ○ ( 2 3 1 ... ) = ( 1 3 2 ... )
