Permutacje, czyli przestawianie

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?