Cyklar och fixpunkter

16-bitars gråkodspermutation G multiplicerad med bitomvändningspermutationen B G har 2 fixpunkter, 1 2-cykel och 3 4 -cykler B har 4 fixpunkter och 6 2-cykler GB har 2 fixpunkter och 2 7-cykler

P * (1,2,3,4) ^T = (4,1,3,2) ^T Permutation av fyra element med 1 fixpunkt och 1 3-cykel

Inom matematiken motsvarar cyklerna för en permutation π av en ändlig mängd S bijektivt banorna i undergruppen som genereras av π som verkar på S . Dessa banor är delmängder av S som kan skrivas som { c ₁ , ..., c _n } , så att

π ( ci ₎ = ci _{. + 1} för i = 1, ..., − 1 n , och π ( c _n ) = c ₁

Den motsvarande cykeln för π skrivs som ( c ₁ c ₂ ... c _n ); detta uttryck är inte unikt eftersom c ₁ kan väljas att vara vilket element som helst i omloppsbanan.

Storleken n av omloppsbanan kallas längden av motsvarande cykel; när n = 1 kallas det enda elementet i omloppsbanan en fixpunkt för permutationen.

En permutation bestäms genom att ge ett uttryck för var och en av dess cykler, och en notation för permutationer består av att skriva sådana uttryck efter varandra i någon ordning. Till exempel, låt

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

vara en permutation som mappar 1 till 2, 6 till 8 etc. Då får man skriva

π = ( 1 2 4 3 ) ( 5 ) ( 6 8 ) (7) = (7) ( 1 2 4 3 ) ( 6 8 ) ( 5 ) = ( 4 3 1 2 ) ( 8 6 ) ( 5 ) ( 7) = ...

Här är 5 och 7 fixpunkter för π , eftersom π (5)=5 och π (7)=7. Det är typiskt, men inte nödvändigt, att inte skriva cyklerna av längd ett i ett sådant uttryck. Således skulle π = (1 2 4 3)(6 8), vara ett lämpligt sätt att uttrycka denna permutation.

Det finns olika sätt att skriva en permutation som en lista över dess cykler, men antalet cykler och deras innehåll ges av uppdelningen av S i banor, och dessa är därför desamma för alla sådana uttryck.

Räknar permutationer efter antal cykler

Stirlingtalet utan tecken av det första slaget, s ( k , j ) räknar antalet permutationer av k element med exakt j disjunkta cykler.

Egenskaper

(1) För varje k > 0 : s ( k , k ) = 1.

(2) För varje k > 0 : s ( k , 1) = ( k − 1)!.

(3) För varje k > j > 1, s ( k , j ) = s ( k − 1, j − 1) + s ( k − 1, j )·( k − 1)

Orsaker till fastigheter

(1) Det finns bara ett sätt att konstruera en permutation av k element med k cykler: Varje cykel måste ha längden 1 så varje element måste vara en fixpunkt.

(2.a) Varje cykel av längden k kan skrivas som permutation av talet 1 till k ; det finns k ! av dessa permutationer.

(2.b) Det finns k olika sätt att skriva en given cykel med längden k , t.ex. ( 1 2 4 3 ) = ( 2 4 3 1 ) = ( 4 3 1 2 ) = ( 3 1 2 4 ).

(2.c) Slutligen: s ( k , 1) = k !/ k = ( k − 1)!.

(3) Det finns två olika sätt att konstruera en permutation av k element med j cykler:

(3.a) Om vi ​​vill att element k ska vara en fixpunkt kan vi välja en av s ( k − 1, j − 1) permutationer med k − 1 element och j − 1 cykler och lägg till element k som en ny cykel av längd 1. (

3.b) Om vi ​​vill att element k inte ska vara en fixpunkt kan vi välja en av s ( k − 1 , j ) permutationer med k − 1 -element och j- cykler och infoga element k i en befintlig cykel framför ett av k − 1 -elementen.

Vissa värderingar

k	j
	1	2	3	4	5	6	7	8	9	belopp
1	1									1
2	1	1								2
3	2	3	1							6
4	6	11	6	1						24
5	24	50	35	10	1					120
6	120	274	225	85	15	1				720
7	720	1,764	1 624	735	175	21	1			5 040
8	5 040	13 068	13.132	6,769	1 960	322	28	1		40 320
9	40 320	109,584	118,124	67,284	22,449	4,536	546	36	1	362,880
	1	2	3	4	5	6	7	8	9	belopp

Räknar permutationer efter antal fixpunkter

Värdet f ( k , j ) räknar antalet permutationer av k element med exakt j fixpunkter. För huvudartikeln om detta ämne, se rencontres numbers .

Egenskaper

(1) För varje j < 0 eller j > k : f ( k , j ) = 0.

(2) f (0, 0) = 1.

(3) För varje k > 1 och k ≥ j ≥ 0, f ( k , j ) = f ( k − 1, j − 1) + f ( k − 1, j )·( k − 1 − j ) + f ( k − 1, j + 1)·( j + 1)

Orsaker till fastigheter

(3) Det finns tre olika metoder för att konstruera en permutation av k element med j fixpunkter:

(3.a) Vi kan välja en av f ( k − 1, j − 1) permutationerna med k − 1 element och j − 1 fixpunkter och lägga till element k som en ny fixpunkt.

(3.b) Vi kan välja en av f ( k − 1, j ) permutationerna med k − 1 element och j fixpunkter och infoga element k i en existerande cykel av längd > 1 framför en av ( k − 1) − j element.

(3.c) Vi kan välja en av f ( k − 1, j + 1) permutationerna med k − 1 element och j + 1 fixpunkter och sammanfoga element k med en av j + 1 fixpunkter till en cykel av längd 2.

Vissa värderingar

k	j
	0	1	2	3	4	5	6	7	8	9	belopp
1	0	1									1
2	1	0	1								2
3	2	3	0	1							6
4	9	8	6	0	1						24
5	44	45	20	10	0	1					120
6	265	264	135	40	15	0	1				720
7	1 854	1 855	924	315	70	21	0	1			5 040
8	14,833	14,832	7 420	2,464	630	112	28	0	1		40 320
9	133,496	133,497	66,744	22 260	5,544	1,134	168	36	0	1	362,880
	0	1	2	3	4	5	6	7	8	9	belopp

Alternativa beräkningar

Ekvationer	Exempel
$f(k,1)=\sum _{i=1}^{k}(-1)^{i+1}{k \choose i}i(ki)!$	${\begin{aligned}f(5,1)&=5\ gånger 1\ gånger 4!-10\ gånger 2\ gånger 3!+10\ gånger 3\ gånger 2!-5\ gånger 4\ gånger 1!+1\ gånger 5\ gånger 0!\\&=120-120+60-20+5=45.\end{aligned}}$
$f(k,0)=k!-\sum _{i=1}^{k}(-1)^{i+1}{k \choose i}(ki)!$	${\begin{aligned}f(5,0)&=120-(5\ gånger 4!-10\ gånger 3!+10\ gånger 2!-5\ gånger 1!+1\ gånger 0!)\\&=120-(120-60+20-5+1)=120-76=44.\end{aligned}}$
För varje k > 1: $f(k,0)=(k-1)( f(k-1,0)+f(k-2,0))$	$f(5,0)=4\ gånger (9+2)=4\ gånger 11=44$
För varje k > 1: $f(k,0)=k!\sum _{i=2}^{k}(-1)^{i}/i!$	${\begin{aligned}f(5,0)&=120\ gånger (1/2-1/6+1/24-1/120)\\&=120\ gånger (60/ 120-20/120+5/120-1/120)=120\ gånger 44/120=44\end{aligned}}$
$f(k,0)\approx k!/e$ där e är Eulers tal ≈ 2,71828

Se även

• Cyklisk permutation
• Cykelnotation

Anteckningar

•   Brualdi, Richard A. (2010), Introductory Combinatorics (5:e upplagan), Prentice-Hall, ISBN 978-0-13-602040-0
•   Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms , Cambridge University Press, ISBN 0-521-45761-0
•   Gerstein, Larry J. (1987), Discrete Mathematics and Algebraic Structures , WH Freeman and Co., ISBN 0-7167-1804-9