Permutationen und Transpositionen

Permutation

Definition

Es sei M eine endliche Menge. Eine bijektive Selbstabbildung von M heißt Permutation. Die Menge $S_M$ der Permutationen von M ist eine Gruppe bezüglich der Verkettung $\circ$ von Abbildungen und heißt symmetrische Gruppe von M.

Quelle: Skript von Herrn Prof. Dr. Leuzinger, KIT

Allgemeines

Es ist nun egal, ob ich die Permutationen von {1, 2, 3} oder {42, 1337, ABC} anschaue. Es sind einfach nur drei Objekte, die unterscheidbar sind. Um es einfacher zu machen, gehen wir nun von den Objekten {1, 2, ..., m} aus. Alle Permutationen dieser Objekte bilden eine Gruppe. Diese nennen wir \(S_m\).

Ein einzelnes Element aus \(S_m\) wird meist \(\pi\) oder \(\sigma\) genannt, also \(\pi \in S_m\). Da \(\pi\) eine Permutation ist, ist es insbesondere eine bijektive Selbstabbildung, also:

$$M = {1, ..., m}$$
$$\pi: M \rightarrow M$$
$$i \mapsto \pi(i)$$

Kurz schreibt man auch: (\pi =

\begin{pmatrix} 1 & 2 & 3 & ... & m\\ \pi(1) & \pi(2) & \pi(3) & ... & \pi(m) \end{pmatrix}

)

Anzahl der Permutationen

Wenn ich n Elemente habe, die ich auf n Plätze verteilen muss: Wie viele unterschiedliche Zuordnungen von Elementen zu den Plätzen gibt es?

Die Antwort ist \(n! = 1 \cdot 2 \cdot ... (n - 1) \cdot n = \prod_{i=1}^n i\). Für das erste Element sind \(n\) Plätze frei. Das Zweite kann nur noch auf \((n-1)\) Plätze verteilt werden, ... , das letzte hat nur noch einen Platz zur "Auswahl".

Erzeugung der Permutationen

Angenommen, man muss in einem Test \(S_3\) explizit angeben. Wie geht das?

Nun, zu erst erzeugt man alle Permutationen. Dafür rechnet man sich die Anzahl aus. Es gibt 3 Elemente, also \(3 \cdot 2 \cdot 1 = 6\) Permutationen: 1. _ 2. _ 3. _ 4. _ 5. _ 6. _ _ _

Nun zuerst zum ersten Element, der 1. Diese kann ich an die erste, die zweite oder die dritte Stelle verschieben. Also: 1. 1 _ 2. 1 _ 3. _ 1 4. _ 1 5. _ 1 6. _ 1

Nun zum zweiten Element, der 2. Wieder das gleiche Prinzip: Und nun nur noch das letzte Einfüllen:
1. 1 2 _ 2. 1 _ 2 3. 2 1 _ 4. _ 1 2 5. 2 _ 1 6. _ 2 1 1. 1 2 3 2. 1 3 2 3. 2 1 3 4. 3 1 2 5. 2 3 1 6. 3 2 1

Und nun noch als Menge in der mathematischen Schreibweise aufschreiben:

(S_3 = \left { \underbrace{

\begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}

}{\pi_1}, \underbrace{

\begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}
}, \underbrace{

\begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}

}{\pi_3}, \underbrace{

\begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}
}, \underbrace{

\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}

}{\pi_5}, \underbrace{

\begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}
} \right })

Verkettung

Was passiert, wenn ich die Permuation \(\pi_2\) mit der Permutation \(\pi_3\) verkette? Also: (\pi_x(i) = \pi_2(\pi_3(i)) =

\begin{pmatrix}1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix}

= \pi_6)

Aber:

(\pi_y(i) = \pi_3(\pi_2(i)) =

\begin{pmatrix}1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix}

= \pi_5 \neq \pi_6)

Die Verkettung von Permutationen ist also nicht kommutativ!

Es ergibt sich insgesamt folgende Verknüfungstabelle (gelesen wird: Zeile zuerst, Spalte später):

  \(\pi_1\) \(\pi_2\) \(\pi_3\) \(\pi_4\) \(\pi_5\) \(\pi_6\)
\(\pi_1\) \(\pi_1\) \(\pi_2\) \(\pi_3\) \(\pi_4\) \(\pi_5\) \(\pi_6\)
\(\pi_2\) \(\pi_2\) \(\pi_1\) \(\pi_5\) \(\pi_6\) \(\pi_3\) \(\pi_4\)
\(\pi_3\) \(\pi_3\) \(\pi_4\) \(\pi_1\) \(\pi_2\) \(\pi_6\) \(\pi_5\)
\(\pi_4\) \(\pi_4\) \(\pi_3\) \(\pi_6\) \(\pi_5\) \(\pi_1\) \(\pi_2\)
\(\pi_5\) \(\pi_5\) \(\pi_6\) \(\pi_2\) \(\pi_1\) \(\pi_4\) \(\pi_3\)
\(\pi_6\) \(\pi_6\) \(\pi_5\) \(\pi_4\) \(\pi_3\) \(\pi_2\) \(\pi_1\)

Man sieht nun, und das finde ich durchaus erstaunlich, man landet immer wieder in \(S_3\). Durch die Verknüpfung von Permutationen kommt also immer wieder eine Permutation heraus! Das bedeutet, () ist unter dieser Verknüpfung abgeschlossen.

Man kann nun auch noch sehen, jedes Element aus \((S_3, \circ)\) ein inverses hat, da in jeder Zeile ein mal \(\pi_1\) vorkommt.

Außerdem ist \((S_3, \circ)\) assoziativ.

Kurz: \((S_3, \circ)\) ist eine Gruppe, die jedoch nicht abelsch ist.

Es wurde in der Vorlesung auch gezeigt, dass allgemein \((S_m, \circ)\) eine Gruppe ist.

Die Fehlstandszahl

Es sei $\pi \in S_m$ eine Permutation. Die Fehlstandszahl $F(\pi)$ von $\pi$ ist die (eindeutige) Anzahl der Fälle, in denen für $i < k$ gilt $\pi(i) > \pi(k)$. Die Permutationen mit gerader Fehlstandszahl $F(\pi)$ heißen gerade, die Permutationen mit ungerader Fehlstandszahl heißen ungerade.

Beispiele

(\pi_1 =

\begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}

)

hat die Fehlstandszahl 0.

(\pi_2 =

\begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}

)

hat die Fehlstandszahl 1, da \(i = 2 < 3 = k\) gilt, aber \(\pi_2(2) = 3 > 2 = \pi_2(3)\).

(\pi_3 =

\begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}

)

hat die Fehlstandszahl 1.

(\pi_4 =

\begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}

)

hat die Fehlstandszahl 2.

(\pi_5 =

\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}

)

hat die Fehlstandszahl 2.

(\pi_6 =

\begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}

)

hat die Fehlstandszahl 2.

Transposition

Eine Transposition ist eine Permutation aus $S_m$, bei der zwei verschiedene, fest gewahlte Zahlen $i, k \in \{1, 2, ..., m\}$ vertauscht werden, während alle anderen Zahlen fest bleiben. Man schreibt fur diese Transposition auch kurz $(i~k)$.

Transpositionen werden gerne mit \(\tau\) abgekürzt.

Also: \(\pi_2 = (2~3), \pi_3=(1~2), \pi_6 = (1~3)\) sind Transpositionen. \(\pi_1, \pi_4, \pi_5\) sind keine Transpositionen.

Es gilt: \(\tau \circ \tau = id\)

wir haben in der Vorlesung gezeigt:

Jede Permutation \(\pi \in S_m, m \geq 2,\) lässt sich als Verkettung von Transpositionen darstellen.

Beispiel: (\sigma =

\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 5 & 4 & 1 & 3 & 2\end{pmatrix}

= (1~6) \circ (2~5) \circ (3~4) \circ (4~6) \circ (5~6))

Gelesen wird das ganze von rechts nach links. Die Transposition \((5~6)\) wird also zuerst angewendet. Wie bei Abbildungen die verkettet werden halt auch.

Die Fehlstandszahl von \(\sigma\) ist 13 und die Anzahl der Transpositionen ist ungerade.

Interessanterweise gilt auch \(\sigma = (1~4) \circ (3~5) \circ (2~6) \circ (1~3) \circ (1~2)\). Außerdem kann man beliebig häufig eine Transposition doppelt hinzufügen, da es ja die Identität ist. Die Darstellung einer Permutation als folge von Transpositionen ist also nicht eindeutig.

Siehe auch

Wikipedia: Permutation

Published


by

Category

German posts

Tags

Contact