Wyjaśnione: Permutacje vs. Kombinacje

Tak, mówię o tych mistycznych przyciskach na twoim kalkulatorze (nCr i nPr), które łaskawie uderzasz i wypluwasz poprawną odpowiedź. Magia.

Te dwie koncepcje są dość proste, więc nie powinno to zająć zbyt wiele czasu, aby wyjaśnić. Zamierzam wyjaśnić różnice, kiedy ich używać i co dokładnie oblicza kalkulator, kiedy je wprowadzasz (równanie).

Najlepszym sposobem na zilustrowanie ich zastosowania są dwa przykłady:

Przykład 1: 10 sportowców bierze udział w wyścigu, w którym zdobywca pierwszego miejsca otrzyma złoty medal, drugiego miejsca srebrny medal, a trzeciego miejsca brązowy medal. Jeśli zdobędą medal, staną na podium. Reszta nie otrzymuje nic… nawet trofeum uczestnictwa… bo to jest Ameryka… i jeśli nie jesteś pierwszy to jesteś ostatni.

Pytanie 1: ile jest możliwości zajęcia miejsca na podium?

Pytanie 2: ile jest możliwości, kto zdobędzie medal?

Kiedy używać nPr, a kiedy nCr?

Kiedy ich używać:

Te dwa pytania mogą wydawać się podobne, ale istnieje zasadnicza różnica, która dyktuje, którego równania użyć.

Pytanie 1 (podium) czynniki w istotności kolejności:

Jeśli Bob, Lacy i Sarah są na podium, Bob przychodzący na pierwszym miejscu nie jest taki sam jak Bob przychodzący na drugim. Jest to inny wynik. Kolejność jest istotna, więc użyjesz nPr.

nPr (permutacje) jest używany, gdy kolejność ma znaczenie.

Pytanie 2 nie bierze pod uwagę kolejności na podium, po prostu pyta, kto wygrywa medal. Pytanie nie rozgranicza pomiędzy złotem, srebrem i brązem, wszystkie są medalami i tylko to ma znaczenie. Kiedy kolejność nie ma znaczenia, używasz nCr.

nCr (kombinacje) jest używany, gdy kolejność nie ma znaczenia.

Co one właściwie robią:

Teraz, gdy już wiesz, kiedy użyć którego z nich, przejdźmy do tego, co one właściwie robią.

nPr
Jak wspomniano, nPr znajduje wszystkie permutacje, które istnieją w danym zestawie dla danego podzbioru. W naszym konkretnym przykładzie, będzie patrzeć na to, jak wiele różnych wyników może wynikać z wyścigu, który spowodowałby permutację podium (inna kolejność).

W naszym wyścigu:

Okay, więc rozbiliśmy magiczny przycisk trochę bardziej, ale możesz zadawać sobie teraz pytanie…dlaczego to jest równanie, i dlaczego wszystkie liczby krzyczą na mnie!!!! – co oznacza !!! lub inaczej zwany czynnikiem jest po prostu wygodnym sposobem na wyrażenie serii mnożenia.

W szczególności:

Zilustrujmy to wracając do naszego przykładu:

n = 15 (bo jest 15 sportowców)

n! = 15! = 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1

To właśnie oblicza Twój kalkulator po naciśnięciu przycisku !

15! = 1 307 674 368 000

Ta liczba reprezentuje maksymalną liczbę różnych zamówień, które mogą wystąpić na liście. Na naszej liście jest 15 biegaczy, a istnieje 1 307 674 368 000 różnych sposobów ich rozmieszczenia. Pomnożona liczba maleje, ponieważ po umieszczeniu numeru, to miejsce jest teraz zajęte.

Jeśli biegacz 1 zajmuje 15 miejsce, jest tylko 14 innych miejsc do wylądowania dla wszystkich pozostałych biegaczy, jeśli biegacz 2 zajmuje 14 miejsce, jest już tylko 13 miejsc dla wszystkich biegaczy. Jak większość rzeczy, łatwiej to wytłumaczyć poprzez przeskalowanie liczb:

Przykład prostszy (można pominąć, jeśli już rozumiesz):

Powiedzmy, że są cztery dostępne miejsca, i 4 przyjaciół, którzy chcą usiąść. Dla pierwszego miejsca, istnieją cztery potencjalne wyniki (każdy z czterech przyjaciół może go zająć), po tym jak zostało zajęte, drugie miejsce ma tylko trzy różne potencjalne wyniki (każdy z 3 odsuniętych przyjaciół może je zająć), trzecie miejsce ma tylko dwie możliwości, a ostatnie miejsce domyślnie ma tylko jedną opcję – biedny frajer, który jeszcze nie usiadł.

W rezultacie, matematycznie rzecz biorąc, istnieje 4 x 3 x 2 x 1 potencjalnych wyników.

Gdyby wyścig był po prostu pytaniem, na ile różnych sposobów może zmienić się kolejność wyścigu, nie użylibyśmy nPr, użylibyśmy factorial(!)… ale to nie jest… to jest pytanie, ile razy podium może się zmienić, co jest konkretnie patrząc na trzech najlepszych biegaczy, a nie wszystkich z nich. W rezultacie nie używamy czynnikowego. Factorial ma zbyt szeroki zakres.

Ponieważ jest on zbyt szeroki, musimy go ograniczyć. Badamy tylko trzy pierwsze pozycje, a nie pozostałe 12. Innymi słowy, jeśli kolejność pierwszych trzech się zmieni, to jest to uważane za nową permutację, ale jeśli kolejność pierwszych trzech pozostaje taka sama, (nawet jeśli kolejność pozostałych 12 się zmienia), to nie uważamy tego za nową permutację.

Ponieważ 12 pozycji jest nieistotnych, musimy zmniejszyć ich znaczenie w równaniu.

Dlatego właśnie otrzymujemy

Najprostszym sposobem na usunięcie istotności pozostałych 12 pozycji jest podzielenie pełnej liczby możliwości(!) przez możliwą liczbę nieistotnych pozycji. Jak wcześniej zaznaczono, istnieje 12 pozycji, które są nieistotne dla naszego podium.

Więc 15! podzielone przez (15 -3)!

To równa się wypisaniu:

co równa się 15 x 14 x 13, ponieważ wszystkie pozostałe liczby się anulują.

15 x 14 x 13 również = 2730

Teraz spójrzmy na nCr:

Whew, to zajęło dużo czasu, aby przejść przez permutacje, ta runda powinna być szybsza, ponieważ już mówiłem o czynnikach teraz.

Jak wspomniano, nCr, jest znalezienie wszystkich kombinacji, które istnieją w danym zestawie dla danego podzbioru, gdy kolejność nie ma znaczenia. W naszym przykładzie, to patrzy na liczbę różnych kombinacji, które mogą wystąpić dla wygrania medalu (tj. zajęcie miejsca w pierwszej trójce)

Teraz zaraz po zakończeniu, zauważysz, że jest mniej kombinacji niż permutacji (455 < 2730). Ma to sens, ponieważ kombinacje oznaczają ABC i ACB jako to samo, podczas gdy permutacje rozróżniają te dwa elementy. Zbadajmy, co robi nasz kalkulator, gdy naciskamy przycisk.

Teraz pierwszą rzeczą, którą powinieneś zauważyć jest to, że równanie jest całkiem podobne do równania permutacji, z tą różnicą, że do mianownika dodano więcej (jest to k!(n-r)!, a nie tylko (n-r)!

Zgodnie z poprzednim stwierdzeniem, ma to sens, ponieważ dodanie większej ilości do mianownika spowoduje mniejszy wynik (np. 10/2) < 10/5), a ustaliliśmy, że kombinacje będą mniejsze niż permutacje.

Jeśli zwróciłeś uwagę/moje pisanie ma jakikolwiek sens, powinniśmy już wiedzieć, dlaczego dodajesz (n-r)! do równania. Jeśli nie, to ctrl/command +f „zbyt szeroki zakres” i przeczytaj ten fragment jeszcze raz.

Dodajemy r! do mianownika, ponieważ istnieje r! sposobów na to, aby zdobywcy medali pozostali tacy sami, podczas gdy ich kolejność się zmienia.

Dla każdego zestawu trzech zdobywców medali, mogą oni zostać przetasowani 3! razy, aby stworzyć nową permutację (3! = 6 razy)… ale nie obchodzi nas ta permutacja. Te 6 różnych permutacji to tak naprawdę tylko jedna kombinacja sportowców, więc chcemy ją wyciągnąć z naszej odpowiedzi. Najłatwiejszym sposobem na to jest dodanie jej do mianownika, tak aby została wyciągnięta z licznika.

To nie przypadek, że 455 x 3! = 2730.

Anyp>To wszystko, co mam na dzisiaj. Mam nadzieję, że to ma sens.

Ciao,