Syklisk permutasjon

Graf av en syklisk permutasjon av tall fra 1 til 8

En syklisk permutasjon , eller kort syklus (fra den greske κύκλος 'sirkelen' ), er en permutasjon i kombinatorikk og gruppeteori som bytter visse elementer i et sett i en sirkel og holder de andre. Det første elementet i syklusen er kartlagt på det andre, det andre elementet på det tredje, og så videre opp til det siste elementet, som er kartlagt tilbake på det første.

Sykliske permutasjoner har en rekke spesielle egenskaper. Den sammenkobling av to sykliske permutasjoner er kommutativ om de har atskilte bærere. Den omvendte permutasjonen av en syklisk permutasjon er alltid også syklisk. Videre vil enhver krefter av en syklisk permutasjon, hvis lengde er et primtall , igjen resultere i sykliske permutasjoner. De sykliske permutasjonene med fast lengde danner også konjugasjonsklasser for den symmetriske gruppen av alle permutasjoner.

Hver sykliske permutasjon kan brytes ned i individuelle transposisjoner (utveksler nøyaktig to elementer) og har derfor et jevnt tegn hvis lengden er merkelig. Hver permutasjon kan igjen skrives som en sammenkobling av parvise sammenhengende sykluser, som brukes i syklusnotasjonen av permutasjoner. Den rekkefølge av en permutasjon deretter tilsvarer den minste felles multiplum av lengden av disse sykluser. Sykliske permutasjoner med lange sykluslengder spiller en viktig rolle i konstruksjonen av pseudorandom nummergeneratorer .

definisjon

Hvis den symmetriske gruppen av alle permutasjoner i settet er , kalles en permutasjon syklisk med lengde eller syklus hvis den bytter ut en liste med parvis forskjellige tall i en sirkel, det vil si ${\ displaystyle S_ {n}}$${\ displaystyle \ {1, \ dotsc, n \}}$${\ displaystyle \ pi = (\ pi (1), \ pi (2), \ dotsc, \ pi (n)) \ i S_ {n}}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle k \ leq n}$${\ displaystyle i_ {1}, i_ {2}, \ dotsc, i_ {k} \ in \ {1, \ dotsc, n \}}$

${\ displaystyle i_ {1} \ mapsto i_ {2} \ mapsto \ dotsb \ mapsto i_ {k} \ mapsto i_ {1}}$,

og registrerer alle andre tall. Så det må gjelde

${\ displaystyle \ pi (i_ {1}) = i_ {2}, ~ \ pi (i_ {2}) = i_ {3}, \; \ dotsc, ~ \ pi (i_ {k-1}) = i_ {k}}$   og   ${\ displaystyle \ pi (i_ {k}) = i_ {1}}$

som

${\ displaystyle \ pi (j) = j}$   for   .${\ displaystyle j \ not \ in \ {i_ {1}, \ dotsc, i_ {k} \}}$

Beløpet kalles transportøren eller banen til . På en mer generell måte kan permutasjoner av eventuelle begrensede sett , for eksempel alfabeter , vurderes, men analysen av de matematiske egenskapene kan begrenses til de første naturlige tallene. ${\ displaystyle \ {i_ {1}, \ dotsc, i_ {k} \}}$${\ displaystyle \ pi}$${\ displaystyle n}$

notasjon

I tillegg til ovennevnte funksjonsnotasjon, der figuren er spesifisert i sin helhet, kan en syklisk permutasjon også noteres ved å bruke bare tallene som syklisk byttes ut som indekser ved bruk av ${\ displaystyle \ pi}$

${\ displaystyle \ pi _ {i_ {1}, i_ {2}, \ dotsc, i_ {k}}}$

kan spesifiseres. Ofte blir en syklisk permutasjon også notert i syklusnotasjon ved å sette disse tallene i parentes uten skilletegn:

${\ displaystyle (i_ {1} ~ i_ {2} ~ \ dotso ~ i_ {k})}$

Begge stavemåtene antar at det totale antall tall er kjent. Indeksen og syklusnotasjonen er imidlertid ikke unik, fordi startnummeret kan velges som ønsket i syklusen. Hver syklus kan gjøre det på forskjellige måter ${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle k}$

${\ displaystyle \ 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}}}$

eller

${\ displaystyle (i_ {1} ~ i_ {2} ~ \ dotso ~ i_ {k}) = (i_ {2} ~ \ dotso ~ i_ {k} ~ i_ {1}) = \ dotsb = (i_ {k } ~ i_ {1} ~ \ dotso ~ i_ {k-1})}$

å bli beskrevet. Konvensjonen som ofte settes er imidlertid å velge det minste eller det største antallet i syklusen. ${\ displaystyle i_ {1}}$

Eksempler

Er en enkel syklisk permutasjon av lengde tre

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

Her er tallet nummeret , nummeret på nummeret og tallet tilbake på nummeret som vises. Permutasjonen ${\ displaystyle 1}$${\ displaystyle 2}$${\ displaystyle 2}$${\ displaystyle 3}$${\ displaystyle 3}$${\ displaystyle 1}$

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

er en syklisk permutasjon av lengde to der tallene og byttes ut og tallene og beholdes. Enhver syklisk permutasjon av lengde en ${\ displaystyle 2}$${\ displaystyle 4}$${\ displaystyle 1}$${\ displaystyle 3}$

${\ displaystyle \ pi _ {1} = \ pi _ {2} = \ dotsb = \ pi _ {n} = (1) = (2) = \ dotsb = (n) = {\ begin {pmatrix} 1 & 2 & \ cdots & n \\ 1 & 2 & \ cdots & n \ end {pmatrix}} \ i S_ {n}}$

tilsvarer den samme permutasjonen , som etterlater alle tall uendret. De sykliske permutasjonene oppført i den tilstøtende tabellen er funnet i den symmetriske gruppen . Av permutasjonene i er bare tre permutasjoner derfor ikke-sykliske, nemlig de som utveksler to par tall. ${\ displaystyle \ operatorname {id}}$${\ displaystyle S_ {4}}$${\ displaystyle 24}$${\ displaystyle S_ {4}}$

Spesielle tilfeller

Følgende spesielle tilfeller vurderes for sykliske permutasjoner:

Utveksling eller transponering

En syklisk permutasjon som bytter nøyaktig to elementer med hverandre, altså

${\ displaystyle \ pi _ {i, j} = (i ~ j)}$   for   .${\ displaystyle i, j \ in \ {1, \ dotsc, n \}, i \ neq j}$

Nabobytte eller nabotransposisjon

En syklisk permutasjon som bytter ut to påfølgende elementer, dvs.

${\ displaystyle \ pi _ {i, i + 1} = (i ~ i + 1)}$   for   .${\ displaystyle i \ in \ {1, \ dotsc, n-1 \}}$

Syklisk skift til høyre

En syklisk permutasjon som bytter alle elementer i stigende rekkefølge i en sirkel, dvs.

${\ displaystyle \ pi _ {1,2, \ dotsc, n} = (1 ~ 2 ~ \ dotso ~ n)}$.

Syklisk venstreskift

En syklisk permutasjon som bytter ut alle elementene i en sirkel i synkende rekkefølge, dvs.

${\ displaystyle \ pi _ {n, n-1, \ dotsc, 1} = (n ~ n-1 ~ \ dotso ~ 1)}$.

eiendommer

Nummer

Antall k sykluser i S _n

${\ displaystyle {} _ {n} \! \ diagdown \! \! {} ^ {k}}$	1	2	3	4. plass	5	Sjette	Total
1	1						1
2	1	1					2
3	1	3	2				Sjette
4. plass	1	Sjette	8. plass	Sjette			21
5	1	10	20.	30.	24		85
Sjette	1	15.	40	90	144	120	410

I settet med de forskjellige permutasjonene av tallene er det nøyaktig mange sykluser. Hver permutasjon i tupelnotasjon tilsvarer en syklus , som igjen kan skrives på forskjellige måter. Hvis nå generelt betegner settet med -cykler i , gjelder det for${\ displaystyle n!}$${\ displaystyle \ {1, \ dotsc, n \}}$${\ displaystyle (n-1)!}$${\ displaystyle n}$ ${\ displaystyle (i_ {1}, i_ {2}, \ dotsc, i_ {n})}$${\ displaystyle n}$${\ displaystyle (i_ {1} ~ i_ {2} ~ \ dotso ~ i_ {n})}$${\ displaystyle n}$${\ displaystyle Z_ {n, k}}$${\ displaystyle k}$${\ displaystyle S_ {n}}$${\ displaystyle k = 2, \ dotsc, n}$

${\ displaystyle | Z_ {n, k} | = {\ binom {n} {k}} (k-1)!}$    (Følg A111492 i OEIS ),

fordi det er måter å velge mellom tall. For den totale mengden av alle sykliske permutasjoner inkludert identisk permutasjon, gjelder følgende: ${\ displaystyle {\ tbinom {n} {k}}}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle Z_ {n}}$${\ displaystyle S_ {n}}$

${\ displaystyle | Z_ {n} | = 1 + \ sum _ {k = 2} ^ {n} {\ binom {n} {k}} (k-1)!}$    (Følg A121726 i OEIS )

Kommutativitet

Generelt er den sekvensielle kjøringen av to sykliske permutasjoner ikke kommutativ . Imidlertid , hvis de har to sykliske permutasjoner og usammenhengende bærere, så gjelder følgende ${\ displaystyle \ pi _ {i_ {1}, \ dotsc, i_ {k}} \ i Z_ {n, k}}$${\ displaystyle \ pi _ {j_ {1}, \ dotsc, j_ {l}} \ i Z_ {n, l}}$

${\ displaystyle \ {i_ {1}, \ dotsc, i_ {k} \} \ cap \ {j_ {1}, \ dotsc, j_ {l} \} = \ emptyset}$,

da kan ordren deres reverseres når de blir henrettet etter hverandre, det vil si at den gjelder

${\ displaystyle \ 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}}}$.

Sykliske permutasjoner med usammenhengende bærere kalles også usammenhengende sykluser.

Isolasjon og omvendt

Å utføre to sykliske permutasjoner etter hverandre er ikke nødvendigvis syklisk igjen, som eksemplet

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

viser. Derfor dannes mengden av sykliske permutasjoner for en hvilken som helst undergruppe av den symmetriske gruppen . Imidlertid er den omvendte permutasjonen av en syklisk permutasjon alltid også en syklisk permutasjon, nemlig den som syklisk bytter ut tallene i omvendt rekkefølge, det vil si ${\ displaystyle Z_ {n}}$${\ displaystyle n \ geq 4}$${\ displaystyle S_ {n}}$${\ displaystyle \ pi _ {i_ {1}, \ dotsc, i_ {k}}}$${\ displaystyle i_ {1}, \ dotsc, i_ {k}}$

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

Den omvendte permutasjonen av en transponering er altså den samme transponeringen igjen.

Potenser

Move er en syklisk permutasjon som påføres to ganger etter hverandre, alle indeksene er syklisk , det vil si, satt til klare, videre og så videre til på og av . Generelt, ved å bruke en syklisk permutasjon en gang, forskyves alle indekser syklisk . Den -th kraften av en syklisk permutasjon av den lengde i seg selv er cyklisk igjen hvis og bare hvis , og er coprime . Spesielt resulterer gjentatt påføring av en syklisk permutasjon i identisk permutasjon, dvs. ${\ displaystyle 2}$${\ displaystyle i_ {1}}$${\ displaystyle i_ {3}}$${\ displaystyle i_ {2}}$${\ displaystyle i_ {4}}$${\ displaystyle i_ {k-1}}$${\ displaystyle i_ {1}}$${\ displaystyle i_ {k}}$${\ displaystyle i_ {2}}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle k}$${\ displaystyle m}$${\ displaystyle k}$ ${\ displaystyle k}$${\ displaystyle \ pi \ i Z_ {n, k}}$

${\ displaystyle \ pi ^ {k} = \ operatorname {id}}$,

og -mal påføring resulterer igjen i den første permutasjonen, det vil si ${\ displaystyle (k + 1)}$

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

Derfor dannes mengden

${\ displaystyle \ {\ pi, \ pi ^ {2}, \ dotsc, \ pi ^ {k-1}, \ pi ^ {k} \}}$

med den sekvensielle kjøringen av en delmengde av den symmetriske gruppen , hvor det inverse elementet skal være. Denne undergruppen er isomorf til den sykliske gruppen og består utelukkende av sykliske permutasjoner hvis og bare hvis er et primtall . ${\ displaystyle S_ {n}}$${\ displaystyle \ pi ^ {kj}}$${\ displaystyle \ pi ^ {j}}$ ${\ displaystyle C_ {k}}$${\ displaystyle k}$

bøyning

For en syklisk permutasjon

${\ displaystyle \ pi = (i_ {1} ~ i_ {2} ~ \ dotso ~ i_ {k}) \ i Z_ {n, k}}$

som er beregnet konjugasjon med en vilkårlig permutasjon til ${\ displaystyle \ sigma \ in S_ {n}}$

${\ displaystyle \ sigma \ circ \ pi \ circ \ sigma ^ {- 1} = \ left (\ sigma (i_ {1}) ~ \ sigma (i_ {2}) ~ \ dotso ~ \ sigma (i_ {k} ) \ Ikke sant)}$,

så det igjen resulterer i en syklus. Settet danner en bøyningsklasse for gruppen for hver . Generelt er to permutasjoner konjugert til hverandre hvis og bare hvis syklusstypen samsvarer. ${\ displaystyle k}$${\ displaystyle Z_ {n, k}}$${\ displaystyle k \ in \ {1, \ dotsc, n \}}$${\ displaystyle S_ {n}}$${\ displaystyle \ pi, \ sigma \ in S_ {n}}$

Nedbrytning

Fordeling av sykluser i undersykluser

Hver sykliske permutasjon av lengden kan endres når som helst ved hjelp av ${\ displaystyle k> 2}$${\ displaystyle l \ in \ {2, \ dotsc, k-1 \}}$

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

delt inn i to undersykluser. Hvis denne nedbrytningen påføres gjentatte ganger , resulterer det i at hver syklisk permutasjon av lengden ved hjelp av ${\ displaystyle l = 2,3, \ dotsc, k-1}$${\ displaystyle k}$

${\ displaystyle \ pi _ {i_ {1}, \ dotsc, i_ {k}} = \ pi _ {i_ {1}, i_ {2}} \ circ \ dotsb \ circ \ pi _ {i_ {k-1 }, i_ {k}}}$

kan skrives som en kjede av transposisjoner. For tegnet på en syklisk permutasjon av lengden, gjelder følgende ${\ displaystyle k-1}$${\ displaystyle k}$

${\ displaystyle \ 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}}$,

siden transposisjoner alltid har et merkelig tegn. En syklisk permutasjon er selv om og bare hvis lengden er merkelig.

eksempel

Den sykliske permutasjonen med lengde fire kan passeres ${\ displaystyle \ pi _ {1423} \ i S_ {4}}$

${\ displaystyle \ pi _ {1423} = \ pi _ {14} \ circ \ pi _ {42} \ circ \ pi _ {23}}$

delt i tre transposisjoner og er derfor rart.

Nedbrytning av permutasjoner i sykluser

Graf over en permutasjon av tallene fra 1 til 7 som brytes ned i tre usammenhengende sykluser

Hver permutasjon kan være unikt representert (bortsett fra utveksling av faktorene) som en sammenkobling av parvise sammenhengende sykluser. Det vil si at det gjelder ${\ displaystyle \ pi \ i S_ {n}}$${\ displaystyle m \ leq n}$

${\ displaystyle \ pi = \ pi _ {I_ {1}} \ circ \ dotsb \ circ \ pi _ {I_ {m}}}$

med parvise usammenhengende bærere for , hvor er. De Stirling tallene i første typen indikerer hvor mange permutasjoner kan skrives på som en sammensetning av nøyaktig sykliske variasjoner. Den rekkefølge av en permutasjon svarer til rekkefølgen av de tilhørende cykliske gruppe, og er derfor den minste felles multiplum av lengden av disse sykluser. Videre er tegn på permutasjon resultatet av antall sykluser med jevn lengde. ${\ displaystyle I_ {j} = \ {i_ {j, 1}, \ dotsc, i_ {j, n_ {j}} \}}$${\ displaystyle j = 1, \ dotsc, m}$${\ displaystyle n_ {1} + \ dotsb + n_ {m} = n}$${\ displaystyle s_ {n, m}}$${\ displaystyle S_ {n}}$${\ displaystyle m}$${\ displaystyle n_ {1}, \ dotsc, n_ {m}}$

eksempel

Permutasjonen

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

brytes ned i de tre usammenhengende syklusene

${\ displaystyle \ pi = \ pi _ {134} \ circ \ pi _ {26} \ circ \ pi _ {5}}$

og har dermed ordren . Siden bare en av de tre syklusene er jevn i lengde, er permutasjonen merkelig. ${\ displaystyle \ operatorname {kgV} (3,2,1) = 6}$

applikasjoner

Sykliske permutasjoner med lange sykluslengder spiller en viktig rolle i konstruksjonen av pseudorandom nummergeneratorer . Den maksimale periode på slike en tilfeldig tall generator svarer til antallet av mulige tilstander av generatoren. Med enkle rekursive generatorer av skjemaet

${\ displaystyle x_ {i + 1} = f (x_ {i})}$

med antall mulige tilstander er jevnt . Perioden for en slik generator er maksimal hvis funksjon representerer en syklisk permutasjon av lengden av settet . Når det gjelder lineære kongruensgeneratorer av typen ${\ displaystyle f \ colon \ {0, \ dotsc, m-1 \} \ to \ {0, \ dotsc, m-1 \}}$${\ displaystyle m}$${\ displaystyle f}$${\ displaystyle m}$${\ displaystyle \ {0, \ dotsc, m-1 \}}$

${\ displaystyle x_ {i + 1} = (ax_ {i} + b) {\ bmod {m}}}$

Knuths teorem gir tilstrekkelige og nødvendige betingelser for parametrene og for maksimaliteten av periodelengden. ${\ displaystyle a, b}$${\ displaystyle m}$

litteratur

• Albrecht Beutelspacher : Lineær algebra. En introduksjon til vitenskapen om vektorer, kart og matriser . 6. utgave. Vieweg, 2009, ISBN 3-528-56508-X . 
• Gerd Fischer : Algebra-lærebok . Springer, 2007, ISBN 3-8348-0226-3 . 
• Jens Carsten Jantzen, Joachim Schwermer : Algebra . Springer, 2005, ISBN 3-540-21380-5 . 

weblenker

• DA Suprunenko: Permutasjon av et sett . I: Michiel Hazewinkel (red.): Encyclopedia of Mathematics . Springer-Verlag og EMS Press, Berlin 2002, ISBN 978-1-55608-010-4 (engelsk, online ). 
• Eric W. Weisstein : Permutasjonssyklus . På: MathWorld (engelsk).
• yark, Pedro Sanchez: Syklus . I: PlanetMath . (Engelsk)