~2025-35964-91: /* Potenzen */

2025-11-24T09:04:56Z

Potenzen

Neue Seite

[[Datei:050712 perm 2.png|mini|Graph einer zyklischen Permutation der Zahlen von 1 bis 8]]
Eine '''zyklische Permutation''', kurz '''Zyklus''' (von {{elS|κύκλος|de=Kreis}}), ist in der [[Kombinatorik]] und der [[Gruppentheorie]] eine [[Permutation]], die bestimmte Elemente einer [[Menge (Mathematik)|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.

Zyklische Permutationen weisen eine Reihe besonderer Eigenschaften auf. So ist die [[Komposition (Mathematik)|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 [[Konjugationsklasse]]n der [[Symmetrische Gruppe|symmetrischen Gruppe]] aller Permutationen.

Jede zyklische Permutation kann in einzelne Transpositionen (Vertauschung von genau zwei Elementen) zerlegt werden und weist daher genau dann ein gerades [[Vorzeichen (Permutation)|Vorzeichen]] auf, wenn ihre Länge ungerade ist. Jede Permutation kann wiederum als Verkettung paarweise disjunkter Zyklen geschrieben werden, was in der [[Permutation#Zyklenschreibweise|Zyklenschreibweise]] von Permutationen genutzt wird. Die [[Permutation#Ordnung|Ordnung einer Permutation]] entspricht dann dem [[Kleinstes gemeinsames Vielfaches|kleinsten gemeinsamen Vielfachen]] der Längen dieser Zyklen. Zyklische Permutationen mit großer Zyklenlänge spielen eine wichtige Rolle bei der Konstruktion von [[Pseudozufallszahlengenerator]]en.

== Definition ==

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

:<math>i_1 \mapsto i_2 \mapsto \dotsb \mapsto i_k \mapsto i_1</math>,

und alle anderen Zahlen festhält. Es muss also gelten

:<math>\pi(i_1) = i_2, ~\pi(i_2) = i_3, \;\dotsc, ~\pi(i_{k-1}) = i_k</math>   und   <math>\pi(i_k) = i_1</math>

sowie

:<math>\pi(j) = j</math>   für   <math>j \not\in \{ i_1, \dotsc, i_k \}</math>.

Die Menge <math>\{ i_1, \dotsc, i_k \}</math> heißt der Träger oder die Bahn von <math>\pi</math>. Allgemeiner können auch Permutationen beliebiger [[Endliche Menge|endlicher Mengen]], beispielsweise [[Alphabet (Informatik)|Alphabete]], betrachtet werden, zur Analyse der mathematischen Eigenschaften kann man sich jedoch auf die ersten <math>n</math> natürlichen Zahlen beschränken.

== Notation ==

Neben der obigen Funktionsnotation, bei der die Abbildung <math>\pi</math> vollständig angegeben wird, kann eine zyklische Permutation auch dadurch notiert werden, dass lediglich die Zahlen, die zyklisch vertauscht werden, als [[Index (Mathematik)|Indizes]] mittels

:<math>\pi_{i_1, i_2, \dotsc, i_k}</math>

angegeben werden. Häufig wird eine zyklische Permutation auch in [[Permutation#Zyklenschreibweise|Zyklenschreibweise]] notiert, indem diese Zahlen ohne Trennzeichen in Klammern gesetzt werden:

:<math>( i_1 ~ i_2 ~ \dotso ~ i_k )</math>

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

:<math>\pi_{i_1, i_2, \dotsc, i_k} = \pi_{i_2, \dotsc, i_k, i_1} = \dotsb = \pi_{i_k, i_1, \dotsc, i_{k-1}}</math>

oder

:<math>( i_1 ~ i_2 ~ \dotso ~ i_k ) = ( i_2 ~ \dotso ~ i_k ~ i_1 ) = \dotsb = ( i_k ~ i_1 ~ \dotso ~ i_{k-1} )</math>

beschrieben werden. Oft gesetzte Konvention ist aber, für <math>i_1</math> die kleinste oder die größte Zahl des Zyklus zu wählen.

== Beispiele ==

{| class="wikitable float-right" style="text-align:center"
|+ Zyklische Permutationen in ''S4''
|- class="hintergrundfarbe8"
! Länge !! Zyklische Permutationen !! Anzahl
|-
|class="hintergrundfarbe8" | 1 || align="left" | id || 1
|-
|class="hintergrundfarbe8" | 2 || align="left" | (1 2), (1 3), (1 4), (2 3), (2 4), (3 4) || 6
|-
|class="hintergrundfarbe8" | 3 || align="left" | (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
|-
|class="hintergrundfarbe8" | 4 || align="left" | (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

:<math>\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</math>.

Hierbei wird die Zahl <math>1</math> auf die Zahl <math>2</math>, die Zahl <math>2</math> auf die Zahl <math>3</math> und die Zahl <math>3</math> wieder auf die Zahl <math>1</math> abgebildet. Die Permutation

:<math>\pi_{24} = \pi_{42} = ( 2 ~ 4 ) = ( 4 ~ 2 ) = \begin{pmatrix} 1 & 2 & 3 & 4\\ 1 & 4 & 3 & 2\end{pmatrix} \in S_4</math>

ist eine zyklische Permutation der Länge zwei, bei der die Zahlen <math>2</math> und <math>4</math> vertauscht werden und die Zahlen <math>1</math> und <math>3</math> festgehalten werden. Jede zyklische Permutation der Länge eins

:<math>\pi_1 = \pi_2 = \dotsb = \pi_n = ( 1 ) = ( 2 ) = \dotsb = ( n ) = \begin{pmatrix} 1 & 2 & \cdots & n \\ 1 & 2 & \cdots & n \end{pmatrix}\in S_n</math>

entspricht gerade der [[Identische Permutation|identischen Permutation]] <math>\operatorname{id}</math>, die alle Zahlen unverändert lässt. In der symmetrischen Gruppe <math>S_4</math> finden sich die in der nebenstehenden Tabelle aufgeführten zyklischen Permutationen. Von den <math>24</math> Permutationen in <math>S_4</math> sind demnach nur drei Permutationen nichtzyklisch, nämlich diejenigen, die jeweils zwei Paare von Zahlen vertauschen.

== Spezialfälle ==

Bei zyklischen Permutationen werden folgende Spezialfälle betrachtet:

; Vertauschung oder Transposition: Eine zyklische Permutation, die genau zwei Elemente miteinander vertauscht, also

::<math>\pi_{i,j} = ( i ~ j )</math>   für   <math>i,j \in \{ 1, \dotsc, n \}, i \neq j</math>.

; Nachbarvertauschung oder Nachbartransposition: Eine zyklische Permutation, die zwei aufeinander folgende Elemente miteinander vertauscht, also

::<math>\pi_{i,i+1} = ( i ~ i+1 )</math>   für   <math>i \in \{ 1, \dotsc, n-1 \}</math>.

; Zyklischer Rechtsshift: Eine zyklische Permutation, die alle Elemente der Reihe nach aufsteigend im Kreis vertauscht, also

::<math>\pi_{1,2, \dotsc, n} = ( 1 ~ 2 ~ \dotso ~ n )</math>.

; Zyklischer Linksshift: Eine zyklische Permutation, die alle Elemente der Reihe nach absteigend im Kreis vertauscht, also

::<math>\pi_{n,n-1, \dotsc,1} = ( n ~ n-1 ~ \dotso ~ 1 )</math>.

== Eigenschaften ==

=== Anzahl ===

{| class="wikitable float-right" style="text-align:right"
|+ Anzahl der ''k''-Zyklen in ''Sn''
|- class="hintergrundfarbe8"
|style="width:2em" | <math>{}_{n} \! \diagdown \!\! {}^{k}</math>
|style="width:2em" | 1
|style="width:2em" | 2
|style="width:2em" | 3
|style="width:2em" | 4
|style="width:2em" | 5
|style="width:2em" | 6
|style="width:2em" | Summe
|-
|class="hintergrundfarbe8" | 1 || 1 || || || || || || 1
|-
|class="hintergrundfarbe8" | 2 || 1 || 1 || || || || || 2
|-
|class="hintergrundfarbe8" | 3 || 1 || 3 || 2 || || || || 6
|-
|class="hintergrundfarbe8" | 4 || 1 || 6 || 8 || 6 || || || 21
|-
|class="hintergrundfarbe8" | 5 || 1 || 10 || 20 || 30 || 24 || || 85
|-
|class="hintergrundfarbe8" | 6 || 1 || 15 || 40 || 90 || 144 || 120 || 410
|}

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

:<math>| Z_{n,k} | = \binom nk (k-1)!</math>    ({{OEIS|A111492}}),

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

:<math>| Z_n | = 1 + \sum_{k=2}^n \binom nk (k-1)!</math>    ({{OEIS|A121726}})

=== Kommutativität ===

Im Allgemeinen ist die [[Komposition (Mathematik)|Hintereinanderausführung]] zweier zyklischer Permutationen nicht [[Kommutativität|kommutativ]]. Besitzen allerdings zwei zyklische Permutationen <math>\pi_{i_1, \dotsc, i_k} \in Z_{n,k}</math> und <math>\pi_{j_1, \dotsc, j_l} \in Z_{n,l}</math> [[disjunkt]]e Träger, gilt also

:<math>\{ i_1, \dotsc, i_k \} \cap \{ j_1, \dotsc, j_l \} = \emptyset</math>,

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

:<math>\pi_{i_1, \dotsc, i_k} \circ \pi_{j_1, \dotsc, j_l} = \pi_{j_1, \dotsc, j_l} \circ \pi_{i_1, \dotsc, i_k}</math>.

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

=== Abgeschlossenheit und Inverse ===

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

:<math>\pi_{1234} \circ \pi_{1234} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \end{pmatrix} = \pi_{13} \circ \pi_{24}</math>

zeigt. Daher bildet die Menge der zyklischen Permutationen <math>Z_n</math> für <math>n \geq 4</math> keine [[Untergruppe]] der symmetrischen Gruppe <math>S_n</math>. Allerdings ist die [[inverse Permutation]] einer zyklischen Permutation <math>\pi_{i_1, \dotsc, i_k}</math> stets ebenfalls eine zyklische Permutation, nämlich diejenige, die die Zahlen <math>i_1, \dotsc, i_k</math> in umgekehrter Reihenfolge zyklisch vertauscht, also

:<math>(\pi_{i_1, \dotsc, i_k})^{-1} = \pi_{i_k, \dotsc, i_1}</math>.

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

=== Potenzen ===

Wird eine zyklische Permutation zweimal hintereinander angewandt, so verschieben sich alle Indizes zyklisch um <math>2</math>, das heißt, <math>i_1</math> wird auf <math>i_3</math> abgebildet, <math>i_2</math> auf <math>i_4</math> und so weiter bis hin zu <math>i_{k-1}</math> auf <math>i_1</math> und <math>i_k</math> auf <math>i_2</math>. Allgemein verschieben sich durch die <math>m</math>-malige Anwendung einer zyklischen Permutation alle Indizes zyklisch um <math>m</math>. Die <math>m</math>-te Potenz einer zyklischen Permutation der Länge <math>k</math> ist genau dann selbst wieder zyklisch, wenn <math>m</math> und <math>k</math> [[teilerfremd]] sind. Speziell ergibt die <math>k</math>-malige Anwendung einer zyklischen Permutation <math>\pi \in Z_{n,k}</math> die identische Permutation, also

:<math>\pi^k = \operatorname{id}</math>,

und die <math>(k+1)</math>-malige Anwendung ergibt wieder die Ausgangspermutation, also

:<math>\pi^{k+1} = \pi</math>.

Daher bildet die Menge

:<math>\{ \pi, \pi^2, \dotsc, \pi^{k-1}, \pi^k \}</math>

mit der Hintereinanderausführung eine Untergruppe der symmetrischen Gruppe <math>S_n</math>, wobei <math>\pi^{k-j}</math> das [[Inverses Element|inverse Element]] zu <math>\pi^j</math> ist. Diese Untergruppe ist [[Gruppenisomorphismus|isomorph]] zur [[Zyklische Gruppe|zyklischen Gruppe]] <math>C_k</math> und besteht genau dann ausschließlich aus zyklischen Permutationen, wenn <math>k</math> eine [[Primzahl]] ist.

=== Konjugation ===

Für eine zyklische Permutation

:<math>\pi = (i_1 ~ i_2 ~ \dotso ~ i_k) \in Z_{n,k}</math>

berechnet sich die [[Konjugation (Gruppentheorie)|Konjugation]] mit einer beliebigen Permutation <math>\sigma \in S_n</math> zu

:<math>\sigma \circ \pi \circ \sigma^{-1} = \left(\sigma(i_1) ~ \sigma(i_2) ~ \dotso ~ \sigma(i_k)\right)</math>,

sie ergibt also wiederum einen <math>k</math>-Zyklus. Die Menge <math>Z_{n,k}</math> bildet dabei für jedes <math>k \in \{1,\dotsc,n\}</math> eine [[Konjugationsklasse]] der Gruppe <math>S_n</math>. Allgemein sind zwei Permutationen <math>\pi,\sigma \in S_n </math> genau dann zueinander konjugiert, wenn ihr [[Zykeltyp|Zyklentyp]] übereinstimmt.

== Zerlegungen ==

=== Zerlegung von Zyklen in Teilzyklen ===

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

:<math>\pi_{i_1, \dotsc, i_k} = \pi_{i_1, \dotsc, i_l} \circ \pi_{i_l, \dotsc, i_k}</math>

in zwei Teilzyklen zerlegen. Wendet man diese Zerlegung wiederholt mit <math>l=2, 3, \dotsc, k-1</math> an, ergibt sich, dass jede zyklische Permutation der Länge <math>k</math> mittels

:<math>\pi_{i_1, \dotsc, i_k} = \pi_{i_1,i_2} \circ \dotsb \circ \pi_{i_{k-1},i_k}</math>

als Verkettung von <math>k-1</math> Transpositionen geschrieben werden kann. Für das [[Vorzeichen (Permutation)|Vorzeichen]] einer zyklischen Permutation der Länge <math>k</math> gilt damit

:<math>\operatorname{sgn}(\pi_{i_1, \dotsc, i_k}) = \operatorname{sgn}(\pi_{i_1,i_2}) \dotsm \operatorname{sgn}(\pi_{i_{k-1},i_k}) = (-1)^{k-1}</math>,

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 <math>\pi_{1423} \in S_4</math> der Länge vier lässt sich durch

:<math>\pi_{1423} = \pi_{14} \circ \pi_{42} \circ \pi_{23}</math>

in drei Transpositionen zerlegen und ist demnach ungerade.

=== Zerlegung von Permutationen in Zyklen ===
[[Datei:050712 perm 0.png|mini|Graph einer Permutation der Zahlen von 1 bis 7, die in drei disjunkte Zyklen zerfällt]]

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

:<math>\pi = \pi_{I_1} \circ \dotsb \circ \pi_{I_m}</math>

mit paarweise disjunkten Trägern <math>I_j = \{ i_{j,1}, \dotsc, i_{j,n_j} \}</math> für <math>j=1, \dotsc, m</math>, wobei <math>n_1 + \dotsb + n_m = n</math> ist. Die [[Stirling-Zahl]]en erster Art <math>s_{n,m}</math> geben dabei an, wie viele Permutationen in <math>S_n</math> als Verkettung von genau <math>m</math> zyklischen Permutationen geschrieben werden können. Die [[Permutation#Ordnung|Ordnung einer Permutation]] entspricht der [[Gruppenordnung|Ordnung]] der zugehörigen zyklischen Gruppe und ist damit das [[Kleinstes gemeinsames Vielfaches|kleinste gemeinsame Vielfache]] der Längen <math>n_1, \dotsc, n_m</math> dieser Zyklen. Weiter ergibt sich das Vorzeichen einer Permutation aus der Zahl der Zyklen gerader Länge.

==== Beispiel ====

Die Permutation

:<math>\pi = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 3 & 6 & 4 & 1 & 5 & 2 \end{pmatrix} \in S_6</math>

zerfällt in die drei disjunkten Zyklen

:<math>\pi = \pi_{134} \circ \pi_{26} \circ \pi_5</math>

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

== Anwendungen ==

Zyklische Permutationen mit großer Zyklenlänge spielen eine wichtige Rolle bei der Konstruktion von [[Pseudozufallszahlengenerator]]en. Die maximale [[Periodizität (Mathematik)|Periode]] eines solchen Zufallszahlengenerators entspricht der Anzahl der möglichen Zustände des Generators. Bei einfachen [[Rekursiver arithmetischer Zufallszahlengenerator|rekursiven Generatoren]] der Form

:<math>x_{i+1} = f(x_i)</math>

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

:<math>x_{i+1} = (a x_i + b) \bmod m</math>

liefert der [[Satz von Knuth]] hinreichende und notwendige Bedingungen an die Parameter <math>a, b</math> und <math>m</math> für die Maximalität der Periodenlänge.

== Literatur ==

* {{Literatur
|Autor=[[Albrecht Beutelspacher]]
|Titel=Lineare Algebra. Eine Einführung in die Wissenschaft der Vektoren, Abbildungen und Matrizen
|Auflage=6.
|Verlag=Vieweg
|Datum=2009
|ISBN=3-528-56508-X}}
* {{Literatur
|Autor=[[Gerd Fischer (Mathematiker)|Gerd Fischer]]
|Titel=Lehrbuch der Algebra
|Verlag=Springer
|Datum=2007
|ISBN=3-8348-0226-3}}
* {{Literatur
|Autor=Jens Carsten Jantzen, [[Joachim Schwermer]]
|Titel=Algebra
|Verlag=Springer
|Datum=2005
|ISBN=3-540-21380-5}}

== Weblinks ==

* {{EoM|Autor=D.A. Suprunenko|Titel=Permutation of a set|Url=https://encyclopediaofmath.org/wiki/Permutation_of_a_set}}
* {{MathWorld|id=PermutationCycle|title=Permutation Cycle}}
* {{PlanetMath|id=Cycle2|title=Cycle|author=yark, Pedro Sanchez}}

[[Kategorie:Permutationstheorie]]

Zyklische Permutation - Versionsgeschichte

~2025-35964-91: /* Potenzen */