Permutacja
![]() | Ten artykuł od 2013-10 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu. |
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[1]. 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ć[2] 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
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 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
Osobny artykuł: Złożenie funkcji.
Złożeniem permutacji jest permutacja zadana wzorem
- dla
- Przykład
Permutacja odwrotna
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
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Permutations_RGB.svg/220px-Permutations_RGB.svg.png)
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[3].
Zobacz też
Przypisy
- ↑ Permutacja, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2021-07-21] .
- ↑ Miklos Bona: Combinatorics of Permutations. CRC Press, 2004-07-25, s. 76.
- ↑ Joanna Wąsik, „Złamanie szyfru Enigmy przy użyciu teorii permutacji”, Instytut Matematyki Wydział Matematyki i Informatyki Uniwersytet Jagielloński. Plik w formacie PDF.
Linki zewnętrzne
Signature (permutation) (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-04-05].
- p
- d
- e
zagadnienia – znajdowanie liczby |
| ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
inne |
|
- p
- d
- e
pojęcia definiujące |
| ||||
---|---|---|---|---|---|
typy ciągów |
| ||||
przykłady ciągów liczb naturalnych | |||||
inne przykłady ciągów liczb | |||||
twierdzenia |
| ||||
powiązane pojęcia |
- p
- d
- e
pojęcia podstawowe |
| ||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
obraz |
| ||||||||||||||||||||||
przeciwobraz |
| ||||||||||||||||||||||
typy (rodzaje) |
| ||||||||||||||||||||||
pojęcia określone głównie dla działań jednoargumentowych | |||||||||||||||||||||||
złożenie funkcji (superpozycja) |
| ||||||||||||||||||||||
struktury definiowane funkcjami | |||||||||||||||||||||||
inne powiązane pojęcia | |||||||||||||||||||||||
twierdzenia | |||||||||||||||||||||||
uogólnienia |
|
- PWN: 4009487
- Britannica: topic/permutation
- Treccani: permutazione
- DSDE: permutation