Kalkulator Permutacji

Nasz kalkulator permutacji pozwala szybko i precyzyjnie obliczyć liczbę sposobów, na jakie można ułożyć n różnych obiektów, wybierając z nich próbkę składającą się z r elementów. Narzędzie to ułatwia ustalenie liczby możliwych układów w sytuacjach, w których kolejność elementów ma kluczowe znaczenie. W matematyce całkowitą liczbę dostępnych obiektów oznaczamy jako n, natomiast wielkość wybieranej grupy jako r.

Na przykład, chcąc ułożyć litery XYZ w dwuliterowe ciągi, otrzymamy następujące warianty: XY, XZ, YZ, YX, ZX oraz ZY. Daje to łącznie 6 różnych układów (permutacji).

Aby użyć tego kalkulatora, po prostu wpisz n (całkowitą liczbę obiektów) oraz r (liczbę elementów w każdej grupie), a następnie kliknij przycisk „Oblicz”.

Permutacje

Permutacja zbioru to nic innego jak uporządkowanie jego elementów w określoną sekwencję lub ciąg. Jeśli dany zbiór jest już ułożony, mówimy o permutacji jego elementów. Kluczową cechą permutacji jest to, że kolejność elementów ma znaczenie. Przykładowo, układy AB i BA to dwie zupełnie różne permutacje. Liczbę permutacji n obiektów wybieranych z r elementowej próby oznacza się powszechnie symbolem ₙPᵣ.

Sposób obliczania liczby permutacji zależy od specyfiki analizowanych obiektów oraz od tego, czy dopuszczamy ich powtarzanie. O ile nie zaznaczono inaczej, w klasycznych zadaniach zakładamy, że mamy do czynienia z permutacjami bez powtórzeń. W niniejszym artykule skupimy się właśnie na takich przykładach.

Permutacje opierają się na podstawowej regule mnożenia (nazywanej też zasadą wielokrotnego wyboru). Mówi ona, że jeśli pewien proces składa się z k niezależnych zdarzeń, z których pierwsze można zrealizować na n₁ sposobów, drugie na n₂ sposobów, i tak dalej, aż do zdarzenia nₖ, to całkowita liczba możliwych scenariuszy jest równa iloczynowi tych wartości: n₁ × n₂ × ... × nₖ.

Załóżmy, że chcemy poznać liczbę możliwych układów liter ABC bez powtórzeń. Każda z liter może znaleźć się na pierwszej pozycji, co daje nam 3 sposoby wyboru.

Po umiejscowieniu pierwszej litery zostają nam dwie, więc mamy 2 sposoby wyboru litery na drugą pozycję. Po obsadzeniu drugiego miejsca pozostaje już tylko jedna litera, co daje 1 sposób na wypełnienie trzeciej pozycji.

Zgodnie z regułą mnożenia istnieje zatem 3 × 2 × 1 = 6 sposobów ułożenia liter ABC. Tymi układami są: ABC, ACB, BCA, BAC, CAB oraz CBA.

Silnia

W powyższym przykładzie udowodniliśmy, że liczba permutacji 3 różnych obiektów wynosi 3 × 2 × 1 = 6. Uogólniając tę zasadę, całkowitą liczbę permutacji zbioru składającegocego się z n elementów wyraża się za pomocą działania n × (n-1) × (n-2) × ... × 1.

Jest to iloczyn wszystkich kolejnych liczb całkowitych od 1 do n. Takie mnożenie w matematyce nazywamy silnią i oznaczamy znakiem wykrzyknika (!).

Wzór wygląda więc następująco: n! = n × (n-1) × (n-2) × ... × 1 (czytamy jako: n silnia).

Warto również zapamiętać ważne właściwości silni: 0! = 1 oraz 1! = 1.

Przykład Permutacji

Standardowa bieżnia lekkoatletyczna na Igrzyskach Olimpijskich zazwyczaj posiada 9 torów. Jednakże w sprincie na 100 metrów pierwszy tor często pozostaje wolny. Ośmiu biegaczy zajmuje więc tory od 2 do 9. Na ile różnych sposobów można rozmieścić ośmiu zawodników na tych ośmiu torach?

Stosując podstawową regułę mnożenia:

• dowolny z 8 biegaczy może zająć tor 2,
• dowolny z pozostałych 7 biegaczy może zająć tor 3,
• dowolny z pozostałych 6 biegaczy może zająć tor 4,
• dowolny z pozostałych 5 biegaczy może zająć tor 5,
• dowolny z pozostałych 4 biegaczy może zająć tor 6,
• dowolny z pozostałych 3 biegaczy może zająć tor 7,
• dowolny z pozostałych 2 biegaczy może zająć tor 8,
• ostatni zawodnik zajmuje tor 9.

Dlatego całkowita liczba możliwych permutacji 8 biegaczy ustawionych na 8 torach wynosi 8! = 8 × 7 × 6 × ... × 2 × 1 = 40 320 sposobów.

Korzystając z naszego kalkulatora permutacji, wystarczy wprowadzić cyfrę 8 zarówno w polu n (liczba obiektów), jak i r (próbka) i kliknąć „Oblicz”, aby błyskawicznie otrzymać wynik 40 320.

Permutacja Podzbiorów

W poprzednich przykładach analizowaliśmy permutacje, w których do stworzenia układu wykorzystywane są absolutnie wszystkie dostępne obiekty. Często spotykamy się jednak z sytuacjami, w których obiekty wybierane są do mniejszych grup (w polskiej terminologii matematycznej nazywa się to wariacjami bez powtórzeń).

W takich przypadkach całkowitą liczbę dostępnych obiektów oznaczamy jako n, a wielkość mniejszej grupy (próbki) jako r. Wzór pozwalający obliczyć liczbę takich permutacji wygląda następująco:

$$ₙPᵣ = \frac{n!}{\left(n-r\right)!}$$

Powyższa formuła jest niezastąpiona przy obliczaniu permutacji bez powtórzeń, gdy musimy uporządkować podzbiór o wielkości r, pobrany z całkowitego zbioru n.

Jeśli natomiast chcielibyśmy ułożyć w określonym porządku wszystkie elementy danego zbioru (czyli gdy n = r), nasz wzór redukuje się do postaci:

$$ₙPᵣ=n!$$

Przykład

Wcześniej sprawdzaliśmy liczbę możliwych układów dla wszystkich ośmiu biegaczy w biegu na 100 metrów. Spójrzmy na ten wyścig pod nieco innym kątem. Na mecie na zawodników czekają trzy medale: złoty za pierwsze miejsce, srebrny za drugie oraz brązowy za trzecie. Na ile sposobów możemy wyłonić trójkę medalistów spośród wszystkich 8 uczestników wyścigu?

Zgodnie z regułą mnożenia, złoty medal może zdobyć dowolny z 8 biegaczy. Gdy pierwsze miejsce zostanie obsadzone, o srebro rywalizuje pozostałych 7 zawodników. Gdy znamy już zdobywcę srebra, w walce o brązowy medal bierze udział 6 biegaczy. Całkowita liczba możliwych wariantów podium dla 8 zawodników wynosi zatem: 8 × 7 × 6 = 336.

Zastosujmy odpowiedni wzór:

$$ₙPᵣ = \frac{n!}{\left(n-r\right)!}$$

Po podstawieniu danych otrzymujemy:

$$₈P₃=\frac{8!}{\left(8-3\right)!}=\frac{8!}{5!}=\frac{8×7×6×5×4×...×1}{5×4×...×1}=8×7×6=336$$

Używając kalkulatora permutacji, wpisz 8 w polu n (obiekty) oraz 3 w polu r (próbka). Po kliknięciu „Oblicz” natychmiast uzyskasz wynik 336.

Permutacje i Kombinacje: Różnica

Inną niezwykle istotną techniką obliczeniową są kombinacje. Kombinacje pozwalają ustalić na ile sposobów możemy wybrać podgrupę elementów r ze znacznie większego zbioru n. Liczbę kombinacji r obiektów ze zbioru n obiektów oznacza się po prostu jako ₙCᵣ.

W definicji permutacji wielokrotnie podkreślaliśmy znaczenie ułożenia obiektów. I to jest właśnie główna różnica między permutacjami a kombinacjami – w kombinacjach kolejność elementów jest całkowicie bez znaczenia.

Powróćmy do przykładu z literami XYZ. Ustaliliśmy, że dwuliterowe permutacje z tego zbioru prezentują się następująco: XY, XZ, YZ, YX, ZX i ZY, co daje nam sześć układów.

Tymczasem dwuliterowe kombinacje liter XYZ to tylko: XY, XZ oraz YZ. Są to więc raptem trzy kombinacje. Dzieje się tak dlatego, że dla kombinacji pary XY oraz YX stanowią dokładnie ten sam wybór elementów; analogicznie traktujemy XZ i ZX, a także YZ i ZY. Z tego powodu kolejność układu jest w pełni ignorowana w procesie obliczania kombinacji.

Wzór na obliczenie liczby kombinacji r obiektów ze zbioru n obiektów wygląda tak:

$$ₙСᵣ=\frac{n!}{r!\left(n-r\right)!}$$

Przykład Obliczania Kombinacji

W ostatnim przykładzie z biegaczami obliczyliśmy liczbę sposobów obsadzenia pierwszego, drugiego i trzeciego miejsca spośród grupy 8 biegaczy. Wyobraźmy sobie teraz, że zależy nam wyłącznie na tym, aby dowiedzieć się, na ile sposobów można wybrać 3 medalistów, bez zwracania uwagi na to, jak podzielą się medalami. Nie ma znaczenia, czy dany zawodnik zdobędzie złoto, srebro czy brąz – liczy się tylko sam fakt stania na podium.

W takim scenariuszu musimy użyć kombinacji, ponieważ ranga zdobytego medalu (kolejność) przestaje mieć znaczenie. Do wykonania obliczeń skorzystamy ze wzoru na kombinacje:

$$ₙСᵣ = \frac{n!}{r!(n-r)!}$$

Liczbę sposobów wyłonienia trójki medalistów z ośmioosobowej grupy opisuje równanie:

$$₈C₃=\frac{8!}{3! × \left(8-3\right)!}=\frac{8!}{3! × 5!}=\frac{8 × 7 × 6}{3 × 2 × 1}=8×7=56$$

Przykłady obliczania permutacji

1. Producent telewizyjnego programu informacyjnego ma do dyspozycji 5 ekspertów, z których chce zaprosić 3 do udziału w panelu dyskusyjnym. Kolejność występowania poszczególnych gości jest kluczowa dla dynamiki audycji. Na ile różnych sposobów producent może zaplanować harmonogram ich prezentacji? Kolejność ma znaczenie, a eksperci nie mogą powtarzać się na liście (ten sam ekspert nie weźmie udziału dwukrotnie w jednym programie). Warunki są więc idealne, aby użyć wzoru na permutacje.

$$ₙPᵣ = \frac{n!}{(n-r)!}$$

$$₅P₃ = \frac{5!}{(5-3)!} = \frac{5!}{2!} = 5 × 4 × 3 = 60$$

Jak widać, producent ma aż 60 unikalnych wariantów do zaplanowania harmonogramu.

2. Krytyk kulinarny wytypował 10 znakomitych restauracji sushi w mieście. Jego zadaniem jest przygotowanie rankingu trzech najlepszych z nich. Lokale muszą być przedstawione w ustalonej hierarchii (miejsce pierwsze, drugie i trzecie), a dana restauracja może pojawić się na liście najwyżej jeden raz. Powyższy scenariusz idealnie wpisuje się w założenia dotyczące permutacji – kolejność jest priorytetem, a powtórzeń brak. Używamy więc standardowego wzoru:

$$ₙPᵣ = \frac{n!}{(n-r)!}$$

$$₁₀P₃ = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 × 9 × 8 = 720$$

3. Kiedy w permutacjach mówimy, że „kolejność jest ważna”, nie zawsze odnosi się to stricte do liczb na skali od 1 do 10. „Kolejność” może określać na przykład fizyczne przypisanie ludzi do konkretnych obiektów lub zadań.

Załóżmy, że kierownik firmy zajmującej się usługami remontowymi ma na dany dzień cztery zlecenia na malowanie: biuro podróży, halę magazynową, butik odzieżowy i sypialnię w domu prywatnym. Firma zatrudnia sześciu malarzy, z których każdy może być przydzielony tylko do jednego zlecenia dziennie. Pozostała dwójka malarzy otrzymuje wolne.

W tym przypadku nasze cztery zlecenia działają w sposób analogiczny do pozycjonowania (są to „miejsca” 1, 2, 3 i 4).

Kierownik dysponuje:

• 6 malarzami, których może przypisać do biura,
• 5 pozostałymi fachowcami do pomalowania hali,
• 4 kandydatami do pracy w butiku,
• 3 malarzami, których można wysłać do domu prywatnego.

Rozwiązanie intuicyjne podpowiada, że liczbę wariantów opisuje równanie: 6 × 5 × 4 × 3 = 360.

Biorąc pod uwagę fakt, że to, kogo przypiszemy do którego zlecenia, ma dla nas olbrzymie znaczenie (to nasza „kolejność”), a powtórzenia są niemożliwe (jeden malarz ma tylko jedno zlecenie), ponownie bez wahania wykorzystujemy formułę permutacji:

$$ₙPᵣ = \frac{n!}{(n-r)!}$$

$$\frac{6!}{(6-4)!} = \frac{6!}{2!} = 6 × 5 × 4 × 3 = 360$$

Okazuje się, że w powyższych warunkach menedżer firmy ma dokładnie 360 odrębnych sposobów na przydzielenie pracowników do dostępnych zleceń.