Zyklische Permutation

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Graph einer zyklischen Permutation der Zahlen von 1 bis 8

Eine zyklische Permutation, kurz Zyklus oder Zykel (von griechisch κύκλος Kreis), ist in der Kombinatorik und der Gruppentheorie eine Permutation, die bestimmte Elemente einer Menge im Kreis vertauscht und die übrigen festhält. Das erste Element des Zyklus wird dabei auf das zweite abgebildet, das zweite Element auf das dritte, und so weiter bis hin zum letzten Element, das wieder auf das erste abgebildet wird. Eine zyklische Permutation, bei der genau zwei Elemente vertauscht werden, heißt Vertauschung oder Transposition. Eine Vertauschung, die in einer geordneten Menge aufeinander folgende Elemente vertauscht, wird Nachbarvertauschung oder Nachbartransposition genannt.

Zyklische Permutationen weisen eine Reihe besonderer Eigenschaften auf. So ist die Verkettung zweier zyklischer Permutationen kommutativ, wenn diese disjunkte Träger besitzen. Die inverse Permutation einer zyklischen Permutation ist immer ebenfalls zyklisch. Weiter ergeben beliebige Potenzen einer zyklischen Permutation, deren Länge eine Primzahl ist, wieder zyklische Permutationen. Die zyklischen Permutationen fester Länge bilden zudem Konjugationsklassen der symmetrischen Gruppe aller Permutationen.

Jede zyklische Permutation kann in einzelne Transpositionen zerlegt werden und weist daher genau dann ein gerades Vorzeichen auf, wenn ihre Länge ungerade ist. Jede Permutation kann wiederum als Verkettung paarweise disjunkter Zyklen geschrieben werden, was in der Zykelschreibweise von Permutationen genutzt wird. Die Ordnung einer Permutation entspricht dann dem kleinsten gemeinsamen Vielfachen der Längen dieser Zyklen. Zyklische Permutationen mit großer Zykellänge spielen eine wichtige Rolle bei der Konstruktion von Pseudozufallszahlengeneratoren.

Definition[Bearbeiten]

Ist S_n die symmetrische Gruppe aller Permutationen der Menge \{ 1, \ldots , n \}, dann heißt eine Permutation \pi = ( \pi(1), \pi(2), \ldots , \pi(n) ) \in S_n zyklisch mit der Länge k oder k-Zyklus, wenn sie eine Liste von k \leq n paarweise verschiedenen Zahlen i_1, i_2, \ldots , i_k \in \{ 1, \ldots , n \} im Kreis vertauscht, das heißt

i_1 \mapsto i_2 \mapsto \ldots \mapsto i_k \mapsto i_1,

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 \}.

Die Menge \{ i_1, \ldots , i_k \} heißt der Träger oder die Bahn von \pi. Zyklische Permutationen der Länge zwei werden Vertauschungen oder Transpositionen genannt. Gilt bei einer Vertauschung | i_1 - i_2 | = 1, so spricht man von einer Nachbarvertauschung. Allgemeiner können auch Permutationen beliebiger endlicher Mengen, beispielsweise Alphabete, betrachtet werden, zur Analyse der mathematischen Eigenschaften kann man sich jedoch auf die ersten n natürlichen Zahlen beschränken.

Notation[Bearbeiten]

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

\pi_{i_1, i_2, \ldots , i_k}

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

( i_1 ~ i_2 ~ \ldots ~ i_k )

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

\pi_{i_1, i_2, \ldots , i_k} = \pi_{i_2, \ldots , i_k, i_1} = \ldots = \pi_{i_k, i_1, \ldots , i_{k-1}}

oder

( 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. Oft gesetzte Konvention ist aber, für i_1 die kleinste oder die größte Zahl des Zyklus zu wählen.

Beispiele[Bearbeiten]

Zyklische Permutationen in S4
Länge Zyklische Permutationen Anzahl
1 id 1
2 (1 2), (1 3), (1 4),
(2 3), (2 4), (3 4)
6
3 (1 2 3), (1 2 4), (1 3 2), (1 3 4),
(1 4 2), (1 4 3), (2 3 4), (2 4 3)
8
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)
6

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 (also eine Transposition), bei der die Zahlen 2 und 4 vertauscht werden und die Zahlen 1 und 3 festgehalten werden. 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 \operatorname{id}, die alle Zahlen unverändert lässt. In der symmetrischen Gruppe S_4 finden sich die in der nebenstehenden Tabelle aufgeführten zyklischen Permutationen. Von den 24 Permutationen in S_4 sind demnach nur drei Permutationen nichtzyklisch, nämlich diejenigen, die jeweils zwei Paare von Zahlen vertauschen.

Eigenschaften[Bearbeiten]

Anzahl[Bearbeiten]

Anzahl der k-Zyklen in Sn
{}_{n} \! \diagdown \!\! {}^{k} 1 2 3 4 5 6 Summe
1 1 1
2 1 1 2
3 1 3 2 6
4 1 6 8 6 21
5 1 10 20 30 24 85
6 1 15 40 90 144 120 410

In der Menge der n! verschiedenen Permutationen der Zahlen \{ 1, \ldots , n \} gibt es genau (n-1)! viele n-Zyklen. Jeder Permutation in Tupelschreibweise (i_1, i_2, \ldots , i_n) entspricht nämlich ein n-Zyklus (i_1 ~ i_2 ~ \ldots ~ i_n), der wiederum auf n verschiedene Weisen geschrieben werden kann. Bezeichnet nun allgemein Z_{n,k} die Menge der k-Zyklen in S_n, dann gilt für k = 2, \ldots , n

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

denn es gibt \tbinom nk Möglichkeiten, k von n Zahlen auszuwählen. Für die Gesamtmenge Z_n aller zyklischen Permutationen in S_n inklusive der identischen Permutation gilt damit:

| Z_n | = 1 + \sum_{k=2}^n \binom nk (k-1)!    (Folge A121726 in OEIS)

Kommutativität[Bearbeiten]

Im Allgemeinen ist die Hintereinanderausführung zweier zyklischer Permutationen nicht kommutativ. Besitzen 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 \} \cap \{ j_1, \ldots , j_l \} = \emptyset,

dann lässt sich ihre Reihenfolge bei der 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}.

Zyklische Permutationen mit disjunkten Trägern werden auch disjunkte Zyklen genannt.

Abgeschlossenheit und Inverse[Bearbeiten]

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 Z_n 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}.

Die inverse Permutation einer Transposition ist damit wieder die gleiche Transposition.

Potenzen[Bearbeiten]

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. Die m-te Potenz einer zyklischen Permutation der Länge k ist genau dann selbst wieder zyklisch, wenn m und k teilerfremd sind. Speziell ergibt die k-malige Anwendung einer zyklischen Permutation \pi \in Z_{n,k} die identische Permutation, also

\pi^k = \operatorname{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 ist. Diese Untergruppe ist isomorph zur zyklischen Gruppe C_k und besteht genau dann ausschließlich aus zyklischen Permutationen, wenn k eine Primzahl ist.

Konjugation[Bearbeiten]

Für eine zyklische Permutation

\pi = (i_1 ~ i_2 ~ \ldots ~ i_k) \in Z_{n,k}

berechnet sich die Konjugation mit einer beliebigen Permutation \sigma \in S_n zu

\sigma \circ \pi \circ \sigma^{-1} = \bigl(\sigma(i_1) ~ \sigma(i_2) ~ \ldots ~ \sigma(i_k)\bigr),

sie ergibt also wiederum einen k-Zyklus. Die Menge Z_{n,k} bildet dabei für jedes k \in \{1,\dotsc,n\} eine Konjugationsklasse der Gruppe S_n.

Zerlegungen[Bearbeiten]

Zerlegung von Zyklen in Teilzyklen[Bearbeiten]

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 Teilzyklen 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. Für das Vorzeichen einer zyklischen Permutation der Länge k gilt damit

\operatorname{sgn}(\pi_{i_1, \ldots , i_k}) = \operatorname{sgn}(\pi_{i_1,i_2}) \cdot \ldots \cdot \operatorname{sgn}(\pi_{i_{k-1},i_k}) = (-1)^{k-1},

da Transpositionen immer ein ungerades Vorzeichen haben. Eine zyklische Permutation ist also genau dann gerade, wenn ihre Länge ungerade ist.

Beispiel

Die zyklische Permutation \pi_{1423} \in S_4 der Länge vier lässt sich durch

\pi_{1423} = \pi_{14} \circ \pi_{42} \circ \pi_{23}

in drei Transpositionen zerlegen und ist demnach ungerade.

Zerlegung von Permutationen in Zyklen[Bearbeiten]

Graph einer Permutation der Zahlen von 1 bis 7, die in drei disjunkte Zyklen zerfällt

Jede Permutation \pi \in S_n lässt sich eindeutig (bis auf Vertauschung der Faktoren) als Verkettung von k \leq n paarweise disjunkten Zyklen darstellen. Das heißt es gilt

\pi = \pi_{I_1} \circ \ldots \circ \pi_{I_k}

mit paarweise disjunkten Trägern I_j = \{ i_{j,1}, \ldots , i_{j,n_j} \} für j=1, \ldots , k, wobei n_1 + \ldots + n_k = n ist. Die Stirling-Zahlen erster Art s_{n,k} geben dabei an, wie viele Permutationen in S_n als Verkettung von genau k 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_k dieser Zyklen. Weiter ergibt sich das Vorzeichen einer Permutation aus der Zahl der Zyklen gerader Länge.

Beispiel

Die Permutation

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

zerfällt in die drei disjunkten Zyklen

\pi = \pi_{134} \circ \pi_{26} \circ \pi_5

und hat damit die Ordnung \operatorname{kgV}(3,2,1) = 6. Da nur einer der drei Zyklen eine gerade Länge hat, ist die Permutation ungerade.

Anwendungen[Bearbeiten]

Zyklische Permutationen mit großer Zykellänge spielen eine wichtige Rolle bei der Konstruktion von Pseudozufallszahlengeneratoren. Die maximale Periode eines solchen Zufallszahlengenerators entspricht der Anzahl der möglichen Zustände des Generators. Bei einfachen rekursiven Generatoren der Form

x_{i+1} = f(x_i)

mit f \colon \{ 0, \ldots, m-1 \} \to \{ 0, \ldots, m-1 \} ist die Zahl der möglichen Zustände gerade m. Die Periode eines solchen Generators ist genau dann maximal, wenn die Funktion f eine zyklische Permutation der Länge m der Menge \{ 0, \ldots, m-1\} darstellt. Im Fall von linearen Kongruenzgeneratoren der Art

x_{i+1} = a x_i + b \mod m

gibt der Satz von Knuth hinreichende und notwendige Bedingungen an die Parameter a, b und m für die Maximalität der Periodenlänge.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

Weblinks[Bearbeiten]