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