Permutacja

Permutacja ( „zmiana, wymiana”) – wzajemnie jednoznaczne przekształcenie pewnego zbioru na siebie. Najczęściej termin ten oznacza funkcję na zbiorach skończonych.

Permutacje zbiorów skończonych mogą być utożsamiane z ustawianiem elementów zbioru w pewnej kolejności. W poniższym artykule zbiór wszystkich permutacji zbioru  będzie oznaczany  jeżeli  to zapisywany on będzie symbolem  (zob. pozostałe oznaczenia w artykule o grupach permutacji).

Zapis 
Dla permutacji zbiorów skończonych stosuje się specjalne oznaczenia. Niech  wówczas zapisuje się ją jako
 

gdzie  dla

Zapis macierzowy 
Permutację  można też zapisać jako macierz  dla której

Alternatywnie jako macierz

Oba przyporządkowania różnią się o transpozycję wynikowej macierzy, tzn. dla dowolnej  mamy, że 

Reprezentacja w postaci  jest izomorfizmem grupy  z operacją składania funkcji na odpowiednią podgrupę grupy macierzy  z operacją mnożenia macierzy, tzn.:

dla dowolnych 

Reprezentacja w postaci macierzy  jest bijektywnym antyhomomorfizmem:

Na przykład dla permutacji  mamy, postacie macierzowe 

oraz

Grupa permutacji 

Zbiór  wszystkich permutacji zbioru  wraz z działaniem składania funkcji stanowi grupę nazywaną grupą permutacji. Jeśli  jest zbiorem -elementowym, to grupa  jest izomorficzna z  niech  będzie bijekcją. Wówczas odwzorowanie
 

jest izomorfizmem grup. Podobnie można pokazać, że jeśli zbiory  są równoliczne, to grupy  są izomorficzne, a więc nierozróżnialne na gruncie teorii grup.

Rząd grupy  czyli moc zbioru wszystkich permutacji zbioru -elementowego, to możliwa liczba uporządkowań tego zbioru równa  gdzie wykrzyknik oznacza silnię. W kombinatoryce na oznaczenie liczności tego zbioru stosuje się również symbol

Składanie permutacji 

Złożeniem permutacji  jest permutacja  zadana wzorem
  dla 

 Przykład

Permutacja odwrotna 

Permutacja  odwrotna do permutacji  odwzorowującej wiersz górny na dolny to permutacja odwzorowująca dolny wiersz na górny: aby uzyskać jej zapis, należy zamienić porządek wierszy i (dla wygody) uporządkować rosnąco kolumny.

W zapisie macierzowym, macierz permutacji  odwrotnej do permutacji  to transpozycja macierzy permutacji 

 Przykład Jeśli  to
 

 W zapisie macierzowym, ta sama permutacja  ma macierz: 
 a permutacja  odwrotna do  ma macierz

Znak permutacji 
Znak permutacji definiuje się jako znak wyznacznika macierzy tej permutacji.
Można na to spojrzeć też w inny sposób: każdą permutację można otrzymać za pomocą złożenia różnych liczb przestawień (transpozycji) par elementów. Takie przedstawienie permutacji nie jest jednoznaczne i można zmienić liczbę użytych transpozycji, niemniej jednak liczba transpozycji w takiej reprezentacji jest zawsze albo parzysta, albo nieparzysta. Inaczej mówiąc, parzystość liczby transpozycji jest niezmiennikiem tej operacji. Wynika to z faktu, że każda transpozycja zmienia całkowitą liczbę inwersji o liczbę nieparzystą. Permutację, która ma parzystą liczbę inwersji nazywamy parzystą (lub dodatnią), zaś jeśli ma ona nieparzystą liczbę inwersji, to nazywamy ją permutacją nieparzystą (lub ujemną).

Cykle 
Cyklem nazywamy każdą permutację postaci:
 

Zazwyczaj, gdy operujemy na cyklach opuszczamy część:  gdyż nie wnosi ona nic nowego.

Zapis cyklu możemy jeszcze uprościć. Wystarczy zauważyć, że dolny wiersz naszego symbolu oznaczającego cykl można jednoznacznie odtworzyć z górnego. Zatem nasz ostateczny uproszczony symbol przybiera postać:
 

Można udowodnić (choć jest to dość intuicyjne), że każdą permutację można przedstawić jako złożenie  rozłącznych (niezależnych), a więc i różnych, cykli. Ponieważ cykle są różne i wszystkie należą do zbioru  o ilości elementów  więc 

Składanie permutacji, podobnie jak większości funkcji, nie jest przemienne. Nie dotyczy to sytuacji, gdy składamy permutacje rozłączne (niezależne). Ponieważ permutacjami rozłącznymi są rozłączne cykle to zachodzi następujące twierdzenie:
  gdzie  jest rozkładem permutacji  na  rozłącznych cykli.

 Przykłady
 Cyklem jest permutacja:
  którą można zapisać jako 

 Rozkład na cykle

Kombinatoryka

Permutacja bez powtórzeń 
Permutacja jest szczególnym przypadkiem wariacji bez powtórzeń.

Definicja:
Permutacją bez powtórzeń zbioru złożonego z n różnych elementów nazywamy każdy n wyrazowy ciąg utworzony ze wszystkich wyrazów zbioru. Wszystkich możliwych permutacji zbioru n-elementowego jest:
 

Przykład: Elementy zbioru  można ustawić w ciąg na  sposobów: 

Wyjaśnienie: W każdej z permutacji mamy do zapełnienia trzy wolne miejsca. W pierwszym z nich możemy umieścić dowolną z liter na trzy sposoby  na drugim dowolną spośród pozostałych jeszcze dwóch liter na dwa sposoby  itd. Na ostatnim miejscu musi znaleźć się ostatnia dostępna litera (element zbioru), a zatem możemy to zrobić tylko na jeden sposób. Ostatecznie otrzymujemy:

Permutacja z powtórzeniami 
Niech  oznacza zbiór złożony z  różnych elementów  Permutacją  elementową z powtórzeniami, w której elementy  powtarzają się odpowiednio  razy,  jest każdy -wyrazowy ciąg, w którym elementy  powtarzają się podaną liczbę razy.

Liczba takich permutacji z powtórzeniami wynosi 

Przykład:
Przestawiając litery  można otrzymać  różnych napisów.

Wyjaśnienie:
„Zwykłe” przestawianie liter w słowie babka spowoduje kilkukrotne powstanie identycznych wyrazów, np. zamieniając miejscami pierwszą i trzecią literę znów otrzymamy słowo babka. Należy to uwzględnić przy zliczaniu, dlatego rezultat trzeba podzielić każdorazowo przez liczbę „zbędnych” permutacji, które nie prowadzą do powstania nowych słów (ciągów uporządkowanych).

Spostrzeżenie:
Można wobec tego zapisać wzór na permutację bez powtórzeń następująco:  (każdy z elementów występuje dokładnie raz).

Urządzenia do wyliczania permutacji matematycznych 
Urządzeniem do wyliczania cyklicznych permutacji był wynaleziony w połowie lat trzydziestych przez polskiego matematyka i kryptologa Mariana Rejewskiego cyklometr. Służył on polskiemu wywiadowi do łamania kodów niemieckiej maszyny szyfrującej Enigma.

Zobacz też 
 Nieporządek

Przypisy 

Teoria grup skończonych
Kombinatoryka