Permutacja

Permutacja w matematyce oznacza uporządkowany ciąg elementów, gdzie każdy element z danego zbioru może pojawić się tylko raz (w przypadku permutacji bez powtórzeń) lub więcej razy (w przypadku permutacji z powtórzeniami). Permutacje są szczególnym przypadkiem wariacji, gdzie liczba wybranych elementów jest równa liczbie wszystkich elementów w zbiorze.

Permutacja bez powtórzeń

Permutacja bez powtórzeń to taki przypadek, w którym każdy element zbioru pojawia się dokładnie raz.

Liczba możliwych permutacji \( n \)-elementowego zbioru jest opisana wzorem: \[ P_n = n! \] Gdzie:

• \( n! \) (n silnia) to iloczyn wszystkich liczb całkowitych od 1 do \( n \).

Przykład

Rozważmy zbiór \( A = \{a, b, c\} \). Chcemy ustalić, ile jest możliwych sposobów na ułożenie wszystkich elementów tego zbioru w różnych kolejnościach.

Dla zbioru \( A \) liczba permutacji wynosi: \[ P_3 = 3! = 3 \cdot 2 \cdot 1 = 6 \] To oznacza, że istnieje 6 różnych permutacji zbioru \( A \): \( abc, acb, bac, bca, cab, cba \).

Wyjaśnienie

Aby to zrozumieć, wyobraź sobie, że mamy trzy miejsca do wypełnienia i musimy umieścić w nich elementy zbioru \( \{a, b, c\} \).

• Na pierwszym miejscu możemy umieścić dowolny z trzech elementów, więc mamy 3 możliwości.
• Na drugim miejscu możemy umieścić dowolny z pozostałych 2 elementów, więc mamy 2 możliwości.
• Na ostatnim miejscu zostaje nam już tylko 1 element, który możemy tam umieścić. Ostatecznie liczba możliwych permutacji to: \[ P_3 = 3 \cdot 2 \cdot 1 = 3! \]

Permutacja z powtórzeniami

Permutacja z powtórzeniami oznacza, że niektóre elementy zbioru mogą się powtarzać. Liczba permutacji \( n \)-elementowego zbioru, gdzie pewne elementy mogą się powtarzać, jest wyrażona wzorem: \[ P = \frac{n!}{n_1! \cdot n_2! \cdot \dots \cdot n_k!} \] Gdzie:

• \( n \) to liczba wszystkich elementów w zbiorze,
• \( n_1, n_2, \dots, n_k \) to liczba powtórzeń poszczególnych elementów.

Przykład

Weźmy słowo matematyka, które składa się z 10 liter, z czego litery a powtarza się 3 razy i m oraz t powtarza się po 2 razy. Liczba możliwych różnych permutacji tego słowa wynosi: \[ P = \frac{10!}{3! \cdot 2! \cdot 2!} = \frac{3628800}{6 \cdot 2 \cdot 2} = \frac{3628800}{6 \cdot 2 \cdot 2} = 151200 \] Oznacza to, że istnieje 151200 różnych sposobów na ułożenie liter w słowie matematyka.

Wyjaśnienie

Bez uwzględnienia powtórzeń, liczba permutacji wynosiłaby \( 10! = 3628800 \). Jednak ponieważ litery a powtarza się 3 razy oraz m i t powtarzają się po 2 razy, musimy podzielić tę liczbę przez liczbę permutacji powtarzających się elementów: \[ P = \frac{151200}{3! \cdot 2! \cdot 2!} = 151200 \]

• Dzielimy przez \( 3! \), bo każda zamiana miejsc tych samych liter a nie tworzy nowego układu,
• Dzielimy przez \( 2! \), bo każda zamiana miejsc tych samych liter m nie tworzy nowego układu,
• Dzielimy przez \( 2! \), bo każda zamiana miejsc tych samych liter t nie tworzy nowego układu,

więc te powtórzenia należy "usunąć" z liczby permutacji.

Zastosowania

• Kombinatoryka: Permutacje są stosowane w wielu problemach związanych z liczeniem możliwych układów elementów.
• Algorytmy: Permutacje są ważne w analizie algorytmów, zwłaszcza w generowaniu różnych kombinacji i analizowaniu wyników.
• Szyfrowanie: W kryptografii permutacje są używane do mieszania i porządkowania danych, co zwiększa bezpieczeństwo.

Permutacje są kluczowym narzędziem w kombinatoryce i wielu dziedzinach matematyki oraz nauk ścisłych, umożliwiając analizowanie różnych sposobów na porządkowanie elementów.