Permutacja – jak obliczyć? Wzory i przykłady zastosowania
Permutacja to uporządkowanie wszystkich elementów danego zbioru. Dla n różnych elementów liczbę takich uporządkowań obliczamy ze wzoru Pn = n!, a gdy niektóre elementy są nierozróżnialne, dzielimy n! przez silnie liczebności powtarzających się grup.
Czym jest permutacja?
W najprostszym ujęciu permutacja oznacza ustawienie elementów w określonej kolejności. Jeśli trzy osoby oznaczymy literami A, B i C, mogą ustawić się w kolejce na sześć sposobów:
- ABC
- ACB
- BAC
- BCA
- CAB
- CBA
Formalnie permutacja jest wzajemnie jednoznacznym przekształceniem zbioru na siebie. W kombinatoryce skończonej można ją utożsamiać z każdym uporządkowaniem wszystkich elementów zbioru.
Każda permutacja ma trzy podstawowe cechy:
- obejmuje wszystkie elementy rozpatrywanego zbioru,
- każdy element występuje w niej dokładnie raz, jeśli mówimy o permutacji bez powtórzeń,
- kolejność elementów ma znaczenie.
Jak obliczyć permutację bez powtórzeń?
Dla zbioru złożonego z n różnych elementów liczba permutacji wynosi:
\(P_n=n!\)
Symbol \(n!\) oznacza silnię liczby \(n\). Definiuje się ją jako iloczyn wszystkich dodatnich liczb całkowitych od 1 do \(n\):
\(n!=1\cdot 2\cdot 3\cdot \ldots \cdot n\)
Dlaczego stosujemy mnożenie? W pierwszym miejscu można umieścić dowolny z \(n\) elementów. Po jego wyborze pozostaje \(n-1\) możliwości dla drugiego miejsca, następnie \(n-2\), aż do ostatniego miejsca, dla którego zostaje dokładnie jeden element. Zasada mnożenia daje więc \(n\cdot(n-1)\cdot\ldots\cdot1=n!\).
Przy małych zbiorach wartości wyglądają następująco:
| n | Wzór | Wynik (n!) |
|---|---|---|
| 1 | 1! | 1 |
| 2 | 2! | 2 |
| 3 | 3! | 6 |
| 4 | 4! | 24 |
| 5 | 5! | 120 |
Przykład dla zbioru \(\{1,2,3,4\}\):
\(P_4=4!=4\cdot3\cdot2\cdot1=24\)
Elementy można zatem ustawić w 24 różnych kolejnościach.
Jak obliczyć permutację z powtórzeniami?
Permutacja z powtórzeniami dotyczy sytuacji, w której część elementów jest identyczna i nie da się ich od siebie odróżnić. Wtedy zwykłe obliczenie \(n!\) zawyża wynik, ponieważ zamiana miejscami identycznych elementów nie tworzy nowego uporządkowania.
Jeżeli wszystkich elementów jest \(n\), a poszczególne grupy powtarzają się odpowiednio \(n_1,n_2,\ldots,n_k\) razy, stosujemy wzór:
\(P=\frac{n!}{n_1!\cdot n_2!\cdot\ldots\cdot n_k!}\)
Rozważmy słowo „MATEMATYKA”. Ma ono 10 liter. Występują w nim:
- litera A – 3 razy,
- litera M – 2 razy,
- litera T – 2 razy,
- litery E, Y i K – po 1 razie.
Liczbę różnych przestawień obliczamy więc tak:
\[
P=\frac{10!}{3!\cdot2!\cdot2!}
\]
\[
P=\frac{3\,628\,800}{6\cdot2\cdot2}
=\frac{3\,628\,800}{24}
=151\,200
\]
Słowo „MATEMATYKA” można zatem przestawić na 151 200 różnych sposobów. Dzielenie przez \(3!\), \(2!\) i \(2!\) usuwa powtórzenia wynikające z nierozróżnialności takich samych liter.
Zapis cyklowy i operacje na permutacjach
Permutację można zapisać macierzowo. Przykładowo:
\[
\sigma=
\begin{pmatrix}
1&2&3&4&5\\
2&3&1&5&4
\end{pmatrix}
\]
Oznacza to, że \(1\mapsto2\), \(2\mapsto3\), \(3\mapsto1\), \(4\mapsto5\), a \(5\mapsto4\). Ten sam zapis można skrócić, wykorzystując cykle:
\[
\sigma=(1\,2\,3)(4\,5)
\]
Cykl \((1\,2\,3)\) oznacza przejście \(1\to2\), \(2\to3\), \(3\to1\). Elementy pozostające na swoim miejscu zwykle pomija się. Każdą permutację można rozłożyć na rozłączne cykle, a cykle rozłączne można składać w dowolnej kolejności.
| Operacja | Znaczenie | Przykład |
|---|---|---|
| Składanie | Wykonanie jednej permutacji po drugiej | \((\sigma\circ\pi)(x)=\sigma(\pi(x))\) |
| Odwrotność | Odwrócenie każdego przejścia w cyklu | \((1\,2\,3)^{-1}=(1\,3\,2)\) |
| Potęgowanie | Wielokrotne zastosowanie tej samej permutacji | \((1\,2\,3)^2=(1\,3\,2)\) |
W składaniu trzeba zachować kolejność. Zapis \(\sigma\circ\pi\) oznacza, że najpierw działamy permutacją \(\pi\), a dopiero potem \(\sigma\). Składanie permutacji na ogół nie jest przemienne, więc zwykle \(\sigma\circ\pi\neq\pi\circ\sigma\).
Jak potęgować permutację zapisaną cyklami?
Jeżeli cykl ma długość \(m\), jego potęgi powtarzają się co \(m\). Dlatego wykładnik można zredukować modulo \(m\). Dla przykładu:
\[
(1\,2\,3\,4)^7=(1\,2\,3\,4)^{7\bmod4}=(1\,2\,3\,4)^3
\]
Przesunięcie w cyklu o trzy miejsca daje:
\[
(1\,2\,3\,4)^3=(1\,4\,3\,2)
\]
Gdy reszta z dzielenia wynosi 0, otrzymujemy permutację identycznościową:
\[
(1\,2\,3\,4)^4=(1\,2\,3\,4)^0=\operatorname{id}
\]
Dla potęg ujemnych korzysta się z permutacji odwrotnej. Na przykład:
\[
(1\,2\,3)^{-1}=(1\,3\,2)
\]
Ogólnie, jeśli cykl ma długość \(m\), wykładnik ujemny również redukuje się modulo \(m\). Dla \((1\,2\,3)^{-5}\) mamy \(-5\bmod3=1\), więc:
\[
(1\,2\,3)^{-5}=(1\,2\,3)^1=(1\,2\,3)
\]
Takie działania należą do podstaw teorii grup permutacji. Zbiór wszystkich permutacji danego zbioru wraz ze składaniem tworzy grupę permutacji. Permutacje są też wykorzystywane w kryptografii. Przykładem historycznego zastosowania był cyklometr Mariana Rejewskiego, używany w analizie szyfru maszyny Enigma.
Najważniejszy wybór podczas obliczeń dotyczy tego, czy elementy są rozróżnialne. Dla różnych elementów stosuje się \(n!\), a dla powtarzających się – iloraz \(n!\) i silni liczebności poszczególnych grup. Zapis cyklowy pozwala z kolei wygodnie wykonywać składanie, odwracanie i potęgowanie permutacji.
