scattered-lenity

Permutationen

part of [[math2]]

Permutationen $S_n$ ::

Eine Permutation ist eine bijektive Abbildung einer endlichen Menge auf sich selbst.

I.A. verwendet man die Menge $\{1,\dots ,n\}\in \mathbb{N}$ und schreibt die Permutation wie folgt: $\sigma :\{1,\dots ,n\}⟹\{1,\dots ,n\}$ | $i⟶\sigma (i)$

Als Wertetabelle können wir eine Matrix nutzen : $\sigma \left[\begin{array}{cccccc}1& 2& 3& 4& \dots & n\\ \sigma 1& \sigma (2)& \sigma 3& \sigma 4& \dots & n\end{array}\right]$

Mit $S_n$ bezeichnen wir die Menge aller Permutationen von einer gegebenen endlichen Menge $\{1,2,\dots ,n\}n\in \mathbb{N}$

Beispiel ::

Sei $X=\{1,2,3,4\}$ also $n=4$ $\sigma \left[\begin{array}{c}1,2,3,4\\ 2,3,1,4\end{array}\right]$ oder auch $\tau \left[\begin{array}{c}1,2,3,4\\ 4,3,2,1\end{array}\right]$ Beide dieser Abbildungen sind $\in S_n$ –> Sie sind Teil der Menge aller Permutationen der Menge!

Identische Abbildung :

Bilder auch einfach die Identität der Menge : $\sigma \left[\begin{array}{c}1,2,3,4\\ 1,2,3,4\end{array}\right]\in S_n$

Ordnung einer Permutation :

Die Ordnung einer Permutation ist bestimmt, mit der Menge an Hintereinanderausführungen der Permutation auf sich selbst, sodass die Identität erreicht wird. Dabei ist der Ausgangszustand schon mit Ordnung 1 gesetzt wird. Sei $M=\left[\begin{array}{c}1,2,3,4\\ 1,2,4,3,5\end{array}\right]$ Wenn wir jetzt die Ordnung finden möchten, dann wenden wir die Permutation k-mal auf sich selbst an: $\left[\begin{array}{c}1,2,3,4,5\\ 1,2,4,3,5\\ 1,2,3,4,5\end{array}\right]$ Wir haben hier also insgesamt zweimal die Permutation angewandt, um die Identität zu bestimmen. Die Ordnung ist 2

Produkt von Permutationen :

Wir definieren auf $S_n$ eine Verknüpfung $\circ$ über die Hintereinanderausführung - Komposition von zwei Abbildungen. Das heißt $\sigma ,\tau \in {\S }_n$: Sei dann die Verknüpfung: $(\sigma \circ \tau )(i):=\sigma (\tau (i))\forall i\in \{1,\dots ,n\}$ Unter der Betrachtung führen wir demnach zuerst $\tau$ mit dem Argument $i$ aus und anschließend $\sigma$ –

Umgangssprachlich : Somit wird das, was näher zum Argument ist, zuerst ausgeführt

Abgeschlossenheit von $S_n$

Die definierte Menge aller Permutationen $S_N$ ist bezüglich der Verknüpfung $\circ$ abgeschlossen. Die Verknüpfung zweier Permutationen ergibt wieder eine Permutation in dem gegebenen Universum. Das kommt daher, dass die Komposition von bijektiven Abbildungen wieder bijektiv ist, siehe [[math1_abbildungen |Abbildungen]]]

Beispiele von Verknüpfungen ::

Sei $\sigma \left[\begin{array}{c}1,2,3\\ 2,3,1\end{array}\right]$ und $\tau \left[\begin{array}{c}1,2,3\\ 2,1,3\end{array}\right]$

Die Komposition beider Permutationen wird folgend gebildet : $\sigma \circ \tau =\left[\begin{array}{c}1,2,3\\ 2,1,3\\ 3,2,1\end{array}\right]$ –> Wir betrachten also zuerst $\tau$ bilden da die passende Verknüpfung und anschließend “setzen” wir den erhaltenen Wert dann in die Permutation $sigma$ Dabei ist die Verknüpfung nicht Kommutativ!, denn $\tau \circ \sigma =\left[\begin{array}{c}1,2,3\\ 2,3,1\\ 1,3,2\end{array}\right]$

$(S_n,\circ )$ als (symmetrische) Gruppe :

Das Tupel $(S_n,\circ )$ entspricht für $\forall n\in \mathbb{N}$ einer Gruppe, genauer wird sie als symmetrische Gruppe definiert.

Für das Tupel gelten also die drei Gruppenaxiome [[math2_gruppen#Definition:]]

Diese ist für $n\ge 3$ nicht abelsch.

Beweis symmetrischer Gruppe :

das Assoziativgesetz gilt für die Komposition $\circ$ : $((\sigma \circ \tau )\pi )(i)=\sigma (\tau (\pi (i)))=\sigma \circ (\tau \circ \pi )(i)\forall i\in \{1,\dots ,n\}$

Weiterhin gelte die Existenz eines neutralen Elements : $ϵ\left[\begin{array}{c}1,2,\dots ,n\\ 1,2,\dots ,n\end{array}\right]$ also gilt ferner : $ϵ(i)=i$, da es sich um die Identitätspermutation handelt. Daraus folgt : $(\sigma \circ ϵ)(i)=\sigma (ϵ(i))=\sigma (i)$ und weiterhin : $(ϵ\circ \sigma )(i)=ϵ(\sigma (i))=\sigma (i)\forall i$ Allgemein folgt: $\sigma \circ ϵ=ϵ\circ \sigma =\sigma \forall \sigma \in S_n$

Zur Betrachtung des inversen Elements: $\sigma =\left[\begin{array}{c}1,\dots ,n\\ \sigma (1),\dots ,\sigma (n)\end{array}\right]\in S_n$ Definieren wir ein Inverses : ${\sigma }^{-1}$ ${\sigma }^{-1}=\sigma (1)⟼1$ und $\sigma (n)⟼n$ Dann gilt dafür : $\sigma \circ {\sigma }^{-1}={\sigma }^{-1}\circ \sigma$, also $\left[\begin{array}{c}1,\dots ,n\\ 1,\dots ,n\end{array}\right]=ϵ$

Weiterhin gilt nicht die Kommutativität, wie, wir sie zuvor zeigten.

Beispiele :

$\sigma \left[\begin{array}{c}1,2,3,4\\ 4,1,2,3\end{array}\right],\tau =\left[\begin{array}{c}1,2,3,4\\ 2,4,1,3\end{array}\right]\in S_4$ $⟹\sigma \circ \tau =\left[\begin{array}{c}1,2,3,4\\ 1,3,4,2\end{array}\right]$, denn $\left[\begin{array}{c}1,2,3,4\\ 2,4,1,3\\ 1,3,4,2\end{array}\right]$ Umgekehrt folgt: $\tau \circ \sigma$ $⟹\left[\begin{array}{c}1,2,3,4\\ 3,2,4,1\end{array}\right]\in S_4$ , denn auch da folgt : $\left[\begin{array}{c}1,2,3,4\\ 4,1,2,3\\ 3,2,4,1\end{array}\right]$

${\sigma }^{-1}\left[\begin{array}{c}1,2,3,4\\ 2,3,4,1\end{array}\right]$ –> am Ende also nur die Permutation von $\sigma$ oben, aber invertiert / vertauscht betrachtet! somit folgt für ${\tau }^{-1}\left[\begin{array}{c}1,2,3,4\\ 3,1,4,2\end{array}\right]$

Für welche Permutation $x\in s_4$ gilt $\sigma \circ X=\tau$ ? Mit Satz 1.6 können wir folgern: $ax=b⟹x=a^{-1}b$, also $x={\sigma }^{-1}\circ \tau =\left[\begin{array}{c}1,2,3,4\\ 3,1,2,4\end{array}\right]$ Ebenso gilt dann auch : $x\circ \sigma =\tau$ mit $x=\tau \circ {\sigma }^{-1}=\left[\begin{array}{c}1,2,3,4\\ 4,1,3,2\end{array}\right]$

.