Otwórz menu główne

Permutacja

wzajemnie jednoznaczne przekształcenie pewnego zbioru na siebie

Permutacja (łac. permutatio – „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).

Spis treści

ZapisEdytuj

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

 

gdzie   dla  

Zapis macierzowyEdytuj

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

Na przykład permutację   można zapisać jako  

Grupa permutacjiEdytuj

Osobny artykuł: 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  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 permutacjiEdytuj

Osobny artykuł: złożenie funkcji.

Złożeniem permutacji   jest permutacja   zadana wzorem

  dla  
Przykład
 

Permutacja odwrotnaEdytuj

Osobny artykuł: funkcja 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 permutacjiEdytuj

Znak permutacji definiujemy 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 ilości przestawień (transpozycji) par elementów. Takie przedstawienie permutacji nie jest jednoznaczne i można zmienić ilość 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ą).

CykleEdytuj

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
 

KombinatorykaEdytuj

Permutacja bez powtórzeńEdytuj

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órzeniamiEdytuj

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 matematycznychEdytuj

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[1].

PrzypisyEdytuj