Zyklische Permutation

Graph einer zyklischen Permutation der Zahlen von 1 bis 8

Eine zyklische Permutation, kurz Zyklus oder Zykel (von Vorlage:GrS Kreis), ist in der Kombinatorik eine Permutation, die eine Menge von Zahlen zyklisch vertauscht. Die erste Zahl in dem Zyklus wird dabei auf die zweite abbildet, die zweite Zahl auf die dritte, und so weiter bis hin zur letzten Zahl, die wieder auf die erste abgebildet wird. Eine zyklische Permutation zweier Zahlen heißt Vertauschung oder Transposition.

Jede Permutation kann als Verkettung paarweise disjunkter Zyklen geschrieben werden, was in der Zyklusnotation von Permutationen genutzt wird. Die Ordnung einer Permutation entspricht dann dem kleinsten gemeinsamen Vielfachen der Längen dieser Zykeln. Jede zyklische Permutation und damit auch jede Permutation kann weiter in einzelne Transpositionen zerlegt werden.

Definition

Ist $S_{n}$ die symmetrische Gruppe aller Permutationen der Menge $\{1,\ldots ,n\}$, dann heißt eine Permutation

$\pi ={\begin{pmatrix}1&2&\cdots &n\\\pi (1)&\pi (2)&\cdots &\pi (n)\end{pmatrix}}\in S_{n}$

zyklisch mit der Länge $k$ oder $k$-Zyklus, wenn sie eine Liste von $k$ paarweise verschiedenen Zahlen $i_{1},i_{2},\ldots ,i_{k}\in \{1,\ldots ,n\}$ zyklisch vertauscht und alle anderen Zahlen festhält. Es muss also gelten

$\pi (i_{1})=i_{2},~\pi (i_{2})=i_{3},\ldots ,~\pi (i_{k-1})=i_{k}$   und   $\pi (i_{k})=i_{1}$

sowie

$\pi (j)=j$   für   $j\not \in \{i_{1},\ldots ,i_{k}\}$.

Notation

Neben der obigen Matrixnotation, bei der die Abbildung $\pi$ vollständig angegeben wird, kann eine zyklische Permutation auch dadurch notiert werden, dass die Liste der Zahlen, die zyklisch vertauscht werden, in Form von Indizes mittels

$\pi _{i_{1},i_{2},\ldots ,i_{k}}$

angegeben werden. Häufig wird eine zyklische Permutation auch in Zyklusnotation geschrieben, indem diese Zahlen ohne Trennzeichen in Klammern gesetzt werden:

$(i_{1}~i_{2}~\ldots ~i_{k})$

In beiden Schreibweisen wird davon ausgegangen, dass die die Gesamtzahl $n$ der Zahlen bekannt ist. Die Index- und die Zyklusnotation sind allerdings nicht eindeutig, denn die Startzahl kann innerhalb des Zyklus beliebig gewählt werden. Jeder $k$-Zyklus kann so auf $k$ verschiedene Weisen mittels

$(i_{1}~i_{2}~\ldots ~i_{k})=(i_{2}~\ldots ~i_{k}~i_{1})=\ldots =(i_{k}~i_{1}~\ldots ~i_{k-1})$

beschrieben werden. Eine häufige Konvention ist es aber, für $i_{1}$ entweder die kleinste oder die größte Zahl des Zyklus zu wählen.

Beispiele

Eine einfache zyklische Permutation der Länge drei ist

$\pi _{123}=\pi _{231}=\pi _{312}=(1~2~3)=(2~3~1)=(3~1~2)={\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}}\in S_{3}$.

Hierbei wird die Zahl $1$ auf die Zahl $2$, die Zahl $2$ auf die Zahl $3$ und die Zahl $3$ wieder auf die Zahl $1$ abgebildet.

Die Permutation

$\pi _{24}=\pi _{42}=(2~4)=(4~2)={\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}}\in S_{4}$

ist eine zyklische Permutation der Länge zwei, bei der die Zahlen $2$ und $4$ vertauscht werden und die Zahlen $1$ und $3$ festgehalten werden. Zyklische Permutationen der Länge zwei werden daher auch Vertauschungen oder Transpositionen genannt.

Jede zyklische Permutation der Länge eins

$\pi _{1}=\pi _{2}=\ldots =\pi _{n}=(1)=(2)=\ldots =(n)={\begin{pmatrix}1&2&\cdots &n\\1&2&\cdots &n\end{pmatrix}}\in S_{n}$

entspricht gerade der identischen Permutation $id$, die alle Zahlen unverändert lässt.

Eigenschaften

Anzahl

Vergleich der Zahl aller Permutationen mit der Zahl zyklischer Permutationen für wachsendes $\scriptstyle n$

In der Menge der $n!$ verschiedenen Permutationen der Zahlen $\{1,\ldots ,n\}$ gibt es genau $(n-1)!$ viele $n$-Zykel, denn jeder Permutation entspricht ein $n$-Zyklus, der wiederum auf $n$ verschiedene Weisen geschrieben werden kann. Bezeichnet nun allgemein $Z_{n,k}$ die Menge der $k$-Zykel in $S_{n}$, dann gilt für $k=2,\ldots ,n$

$|Z_{n,k}|={\binom {n}{k}}(k-1)!$    (Folge A111492 in OEIS)

denn es gibt ${\tbinom {n}{k}}$ Möglichkeiten, $k$ von $n$ Zahlen auszuwählen. Für die Gesamtmenge $Z_{n}$ aller zyklischen Permutationen in $S_{n}$ ohne die identische Permutation gilt damit:

$|Z_{n}|=\sum _{k=2}^{n}{\binom {n}{k}}(k-1)!$    (Folge A006231 in OEIS)

Beispielsweise finden sich in der symmmetrischen Gruppe $S_{4}$ die folgenden zyklischen Permutationen:

• sechs Zykel der Länge $4$: $(1~2~3~4),(1~2~4~3),(1~3~2~4),(1~3~4~2),(1~4~2~3),(1~4~3~2)$
• acht Zykel der Länge $3$: $(1~2~3),(1~3~2),(1~2~4),(1~4~2),(1~3~4),(1~4~3),(2~3~4),(2~4~3)$
• sechs Zykel der Länge $2$: $(1~2),(1~3),(1~4),(2~3),(2~4),(3~4)$

Von den $24$ Permutationen in $S_{4}$ sind demnach neben der identischen Permutation $id$ nur drei Permutationen nichtzyklisch, nämlich diejenigen, die jeweils zwei Paare von Zahlen vertauschen.

Inverse

Die Hintereinanderausführung zweier zyklischer Permutationen ist nicht notwendigerweise wieder zyklisch, wie das Beispiel

$\pi _{1234}\circ \pi _{1234}={\begin{pmatrix}1&2&3&4\\3&4&1&2\end{pmatrix}}=\pi _{13}\circ \pi _{24}$

zeigt. Daher bildet die Menge der zyklischen Permutationen keine Untergruppe der symmetrischen Gruppe $S_{n}$. Allerdings ist die inverse Permutation einer zyklischen Permutation $\pi _{i_{1},\ldots ,i_{k}}$ stets ebenfalls eine zyklische Permutation, nämlich diejenige, die die Zahlen $i_{1},\ldots ,i_{k}$ in umgekehrter Reihenfolge zyklisch vertauscht, also

$(\pi _{i_{1},\ldots ,i_{k}})^{-1}=\pi _{i_{k},\ldots ,i_{1}}$.

Potenzen

Wird eine zyklische Permutation zweimal hintereinander angewandt, so verschieben sich alle Indizes zyklisch um $2$, das heißt $i_{1}$ wird auf $i_{3}$ abgebildet, $i_{2}$ auf $i_{4}$ und so weiter bis hin zu $i_{k-1}$ auf $i_{1}$ und $i_{k}$ auf $i_{2}$. Allgemein verschieben sich durch die $m$-malige Anwendung einer zyklischen Permutation alle Indizes zyklisch um $m$. Speziell ergibt dabei die $k$-malige Anwendung einer zyklischen Permutation $\pi \in Z_{n,k}$ die identische Permutation, also

$\pi ^{k}=id$,

und die $(k+1)$-malige Anwendung ergibt wieder die Ausgangspermutation, also

$\pi ^{k+1}=\pi$.

Daher bildet die Menge

$\{\pi ,\pi ^{2},\ldots ,\pi ^{k-1},\pi ^{k}\}$

mit der Hintereinanderausführung eine Untergruppe der symmetrischen Gruppe $S_{n}$, wobei $\pi ^{k-j}$ das inverse Element zu $\pi ^{j}$ darstellt. Diese Untergruppe ist isomorph zur zyklischen Gruppe $C_{k}$ und besteht genau dann ausschließlich aus zyklischen Permutationen, wenn $k$ eine Primzahl ist.

Kommutativität

Im Allgemeinen ist die Hintereinanderausführung zweier zyklischer Permutationen nicht kommutativ. Haben allerdings zwei zyklische Permutationen $\pi _{i_{1},\ldots ,i_{k}}\in Z_{n,k}$ und $\pi _{j_{1},\ldots ,j_{l}}\in Z_{n,l}$ disjunkte Träger, gilt also

$\{i_{1},\ldots ,i_{k}\}\cup \{j_{1},\ldots ,j_{l}\}=\emptyset$,

dann lässt sich ihre Hintereinanderausführung vertauschen, das heißt es gilt

$\pi _{i_{1},\ldots ,i_{k}}\circ \pi _{j_{1},\ldots ,j_{l}}=\pi _{j_{1},\ldots ,j_{l}}\circ \pi _{i_{1},\ldots ,i_{k}}$.

Zerlegungen

Zerlegung von Zykeln

Jede zyklische Permutation der Länge $k>2$ lässt sich an einer beliebigen Stelle $l\in \{2,\ldots ,k-1\}$ mittels

$\pi _{i_{1},\ldots ,i_{k}}=\pi _{i_{1},\ldots ,i_{l}}\circ \pi _{i_{l},\ldots ,i_{k}}$

in zwei Teilzykel zerlegen. Wendet man diese Zerlegung wiederholt mit $l=2,3,\ldots ,k-1$ an, ergibt sich, dass jede zyklische Permutation der Länge $k$ mittels

$\pi _{i_{1},\ldots ,i_{k}}=\pi _{i_{1},i_{2}}\circ \cdots \circ \pi _{i_{k-1},i_{k}}$.

als Verkettung von $k-1$ Transpositionen geschrieben werden kann. Beispielsweise ist

$\pi _{4231}=\pi _{42}\circ \pi _{23}\circ \pi _{31}$.

Zerlegung allgemeiner Permutationen

Jede Permutation $\pi \in S_{n}$ lässt sich eindeutig (bis auf Vertauschung der Faktoren) als Verkettung von $s\leq n$ paarweise disjunkten zyklischen Permutationen darstellen. Das heißt es gilt

$\pi =\pi _{I_{1}}\circ \ldots \circ \pi _{I_{s}}$

mit paarweise disjunkten Indexmengen $I_{j}=\{i_{j,1},\ldots ,i_{j,n_{j}}\}$ für $j=1,\ldots ,s$, wobei $n_{1}+\ldots +n_{s}=n$ ist. Die Stirling-Zahlen erster Art geben dabei an, wie viele Permutationen in $S_{n}$ als Verkettung von genau $s$ zyklischen Permutationen geschrieben werden können. Die Ordnung einer Permutation entspricht der Ordnung der zugehörigen zyklischen Gruppe und ist damit das kleinste gemeinsame Vielfache der Längen $n_{1},\ldots ,n_{s}$ dieser Zykel. Weiter ergibt sich das Signum einer Permutation aus der Zahl der Zykel gerader Länge.

Beispielsweise zerfällt die Permutation

$\pi ={\begin{pmatrix}1&2&3&4&5&6\\3&6&4&1&5&2\end{pmatrix}}\in S_{6}$

in die drei disjunkten Zykel

$\pi =\pi _{134}\circ \pi _{26}\circ \pi _{5}=(1~3~4)(2~6)(5)$

und hat damit die Ordnung $6$ und ein ungerades Signum.

Siehe auch

• Zyklus (Graphentheorie)
• Zyklus (Funktionentheorie)

Literatur

• Albrecht Beutelspacher: Lineare Algebra. Eine Einführung in die Wissenschaft der Vektoren, Abbildungen und Matrizen. 6. Auflage. Vieweg, 2009, ISBN 3-528-56508-X. 
• Gerd Fischer: Lehrbuch der Algebra. Springer, 2007, ISBN 3-8348-0226-3. 
• Jens Carsten Jantzen, Joachim Schwermer: Algebra. Springer, 2005, ISBN 3-540-21380-5. 

Weblinks

• D.A. Suprunenko: Permutation of a set. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 1-55608-010-7 (englisch, encyclopediaofmath.org). 
• Eric W. Weisstein: Permutation Cycle. In: MathWorld (englisch).
• Cycle. In: PlanetMath. (englisch)