5600235761

7 Permutacje 18

7.1 Cykle

Cykl zbioru n-elementowego X to taka permutacja a zbioru X, dla której {x,a(x),a²(x),... , a^n_1(ar)} = X,

dla dowolnego x € X. Łatwo zauważyć, że jeśli dla pewnego aro € X mamy {aro, a(xo), Q²(aro),..., Q;^n-1(xo)} — X, to jest tak dla wszystkich ar G X, czyli a jest cyklem na X. Cykl a zbioru X zapisujemy jako

(ar,a(ar),... ,a^n-1(ar))

dla dowolnie wybranego ar G X.

Przykład 7.2. Rozważmy permutację a €. Sq daną przez tabelę:

n	0	1	2	3	4	5
a(n)	3	5	0	1	2	4

Zauważmy, że dla aro = 0 mamy

{0, a(0) = 3, a²(0) = l,a³(0) = 5,a⁴(0) =4,a⁵(0) = 2} = Z₆ zatem a = (0,3,1,5,4,2) jest cyklem.

Dowolną permutację 7r zbioru X można rozłożyć na rozłączne cykle w sposób następujący:

1.    wybieramy dowolny element ar € X, który nie jest jeszcze w żadnym cyklu,

2.    iterujemy permutację 7r otrzymując kolejno: ar,7r(ar),7T²(ar),7r³(ar),... aż do uzyskania 7r^J(ar) = ar,

3.    dodajemy do rozkładu cykl (ar, 7r(ar),..., 7r-^?_1(ar)),

4.    jeśli w zbiorze X pozostały jeszcze elementy niepokryte przez żaden cykl, to wracamy do pierwszego punktu naszej procedury.

Jeśli permutacja 7r złożona jest z k rozłącznych cykli, to zapisujemy ją 7r = (aro,... )(ari,...)... (ar^-i,...), gdzie w kolejnych nawiasach są elementy kolejnych cykli zaczynających się od odpowiednio: aro,ari,...,x^-i-

Przykład 7.3. Rozważmy jeszcze permutację 7r € Sg:

n	0	1	2	3	4	5	6	7	8
7r(n)	2	3	6	0	4	1	5	8	7

Rozkład n na cykle:

•    pierwszy cykl: 0,7r(0) = 2,7r(2) = 6,7r(6) = 5,7r(5) = l,7r(l) = 3,7r(3) = 0,

•    drugi cykl: 4, 7t(4) = 4,

•    trzeci cykl: 7, 7t(7) = 8, 7t(8) = 7,