From 45794fb198c8fac02b5c82b6ac3f1e17bac1075e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Tue, 19 Jan 2021 22:08:40 +0100 Subject: =?UTF-8?q?Permutationen=20hinzugef=C3=BCgt?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/chapters/50-permutationen/endlich.tex | 288 +++++++++++++++++++++++++++++ 1 file changed, 288 insertions(+) (limited to 'buch/chapters/50-permutationen/endlich.tex') 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. + + -- cgit v1.2.1