✖

Permutacja

Kapitoly: Kombinatoryka, Wariacje, Permutacja, Kombinacja, Wariacje z powtórzeniami, Kombinacje z powtórzeniami, Ile jest różnych kodów PIN?, Kalkulator.

Permutacja jest szczególnym przypadkiem wariacji, gdzie mamy zbiór o rozmiarze n i chcemy znaleźć liczbę wszystkich różnych n-tic.

Wzór

Przyjrzyjmy się samym wariacjom. Biorąc pod uwagę zbiór cyfr {1, 2, 3, 4, 5}, ile liczb trzycyfrowych możemy z nich skonstruować, jeśli żadna cyfra nie może się powtórzyć? Jest to typowy przykład wariacji, którą można rozwiązać za pomocą znanego wzoru

$$ V(k, n) = \frac{n!}{(n-k)!}=\frac{5!}{(5-3)!}=60. $$

Ile liczb pięciocyfrowych możemy ułożyć?

$$ V(k, n) = \frac{5!}{(5-5)!}=\frac{5!}{0!}=5!=120. $$

Możemy zauważyć, że jeśli mamy zbiór pięciu elementów i szukamy liczby wszystkich różnych piątek, wynik jest równy 5!. Możemy to uogólnić i powiedzieć, że jeśli mamy zbiór n elementów, istnieje w sumie n! różnych n-tyków. To prowadzi nas do pojęcia permutacji.

Czym jest permutacja?

Jeśli mamy zbiór M o rozmiarze n, to permutacja jest dowolną n-tice składającą się z elementów ze zbioru M, przy czym żaden element nie może się powtarzać. Przykład: jeśli mamy zbiór M = {a, b, c, d}, to permutacją jest na przykład [a, b, d, c] lub [d, b, a, c]. Liczba wszystkich różnych permutacji jest równa

$$ P(n) = V(n, n) = n! $$

Rozwiązane przykłady

  1. Masz w sumie sześć książek i chcesz ułożyć je na półce w pewnej kolejności. Ile jest w sumie różnych porządków? Mamy sześć książek, permutując wszystkie książki za każdym razem, więc wynik jest równy P(6) = 6! = 720.

  2. Oprócz 6 czeskich książek z poprzedniego przykładu są jeszcze 4 książki napisane po łacinie. Na ile różnych sposobów można odłożyć na półkę te 10 książek, jeśli chcemy mieć przy sobie wszystkie czeskie książki i wszystkie łacińskie książki?

    Jakie mamy opcje przechowywania książek? Możemy najpierw umieścić sześć czeskich książek, a następnie cztery łacińskie książki lub odwrotnie - najpierw cztery łacińskie książki, a następnie sześć czeskich książek. Istnieją jednak 6! sposoby przechowywania czeskich książek i 4! sposoby przechowywania łacińskich książek. Używamy reguły iloczynu kombinatorycznego i dodajemy te wyniki: 6! · 4! = 17 280 Ponieważ istnieją dwa sposoby przechowywania książek (czeskie, a następnie łacińskie i odwrotnie), mnożymy tę liczbę przez dwa. Całkowity wynik to 17 280 · 2 = 34 560.

Zasoby i dalsze lektury