Permutacja (przestawienie) to każde ustawienie elementów danego zbioru w jakiejś kolejności. Liczba permutacji mówi, na ile sposobów możemy ustawić elementy zbioru w kolejce.
Jeśli zbiór ma n elementów i chcemy ustawić je w kolejce, to musimy podjąć n wyborów dotyczących tego, jaki element ustawić na kolejnym miejscu.
- I decyzja - pierwszy element do kolejki można wybrać na n sposobów,
- II decyzja - drugi element do kolejki można wybrać na n-1 sposobów (bo jeden jest już wykorzystany)
- III decyzja - trzeci element do kolejki można wybrać na n-2 sposoby (bo 2 elementy są już wykorzystane),
- itd.
- n-1-wsza decyzja - przedostatni element do kolejki można wybrać na 2 sposoby,
- n-ta decyzja - ostatni element kolejki można wybrać na 1 sposób (bo tylko jeden element jeszcze został).
Zatem - zgodnie z regułą iloczynu - liczba możliwych wyborów kolejności to:
n×(n-1)×(n-2)×...×2×1
Jest to iloczyn liczb naturalnych od 1 do n. Oznaczamy go n! (czytaj: en silnia). Liczbę możliwych permutacji (przestawień) n elementów zapisujemy tak: P(n) = n!.
Przykłady
1) Na ile sposobów można ustawić pięciu uczniów w kolejce do automatu z napojami?
Rozwiązanie. Pierwszy w kolejce może ustawić się dowolny uczeń. Gdy on już stoi, jako drugi może ustawić się dowolny z czterech pozostałych uczniów itd. Jako ostatni - piąty w kolejce - zostaje tylko jeden uczeń. Zatem możliwych ustawień uczniów w kolejce jest 5! = 5×4×3×2×1 = 120.
2) Na ile sposobów można ustawić w kolejce do automatu z napojami 6 uczniów i 4 uczennice, jeżeli:
a) panowie są dżentelmenami i przepuszczają dziewczynki przodem?
b) panowie nie byli grzeczni i wepchnęli się przed dziewczynki?
c) kolejność dzieci nie zależy od płci?
Rozwiązanie. a) Dziewczynki można ustawić w obrębie czterech pierwszych miejsc w kolejce na 4! = 4×3×2×1 = 24 sposoby, a chłopców na kolejnych sześciu miejscach na 6! = 6×5×4×3×2×1 = 720 sposobów. Każde ustawienie dziewczynek może wystąpić z każdym z 720 ustawień chłopców. Wyboru kolejności uczennic i uczniów dokonujemy niezależnie, więc (korzystając z reguły iloczynu) mamy 4!×6! = 24×720 = 17 280 różnych możliwych ustawień wszystkich dzieci w kolejce (takich, że dziewczynki stoją z przodu).
b) Możliwych ustawień jest tyle samo.
c) Ustawiamy w kolejce dziesięcioro dzieci, co można zrobić na 10! = 10×9×8×...×3×2×1 =
3 628 800 sposobów.
A teraz spróbuj sam
1) Siedmioro spóźnionych na lekcję uczniów ma zająć siedem pozostałych w klasie wolnych miejsc. Na ile sposobów mogą to zrobić?
2) Na kółko taneczne uczęszcza 12 chłopców i 12 dziewczyn. Na ile sposobów można połączyć chłopców i dziewczęta w pary do poloneza?
3) Ile słów (niekoniecznie mających sens) można ułożyć ze wszystkich liter wyrazu EUROPA? A ile ze wszystkich liter wyrazu AMERYKA?
Ad zad 2
Czy w zadaniu 2 nie powinno być przypadkiem 12!x12!?
Pary do tańca
Zależy, jak rozumieć pytanie, tzn. czy istotna jest kolejność par - samo połączenie w pary można zrealizować na 12! sposobów; jeśli natomiast po zestawieniu par mielibyśmy jeszcze utworzyć z nich polonezowy korowód (czyli ustawienie pary p1 za p2 byłoby innym niż p2 za p1), to odpowiedzią byłoby faktycznie 12!x12!.