✖

Permutacje

Kapitoly: Kombinatoryka, Wariacje, Permutacje, Kombinacje, Wariacje z powtórzeniami, Kombinacje z powtórzeniami, Ile jest różnych kodów PIN

Permutacja to szczególny przypadek wariacji, gdy mamy zbiór n-elementowy i chcemy ustalić liczbę wszystkich różnych ciągów n-wyrazowych.

Wzór

Przypomnijmy sobie wariacje. Mamy zbiór cyfr {1, 2, 3, 4, 5}. Ile liczb trzycyfrowych możemy z nich ułożyć, jeśli żadna cyfra nie może się powtarzać? To typowy przykład na wariacje, który można rozwiązać znanym wzorem

$$ V_5^3 = \frac{5!}{(5-3)!}=60. $$

A ile moglibyśmy ułożyć liczb pięciocyfrowych?

$$ V_5^5 = \frac{5!}{(5-5)!}=\frac{5!}{0!}=5!=120. $$

Możemy zauważyć, że jeśli mamy zbiór pięcioelementowy i szukamy liczby wszystkich różnych piątek, to wynik jest równy 5!. Możemy to uogólnić i powiedzieć, że jeśli mamy zbiór n-elementowy, to istnieje łącznie n! różnych ciągów n-wyrazowych. W ten sposób dochodzimy do pojęcia permutacji.

Co to jest permutacja

Jeśli mamy zbiór M, który ma n elementów, to permutacją nazywamy dowolny ciąg n-wyrazowy złożony z elementów zbioru M, w którym żaden element się nie powtarza. Przykład: jeśli mamy zbiór M = {a, b, c, d}, to permutacją jest na przykład (a, b, d, c) albo (d, b, a, c). Liczba wszystkich różnych permutacji jest równa

$$ P_n = V_n^n = n! $$

Rozwiązane przykłady

  1. Masz sześć książek i chcesz je ustawić na półce w jakiejś kolejności. Ile jest wszystkich różnych kolejności? Mamy sześć książek i za każdym razem permutujemy wszystkie książki, więc wynik jest równy P6 = 6! = 720.

  2. Do twoich 6 polskich książek z poprzedniego przykładu doszły 4 książki napisane po łacinie. Na ile sposobów możesz ustawić tych 10 książek na półce, jeśli chcesz mieć wszystkie polskie obok siebie i wszystkie łacińskie obok siebie?

    Jakie mamy możliwości ustawienia książek? Możemy najpierw ustawić sześć polskich książek, a potem cztery łacińskie, albo odwrotnie — najpierw cztery łacińskie, a potem sześć polskich. Przy tym istnieje 6! sposobów ustawienia polskich książek i 4! sposobów ustawienia łacińskich. Stosujemy regułę mnożenia i mnożymy te wyniki: 6! · 4! = 17 280. Ponieważ istnieją dwie możliwości ułożenia grup książek (polskie, potem łacińskie, i odwrotnie), tę liczbę mnożymy jeszcze przez dwa. Ostateczny wynik to 17 280 · 2 = 34 560.