Permutacje i kombinacje

Liczenie Ustawień i Wyborów z Grupy

Permutacja (nPr) liczy, na ile sposobów można ułożyć r elementów spośród n, gdy kolejność ma znaczenie, a kombinacja (nCr) liczy, na ile sposobów można wybrać r elementów spośród n, gdy kolejność nie ma znaczenia. Podaj całkowitą liczbę elementów (n) oraz ile wybierasz (r), a ten kalkulator znajdzie obie powiązane odpowiedzi naraz.

Wzory

• Permutacje: $P(\vA{n}, \vB{r}) = \frac{\vA{n}!}{(\vA{n} - \vB{r})!}$ — równoważnie, iloczyn $\vB{r}$ malejących liczb zaczynających się od $\vA{n}$: $\vA{n} \times (\vA{n}-1) \times \cdots \times (\vA{n}-\vB{r}+1)$.
• Kombinacje: $C(\vA{n}, \vB{r}) = \frac{P(\vA{n}, \vB{r})}{\vB{r}!}$ — ta sama liczba permutacji, podzielona przez $\vB{r}!$ sposobów, na jakie te same $\vB{r}$ elementów mogłyby same zostać przestawione (ponieważ kolejność nie ma znaczenia dla kombinacji).

Przykład obliczeniowy

Wybieranie 3 elementów z grupy 10, gdy kolejność ma znaczenie (permutacje):

$$P(10,3) = 10 \times 9 \times 8 = 720$$

Ten sam wybór, gdy kolejność NIE ma znaczenia (kombinacje):

$$C(10,3) = 720 \div 3! = 720 \div 6 = 120$$

Sprawdzenie w praktyce

Szanse na trafienie wszystkich 6 liczb w losowaniu loterii 6 z 49 wynoszą 1 do C(49,6) — dokładnie 13 983 816 — ponieważ kolejność losowania liczb nie zmienia tego, czy wygrałeś/wygrałaś.

Kluczowe czynniki do rozważenia

• To, czy kolejność ma znaczenie, to jedyne pytanie, które decyduje, który wzór ma zastosowanie. Ustawianie zdobywców medali na podium (liczy się 1., 2., 3. miejsce) to problem permutacji, podczas gdy wybór, którzy 3 ludzie utworzą komisję (bez rankingu) to problem kombinacji — poprawne rozpoznanie tej różnicy to najczęstsze źródło błędu przy stosowaniu tych wzorów.
• Kombinacje zawsze dają równą lub mniejszą liczbę niż permutacje dla tego samego n i r. Ponieważ kombinacja grupuje każde możliwe uporządkowanie tych samych r elementów w jedną liczbę, C(n,r) to zawsze P(n,r) podzielone przez r! — te dwie wartości pokrywają się dokładnie tylko wtedy, gdy r wynosi 0 lub 1, ponieważ istnieje tylko jeden sposób ułożenia 0 lub 1 elementów niezależnie od kolejności.
• Zarówno liczba permutacji, jak i kombinacji rośnie niezwykle szybko wraz ze wzrostem n i r. Ten wybuchowy wzrost (nazywany eksplozją kombinatoryczną) jest dokładnie powodem, dla którego szanse loteryjne stają się astronomicznie małe przy nawet niewielkim wzroście liczby liczb, z których się losuje — przejście z loterii 6 z 49 do loterii 6 z 59, na przykład, znacząco pogarsza szanse, mimo że pula rośnie tylko o 10 liczb.
• Te wzory zakładają, że każdy element jest odrębny i żaden nie może zostać wybrany więcej niż raz. Scenariusz dopuszczający powtórzone wybory (jak 4-cyfrowy PIN, w którym cyfry mogą się powtarzać) wykorzystuje zupełnie inny wzór liczenia — zawsze potwierdź, czy powtórzenie jest dozwolone, zanim zastosujesz standardowe wzory nPr/nCr tutaj.

Częste Błędy

• Używanie liczby permutacji, gdy kolejność tak naprawdę nie ma znaczenia, lub odwrotnie. To najczęstszy błąd — zawsze najpierw zapytaj, czy zamiana miejscami dwóch wybranych elementów liczyłaby się jako inny wynik, zanim wybierzesz wzór, zamiast zgadywać na podstawie sformułowania problemu.
• Zapominanie, że kombinacje nigdy nie są większe niż permutacje dla tych samych n i r. Jeśli liczba kombinacji wychodzi większa niż odpowiadająca jej liczba permutacji dla tych samych danych wejściowych, coś zostało wprowadzone błędnie — kombinacje dzielą liczbę permutacji w dół, nigdy jej nie zawyżają.
• Stosowanie tych wzorów do sytuacji dopuszczającej powtórzone wybory. Oba wzory zakładają, że każdy element można wybrać co najwyżej raz — problem dopuszczający powtórzenia (jak generowanie 4-cyfrowego PIN-u) wymaga zupełnie innego podejścia do liczenia, a nie nPr czy nCr.

Warto Wiedzieć

• Chcesz faktycznie obliczyć szanse na konkretny wynik, a nie tylko policzyć możliwości? Kalkulator prawdopodobieństwa zamienia liczbę kombinacji lub permutacji na rzeczywiste prawdopodobieństwo.
• Pracujesz z całym zbiorem danych zamiast po prostu liczyć ustawienia? Kalkulator statystyczny oblicza średnią, odchylenie standardowe i inne statystyki podsumowujące z listy liczb.
• Musisz uprościć proporcję lub znaleźć wspólny mianownik jako część powiązanego problemu kombinatorycznego? Kalkulator NWD i NWW znajduje największy wspólny dzielnik i najmniejszą wspólną wielokrotność zbioru liczb.