Permutacja

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Niniejszy artykuł jest częścią cyklu kombinatoryka.




permutacja bez powtórzeń
permutacja z powtórzeniami


kombinacja bez powtórzeń
kombinacja z powtórzeniami


wariacja bez powtórzeń
wariacja z powtórzeniami


liczby Bella
liczby Catalana
liczby Stirlinga
liczby Eulera


zasada szufladkowa Dirichleta
zasada włączeń i wyłączeń


Permutacjawzajemnie 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[edytuj]

W celu skrócenia zapisu, szczególnie, gdy permutacji nie można zadać prostym wzorem, permutację zapisuje się jako

,

gdy dla , czyli permutacja przypisuje liczbie wartość .

Zapis macierzowy[edytuj]

Permutację można też zapisać jako macierz , taką, że .

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

Grupa permutacji[edytuj]

 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 permutacji[edytuj]

 Osobny artykuł: złożenie funkcji.

Złożeniem permutacji jest permutacja zadana wzorem

dla .
Przykład 
.

Permutacja odwrotna[edytuj]

 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 permutacji[edytuj]

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ą).

Cykle[edytuj]

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[edytuj]

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órzeniami[edytuj]

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[edytuj]

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

Przypisy