dz na permutacjach
1
1
Działania na permutacjach.
W tym celu permutację zapisujemy w postaci
=
n
a
a
a
n
f
...
...
2
1
2
1
albo f ( i ) = a
i
i= 1, 2, ... , n
- element stojący na miejscu i przenieś na miejsce a
i
.
Zbiór permutacji n- elementowych oznaczymy symbolem S
n
.
Składanie permutacji.
Składanie permutacji wykonuje się podobnie jak składanie innych
funkcji. Niech będą dane dwie permutacje
=
2
5
1
4
3
5
4
3
2
1
f
=
3
4
1
5
2
5
4
3
2
1
g
Złożeniem permutacji f i g jest permutacja f g = ( f ( g))
=
1
5
3
2
4
5
4
3
2
1
fg
Istotna jest kolejność operacji. W wyniku złozenia gf = g( f )
otrzymujemy
=
5
3
2
4
1
5
4
3
2
1
gf
Składanie permutacji jest na ogół nieprzemienne. Natomiast jest
działaniem łącznym
f ( g ( h )) = (f g) h = f (g h) .
Permutacja identycznościowa.
Permutację identycznościową oznaczymy literą e. Jest to permutacja
dz na permutacjach
2
2
=
n
n
e
...
3
2
1
...
3
2
1
lub inaczej e( i ) = i i = 1,2, ..., n
Dla każdej permutacji f
∈ S
n
zachodzi f e = e f = f
Permutacja odwrotna.
Permutacją odwrotną do danej permutacji f jest permutacja, dla której
f
-1
f = e.
Jeżeli f ( i ) = j , to f
-1
( j ) = i .
Przykład.
Wyznaczyć permutację odwrotną do permutacji
a)
=
2
5
1
4
3
5
4
3
2
1
f
b)
=
3
4
1
5
2
5
4
3
2
1
g
Korzystamy z własności: jeżeli f ( i ) = j , to f
-1
( j ) = i .
Permutację odwrotna do f otrzymujemy zamieniając wiersz górny z
dolnym, po czym, dla uzyskania bardziej przejrzystej tablicy
sortujemy ją w/g elementów górnego wiersza
=
=
−
4
2
1
5
3
5
4
3
2
1
5
4
3
2
1
2
5
1
4
3
1
f
Można sprawdzić, że f
-1
f = e . Istotnie,
e
f
f
=
=
=
−
5
4
3
2
1
5
4
3
2
1
2
5
1
4
3
5
4
3
2
1
4
2
1
5
3
5
4
3
2
1
1
A także
e
f
f
=
=
=
−
5
4
3
2
1
5
4
3
2
1
4
2
1
5
3
5
4
3
2
1
2
5
1
4
3
5
4
3
2
1
1
dz na permutacjach
3
3
Podobnie dla permutacji g
=
=
−
2
4
5
1
3
5
4
3
2
1
5
4
3
2
1
3
4
1
5
2
1
g
oraz
e
g
g
=
=
=
−
5
4
3
2
1
5
4
3
2
1
3
4
1
5
2
5
4
3
2
1
2
4
5
1
3
5
4
3
2
1
1
Jak łatwo można sprawdzić, także g g
-1
= e.
Transpozycja
Jest to permutacja, która zamienia miejscami tylko dwa elementy, a
pozostałe zostawia bez zmian.
Przykłady transpozycji
=
6
2
4
3
5
1
6
5
4
3
2
1
p
=
5
1
3
2
4
5
4
3
2
1
q
Permutację można przedstawić jako złożenie transpozycji – przy czym
rozkład ten nie jest jednoznaczny. Przykład takiego rozkładu:
=
=
4
5
3
2
1
5
4
3
2
1
5
2
3
4
1
5
4
3
2
1
5
4
1
2
3
5
4
3
2
1
2
5
1
4
3
5
4
3
2
1
f
Rozkład permutacji na transpozycje nie jest jednoznaczny, ale
niezmiennicza jest parzystość liczby transpozycji. Dlatego mówimy o
permutacjach parzystych bądź nieparzystych.
Każda transpozycja zmienia liczbę inwersji (nieporządków) o liczbę
nieparzystą.
Inwersją jest liczba tych elementów ciągu (a
1
, a
2
, .. , a
k
} dla których
a
j
> a
k
przy j < k.
dz na permutacjach
4
4
Cykle
Cyklem nazywamy permutacje postaci
=
−
+
−
+
−
n
n
k
k
n
n
k
k
k
a
a
a
a
a
a
a
a
a
a
a
a
a
a
f
1
1
1
3
2
1
1
1
2
1
...
...
...
...
Zwykle przy zapisie opuszczamy część tablicy która nie wnosi zmian
i operując na cyklach zapisujemy krócej
=
−
1
3
2
1
2
1
...
...
a
a
a
a
a
a
a
a
f
k
k
k
Często jest stosowany jeszcze krótszy zapis cyklu
(
)
n
k
k
k
a
a
a
a
a
a
a
a
a
a
a
f
,...,
,
...
...
2
1
1
3
2
1
2
1
=
=
−
Dowodzi się, że każdą permutację można przedstawić jako złożenie
pewnej liczby cykli.
Przykład rozkładu na cykle
=
=
2
6
4
3
5
1
6
5
4
3
2
1
6
5
1
3
4
2
6
5
4
3
2
1
6
1
4
5
2
3
6
5
4
3
2
1
4
6
3
5
1
2
6
5
4
3
2
1
g
lub krócej
=
=
2
6
5
6
5
2
1
4
2
4
2
1
1
5
3
5
3
1
4
6
3
5
1
2
6
5
4
3
2
1
g
albo jeszcze krócej
(
)(
)(
)
6
5
2
4
2
1
5
3
1
=
g