Permutationen hinzugefügt

1 files changed, 288 insertions, 0 deletions

diff --git a/buch/chapters/50-permutationen/endlich.tex b/buch/chapters/50-permutationen/endlich.tex
index 71cc991..9514f88 100644
--- a/buch/chapters/50-permutationen/endlich.tex
+++ b/buch/chapters/50-permutationen/endlich.tex
@@ -6,3 +6,291 @@
 \section{Permutationen einer endlichen Menge
 \label{buch:section:permutationen-einer-endlichen-menge}}
 \rhead{Permutationen}
+Eine endliche Anzahl $n$ von Objekten können auf $n!$ Arten angeordnet
+werden.
+Als Objektmenge nehmen wir $[n] = \{ 1,\dots,n\}$.
+Die Operation, die die Objekte in eine bestimmte Reihenfolge bringt,
+ist eine Abbildung $\sigma\colon[n]\to[n]$.
+Eine Permutation ist eine umkehrbare Abbildung $[n]\to[n]$.
+Die Menge $S_n$ aller umkehrbaren Abbildungen $[n]\to[n]$
+mit der Verknüpfung von Abbildungen als Operation heisst die
+die {\em symmetrische Gruppe}.
+Die identische Abbildung $\sigma(x)=x$ ist das {\em neutrale
+Element} der Gruppe $S_n$ und wir auch mit $e$ bezeichnet.
+
+\subsection{Permutationen als $2\times n$-Matrizen}
+Eine Permutation kann als $2\times n$-Matrix geschrieben werden:
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+\def\sx{0.8}
+\def\sy{1}
+\begin{scope}[xshift=-3cm]
+\foreach \x in {1,...,6}{
+	\node at ({(\x-1)*\sx},\sy) [above] {$\tiny\x$};
+	\fill ({(\x-1)*\sx},\sy) circle[radius=0.05];
+	\fill ({(\x-1)*\sx},0) circle[radius=0.05];
+}
+\draw[->] (0,\sy) to[out=-70,in=110] (\sx,0);
+\draw[<-] (0,0) to[out=70,in=-110] (\sx,\sy);
+\draw[->] ({2*\sx},\sy) -- ({2*\sx},0);
+\draw[->] ({3*\sx},\sy) to[out=-70,in=110] ({4*\sx},0);
+\draw[->] ({4*\sx},\sy) to[out=-70,in=110] ({5*\sx},0);
+\draw[->] ({5*\sx},\sy) to[out=-110,in=70] ({3*\sx},0);
+\end{scope}
+\node at (2.4,{\sy/2}) {$\mathstrut=\mathstrut$};
+\node at (5,{\sy/2}) {$\displaystyle
+\renewcommand{\arraystretch}{1.4}
+\begin{pmatrix}
+1&2&3&4&5&6\\
+2&1&3&5&6&4
+\end{pmatrix}
+$};
+\end{tikzpicture}
+\end{center}
+Das neutrale Element hat die Matrix
+\[
+e = \begin{pmatrix}
+1&2&3&4&5&6\\
+1&2&3&4&5&6
+\end{pmatrix}
+\]
+aus zwei identischen Zeilen.
+
+Die Verknüpfung zweier solcher Permutationen kann leicht graphisch
+dargestellt werden: dazu werden die beiden Permutationen
+untereinander geschrieben und Spalten der zweiten Permutation
+in der Reihen folge der Zahlen in der zweiten Zeile der ersten
+Permutation angeordnet.
+Die zusammengesetzte Permutation kann dann in der zweiten Zeile
+der zweiten Permutation abgelesen werden:
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+\begin{scope}[xshift=-4.5cm]
+\node at (0,0) {$\displaystyle
+\sigma_1=\begin{pmatrix}
+1&2&3&4&5&6\\
+2&1&3&5&6&4
+\end{pmatrix}$};
+\node at (0,-1) {$\displaystyle
+\sigma_2=\begin{pmatrix}
+1&2&3&4&5&6\\
+3&4&5&6&1&2
+\end{pmatrix}
+$};
+\end{scope}
+\begin{scope}
+\node at (0,0) {$\displaystyle
+\begin{pmatrix}
+1&2&3&4&5&6\\
+2&1&3&5&6&4
+\end{pmatrix}$};
+\node at (0,-1) {$\displaystyle
+\begin{pmatrix}
+2&1&3&5&6&4\\
+4&3&5&1&2&6
+\end{pmatrix}
+$};
+
+\end{scope}
+\begin{scope}[xshift=4.5cm]
+\node at (0,-0.5) {$\displaystyle
+\sigma_2\sigma_1=\begin{pmatrix}
+1&2&3&4&5&6\\
+4&3&5&1&2&6
+\end{pmatrix}
+$};
+\end{scope}
+\end{tikzpicture}
+\end{center}
+Die Inverse einer Permutation kann erhalten werden, indem die beiden
+Zeilen vertauscht werden und dann die Spalten wieder so angeordnet werden,
+dass die Zahlen in der ersten Zeile ansteigend sind:
+\[
+\sigma = \begin{pmatrix}
+1&2&3&4&5&6\\
+2&1&3&5&6&4
+\end{pmatrix}
+\qquad\Rightarrow\qquad
+\sigma^{-1}
+=
+\begin{pmatrix}
+2&1&3&5&6&4\\
+1&2&3&4&5&6
+\end{pmatrix}
+=
+\begin{pmatrix}
+1&2&3&4&5&6\\
+2&1&3&6&4&5
+\end{pmatrix}.
+\]
+
+\subsection{Zyklenzerlegung}
+Eine Permutation $\sigma\in S_n$ kann auch mit sogenanten Zyklenzerlegung
+analysiert werden.
+Zum Beispiel:
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+\begin{scope}[xshift=-3cm]
+\node at (0,0) {$\displaystyle
+\sigma=\begin{pmatrix}
+{\color{red}1}&{\color{red}2}&{\color{darkgreen}3}&{\color{blue}4}&{\color{blue}5}&{\color{blue}6}\\
+{\color{red}2}&{\color{red}1}&{\color{darkgreen}3}&{\color{blue}5}&{\color{blue}6}&{\color{blue}4}
+\end{pmatrix}$};
+\end{scope}
+\node at (0,0) {$\mathstrut=\mathstrut$};
+\begin{scope}[xshift=1.5cm]
+\coordinate (A) at (0,0.5);
+\coordinate (B) at (0,-0.5);
+\draw[->,color=red] (A) to[out=-20,in=20] (0,-0.5);
+\draw[->,color=red] (B) to[out=160,in=-160] (0,0.5);
+\node at (A) [above] {$\tiny 1$};
+\node at (B) [below] {$\tiny 2$};
+\fill (A) circle[radius=0.05];
+\fill (B) circle[radius=0.05];
+
+\coordinate (C) at (1.5,0.25);
+\node at (C) [above] {$\tiny 3$};
+\draw[->,color=darkgreen] ({1.5+0.01},0.25) to[out=-10,in=-170] ({1.5-0.01},0.25);
+\draw[color=darkgreen] (1.5,{0.25-0.3}) circle[radius=0.3];
+\fill (C) circle[radius=0.05];
+
+\def\r{0.5}
+\coordinate (D) at ({3.5+\r*cos(90)},{0+\r*sin(90)});
+\coordinate (E) at ({3.5+\r*cos(210)},{0+\r*sin(210)});
+\coordinate (F) at ({3.5+\r*cos(330)},{0+\r*sin(330)});
+\node at (D) [above] {$\tiny 4$};
+\node at (E) [below left] {$\tiny 5$};
+\node at (F) [below right] {$\tiny 6$};
+\draw[->,color=blue] (D) to[out=180,in=120] (E);
+\draw[->,color=blue] (E) to[out=-60,in=-120] (F);
+\draw[->,color=blue] (F) to[out=60,in=0] (D);
+\fill (D) circle[radius=0.05];
+\fill (E) circle[radius=0.05];
+\fill (F) circle[radius=0.05];
+
+\end{scope}
+\end{tikzpicture}
+\end{center}
+
+\begin{definition}
+Ein Zyklus $Z$ ist eine unter $\sigma$ invariante Teilmenge von $[n]$
+minimaler Grösse.
+Die Zyklenzerlegung ist eine Zerlegung von $[n]$ in Zyklen
+\[
+[n]
+=
+\cup_{i=1}^k Z_i,
+\]
+wobei jede Menge $Z_i$ ein Zyklus ist.
+\end{definition}
+
+Der folgende Algorithmus findet die Zyklenzerlegung einer Permutation.
+
+\begin{satz}
+Sei $\sigma\in S_n$ eine Permutation. Der folgende Algorithmus findet
+die Zyklenzerlegung von $\sigma$:
+\begin{enumerate}
+\item
+$i=1$
+\item
+Wähle das erste noch nicht verwendete Element
+\[
+s_i=\min\biggl( [n] \setminus \bigcup_{j< i} Z_j\biggr)
+\]
+\item
+Bestimme alle Elemente, die aus $s_i$ durch Anwendung von $\sigma$
+entstehen:
+\[
+Z_i
+=
+\{ s_i, \sigma(s_i), \sigma(\sigma(s_i)), \dots \}
+=
+\{\sigma^k(s_i)\;|\; k\ge 0\}.
+\]
+\item
+Falls $\bigcup_{j\le i} Z_j\ne [n]$, erhöhe $i$ um $1$ und fahre 
+weiter bei 2.
+\end{enumerate}
+\end{satz}
+
+Mit Hilfe der Zyklenzerlegung von $\sigma$ lassen sich auch
+gewisse Eigenschaften von $\sigma$ ableiten.
+Sei also $[n] = Z_1\cup\dots\cup Z_k$ die Zyklenzerlegung.
+Für jedes Element $x\in S_i$ gilt $\sigma^{|S_i|}(x) = x$.
+Die kleinste Zahl $m$, für die $\sigma^m=e$ ist, das kleinste
+gemeinsame Vielfache der Zyklenlängen:
+\[
+m = \operatorname{kgV} (|Z_1|,|Z_2|,\dots,|Z_k|).
+\]
+
+\subsection{Konjugierte Elemente in $S_n$}
+Zwei Elemente $g_1,g_2\in G$ einer Gruppe heissen konjugiert, wenn
+es ein Element $c\in G$ gibt derart, dass $cg_1c^{-1}=g_2$.
+Bei Matrizen hat dies bedeutet, dass die beiden Matrizen durch
+Basiswechsel auseinander hervorgehen.
+Dasselbe lässt sich auch im Kontext der symmetrischen Gruppe sagen.
+
+Seien $\sigma_1$ und $\sigma_2$ zwei konjugierte Permutationen in $S_n$.
+Es gibt also eine Permutation $\gamma\in S_n$ derat, dass
+$\sigma_1=\gamma\sigma_2\sigma^{-1}$ oder $\gamma^{-1}\sigma_1\gamma=\sigma_2$.
+Dann gilt auch für die Potenzen
+\begin{equation}
+\sigma_1^k = \gamma\sigma_2^k\gamma^{-1}.
+\label{buch:permutationen:eqn:konjpot}
+\end{equation}
+Ist $Z_i$ ein Zyklus von $\sigma_2$ und $x\in Z_i$, dann ist
+$Z_i = \{ x,\sigma_2(x),\sigma_2^2(x),\dots\}$.
+Die Menge $\gamma(Z_i)$ besteht dann aus dem Elementen
+$\gamma(Z_i)=\{\gamma(x),\gamma(\sigma_2(x)),\gamma(\sigma_2^2(x)),\dots\}$.
+Aus der Formel~\eqref{buch:permutationen:eqn:konjpot} folgt
+$\sigma_1^k\gamma = \gamma\sigma_2^k$, also
+\[
+\gamma(Z_i)
+=
+\{\gamma(x),\sigma_1(\gamma(x)),\sigma_1^2(\gamma(x)),\dots\},
+\]
+Also ist $\gamma(Z_i)$ ein Zyklus von $\sigma_1$.
+Die Permutation $\gamma$ bildet also Zyklen von $\sigma_2$ auf Zyklen
+von $\sigma_1$ ab.
+Es folgt daher der folgende Satz:
+
+\begin{satz}
+Sind $\sigma_1,\sigma_2\in S_n$ konjugiert $\sigma_1=\gamma\sigma_2\gamma^{-1}$
+mit dem $\gamma\in S_n$.
+Wenn $Z_1,\dots,Z_k$ die Zyklen von $\sigma_2$ sind, dann sind 
+$\gamma(Z_1),\dots,\gamma(Z_k)$ die Zyklen von $\sigma_1$.
+\end{satz}
+
+Die Zyklenzerlegung kann mit der Jordan-Normalform \ref{XXX}
+einer Matrix verglichen werden.
+Durch einen Basiswechsel, welcher durch eine ``Konjugation''
+von Matrizen ausgedrückt wir, kann die Matrix in eine besonders 
+übersichtliche Form gebracht werden.
+Wenn $\sigma$ die Zyklenzerlegung $Z_1,\dots,Z_k$ mit Zyklenlängen
+$l_i=|Z_i|$, dann kann man die Menge $[n]$ wie folgt in Teilmengen
+\begin{align*}
+X_1 &= \{1,\dots, l_1\},
+\\
+X_2 &= \{l_1+1,\dots,l_1+l_2\},
+\\
+X_i &= \{l_1+\dots+l_{i-1}+1,\dots, l_1+\dots+l_i\}
+\\
+X_k &= \{l_1+\dots+l_{k-1}+1,\dots n\}
+\end{align*}
+zerlegen.
+Sei $\sigma_2$ die Permutation, die in jeder der Mengen $X_i$ durch
+zyklische Vertauschung der Elemente wirkt.
+Indem man die Elemente von $Z_i$ in der Reihenfolge, in der sie durch
+$\sigma_1$ erreicht werden, auf die Elemente $X_i$ abbildet, findet
+man eine Permutation, die Zyklen von $\sigma_1$ in Zyklen von $\sigma_2$
+überführt.
+
+\begin{satz}
+Wenn zwei Elemente $\sigma_1,\sigma_2\in S_n$ Zyklenzerlegungen mit den
+gleichen Zyklenlängen haben, dann sind sie konjugiert.
+\end{satz}
+
+Ein Element $\sigma\in S_n$ ist also bis auf eine Permutation
+vollständig durch die Länge der Zyklen von $\sigma$ charakterisiert.
+
+