Zyklische Permutation

Grundidee und Definition

Eine zyklische Permutation, kurz Zyklus, ist eine Permutation, die ausgewählte Elemente einer Menge kreisförmig vertauscht und alle übrigen Elemente festhält. In der symmetrischen Gruppe S_n aller Permutationen von {1,…,n} heißt eine Permutation π ein k-Zyklus, wenn sie k ≤ n paarweise verschiedene Zahlen i_1,…,i_k nach dem Schema i_1 ↦ i_2 ↦ … ↦ i_k ↦ i_1 abbildet. Es gilt also π(i_1)=i_2, π(i_2)=i_3,…,π(i_{k−1})=i_k und π(i_k)=i_1. Für jedes andere Element j gilt π(j)=j.

Die Menge {i_1,…,i_k} heißt Träger oder Bahn des Zyklus. Der Träger enthält genau die Elemente, die zyklisch bewegt werden. Die Definition lässt sich auch auf beliebige endliche Mengen, etwa Alphabete, übertragen.

Zyklen sind wichtig, weil sich jede Permutation als Verkettung paarweise disjunkter Zyklen darstellen lässt. Dadurch können unter anderem die Ordnung und das Vorzeichen einer Permutation bestimmt werden.

Schreibweisen, Beispiele und Spezialfälle

Ein Zyklus kann vollständig als Funktion oder verkürzt durch seine bewegten Elemente angegeben werden. Üblich sind die Indexschreibweise π_{i_1,i_2,…,i_k} und die Zyklenschreibweise (i_1 i_2 … i_k). Dabei muss die Gesamtzahl n der Elemente aus dem Zusammenhang bekannt sein.

Die Darstellung ist nicht eindeutig, weil jedes Element als Anfang des Kreislaufs gewählt werden kann. Daher gilt beispielsweise (i_1 i_2 … i_k)=(i_2 … i_k i_1)=…=(i_k i_1 … i_{k−1}). Ein k-Zyklus besitzt somit k gleichwertige Schreibweisen. Häufig beginnt man mit dem kleinsten oder größten Element.

Beim Zyklus (1 2 3) wird 1 auf 2, 2 auf 3 und 3 wieder auf 1 abgebildet. Dagegen vertauscht (2 4) in S_4 nur die Zahlen 2 und 4; 1 und 3 bleiben fest. Ein Zyklus der Länge 1 entspricht der identischen Permutation id, die jedes Element unverändert lässt.

In S_4 gibt es einen Zyklus der Länge 1, sechs 2-Zyklen, acht 3-Zyklen und sechs 4-Zyklen. Von den insgesamt 24 Permutationen in S_4 sind nur drei nichtzyklisch; bei ihnen werden jeweils zwei Paare vertauscht.

Wichtige Spezialfälle sind: • Eine Transposition (i j) vertauscht genau zwei verschiedene Elemente. • Eine Nachbartransposition (i i+1) vertauscht zwei aufeinanderfolgende Elemente. • Der zyklische Rechtsshift (1 2 … n) bewegt alle Elemente in aufsteigender Reihenfolge im Kreis. • Der zyklische Linksshift (n n−1 … 1) bewegt sie in absteigender Reihenfolge im Kreis.

Anzahl, Verkettung und Umkehrung

Unter den n! Permutationen von {1,…,n} gibt es genau (n−1)! verschiedene n-Zyklen. Allgemein bezeichnet Z_{n,k} die Menge aller k-Zyklen in S_n. Für k=2,…,n gilt

|Z_{n,k}| = binom(n,k)(k−1)!.

Zuerst werden dabei k der n Elemente ausgewählt; auf diesen Elementen existieren (k−1)! verschiedene Zyklen. Für die Menge Z_n aller zyklischen Permutationen einschließlich der identischen Permutation gilt

|Z_n| = 1 + Σ_{k=2}^n binom(n,k)(k−1)!.

Die Hintereinanderausführung zweier Zyklen ist im Allgemeinen nicht kommutativ, ihre Reihenfolge darf also normalerweise nicht vertauscht werden. Haben zwei Zyklen jedoch disjunkte Träger, also kein gemeinsam bewegtes Element, dann kommutieren sie: π_I ∘ π_J = π_J ∘ π_I. Solche Zyklen heißen disjunkte Zyklen.

Die Verkettung zweier zyklischer Permutationen muss nicht wieder zyklisch sein. Beispielsweise zerfällt π_{1234} ∘ π_{1234} in die beiden Transpositionen π_{13} ∘ π_{24}. Deshalb ist Z_n für n ≥ 4 keine Untergruppe von S_n.

Die inverse Permutation eines Zyklus ist dagegen stets wieder ein Zyklus. Sie durchläuft die Elemente in umgekehrter Reihenfolge:

(π_{i_1,…,i_k})^{−1}=π_{i_k,…,i_1}.

Eine Transposition ist zu sich selbst invers.

Potenzen und Konjugation

Bei der m-maligen Anwendung eines k-Zyklus werden seine Elemente jeweils zyklisch um m Positionen weitergeschoben. Die m-te Potenz eines k-Zyklus ist genau dann selbst wieder zyklisch, wenn m und k teilerfremd sind. Nach k Anwendungen befindet sich jedes Element wieder an seiner Ausgangsstelle:

π^k = id.

Daraus folgt auch π^{k+1}=π. Die Menge {π,π²,…,π^{k−1},π^k} bildet unter der Hintereinanderausführung eine Untergruppe von S_n. Sie ist isomorph zur zyklischen Gruppe C_k; zu π^j ist π^{k−j} das inverse Element. Diese Untergruppe besteht genau dann ausschließlich aus zyklischen Permutationen, wenn k eine Primzahl ist.

Bei der Konjugation wird ein Zyklus durch eine beliebige Permutation σ umbenannt. Für π=(i_1 i_2 … i_k) gilt

σ ∘ π ∘ σ^{−1} = (σ(i_1) σ(i_2) … σ(i_k)).

Das Ergebnis ist wieder ein k-Zyklus. Daher bildet Z_{n,k} für jedes k∈{1,…,n} eine Konjugationsklasse von S_n. Allgemeiner sind zwei Permutationen genau dann konjugiert, wenn sie denselben Zyklentyp besitzen, also in gleich viele Zyklen der jeweiligen Längen zerfallen.

Zerlegungen, Vorzeichen und Ordnung

Jeder Zyklus der Länge k>2 kann an einer Stelle l∈{2,…,k−1} in zwei Teilzyklen zerlegt werden:

π_{i_1,…,i_k}=π_{i_1,…,i_l} ∘ π_{i_l,…,i_k}.

Durch wiederholte Anwendung entsteht eine Darstellung als Verkettung von k−1 Transpositionen:

π_{i_1,…,i_k}=π_{i_1,i_2} ∘ … ∘ π_{i_{k−1},i_k}.

Da jede Transposition ein ungerades Vorzeichen hat, gilt für einen k-Zyklus

sgn(π_{i_1,…,i_k})=(−1)^{k−1}.

Ein Zyklus ist daher genau dann gerade, wenn seine Länge ungerade ist. Beispielsweise lässt sich der 4-Zyklus π_{1423} als π_{14} ∘ π_{42} ∘ π_{23} schreiben. Er besteht aus drei Transpositionen und ist deshalb ungerade.

Umgekehrt lässt sich jede Permutation π∈S_n eindeutig bis auf die Reihenfolge der Faktoren als Verkettung paarweise disjunkter Zyklen darstellen:

π=π_{I_1} ∘ … ∘ π_{I_m}.

Die Träger I_1,…,I_m sind paarweise disjunkt; sind ihre Größen n_1,…,n_m, so gilt n_1+…+n_m=n. Die Stirling-Zahlen erster Art s_{n,m} geben an, wie viele Permutationen aus genau m solchen Zyklen bestehen.

Die Ordnung einer Permutation, also die kleinste positive Anzahl ihrer wiederholten Anwendungen, die id ergibt, ist das kleinste gemeinsame Vielfache der Zykluslängen n_1,…,n_m. Das Vorzeichen ergibt sich aus der Zahl der Zyklen gerader Länge.

Beispielsweise zerfällt die Permutation π∈S_6 mit 1↦3, 2↦6, 3↦4, 4↦1, 5↦5 und 6↦2 in (1 3 4)(2 6)(5). Ihre Ordnung ist kgV(3,2,1)=6. Da genau einer der drei Zyklen gerade Länge hat, ist die Permutation ungerade.

Anwendung bei Pseudozufallszahlen

Zyklische Permutationen mit großer Zyklenlänge werden bei der Konstruktion von Pseudozufallszahlengeneratoren verwendet. Die maximale Periode eines solchen Generators entspricht der Zahl seiner möglichen Zustände.

Bei einem einfachen rekursiven Generator x_{i+1}=f(x_i) mit f:{0,…,m−1}→{0,…,m−1} gibt es m mögliche Zustände. Seine Periode ist genau dann maximal, wenn f eine zyklische Permutation der Länge m auf dieser Zustandsmenge ist. Dann werden alle Zustände durchlaufen, bevor sich ein Zustand wiederholt.

Für lineare Kongruenzgeneratoren der Form

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

liefert der Satz von Knuth notwendige und hinreichende Bedingungen an die Parameter a, b und m dafür, dass die Periodenlänge maximal ist.