Kółko 24 I 2004 - Permutacje

Teoria

1. Permutacja to zamiana elementów. Jeśli mamy zbiór X i ma on n ∈ ℕ elementów, to f : X → X, jeśli jest bijekcj _{}a, to jest to permutacja. Permutacj_{}e zapisujemy np. tak: < a_{1}, a_{2}, …, a_{n} >, tzn., że i przechodzi na a_{i}.

2. Jest n! permutacji zbioru mocy n (o n elementach).

3. Każd _{}a permutacj_{}e można rozłożyć na rozł _{}aczne cykle.

4. Transpozycja to zamiana dwóch elementów. Każda permutacja jest złożeniem transpozycji (niekoniecznie rozł _{}acznych).

5. Inwersja w permutacji < a_{1}, a_{2}, …, a_{n} >, to para i, j taka, że i < j i a_{i} > a_{j}.

6. Jeśli permutacja ma parzyst _{}a ilośc inwersji, to nazywamy j _{}a parzyst _{}a, jeśli ma nieparzyst _{}a ilość inwersji, to nazywamy j _{}a nieparzyst _{}a. Jeśli f to permutacja i I(f) liczba inwersji, to sgn(f) = (−1)^{I(f)} .

7. Znak złożenia to iloczyn znaków (sgn(f ∘ g) = sgn(f) · sgn(g)).

8. Znak cyklu długości k, to (−1)^{k−1} .

9. Permutacja jest parzysta ⇔ ma parzyście wiele cyklów parzystej długości. Zadania

1. Dowody fakcików numer 4, 6, 7, 8, 9.

2. Oblicz ile jest permutacji parzystych zbioru n elementowego.

3. Rozstrzygnij, czy z pierwszej tabliczki można przejść do drugiej tabliczki w popularnej grze przesuwania klocków. Możemy przesuwać dowolny s _{}asiaduj _{}acy z pustym miejscem klocek na puste miejsce.

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14

4. Przy okr _{}agłym stole siedzi n osób. Co minut_{}e zmieniaj _{}a oni miejsca, z tym, że zawsze w ten sam sposób (tzn. np. osoba z krzesła nr 1 zawsze idzie na krzesło nr 5 itd., żadne dwie oczywiście nie mog _{}a przejść na to samo krzesło). Rozstrzygnij, czy na pewno po pewnym czasie wróc _{}a oni do pocz _{}atkowego położenia, a jeśli tak, to ile maksymalnie czasu może im to zaj _{}ać jeśli n = 28.

5. Dany jest zbiór liczb od 1 do n + 1. Mówimy, ze dwie uporz _{}adkowane n-tki s _{}a ze sob _{}a zaprzyjaznione, gdy istniej _{}a takie różne indeksy i oraz j, że na i-tym indeksie w pierwszej n-tce jest ta sama liczba, która jest na j-tym indeksie w drugiej n-tce. Wyznaczyc maksymaln _{}a moc zbioru n-tek, takiego, ze każde dwie s _{}a ze sob _{}a zaprzyjaźnione.