Permutacja vs Kombinacja: Jaka jest różnica między formułą permutacji a formułą kombinacji?

Permutacja vs Kombinacja: Jaka jest różnica między formułą permutacji a formułą kombinacji?

Oto krótka wersja.

Za przykład weźmy bicie dzwonów w kościele.

Permutacja to uporządkowanie dzwonów. Zastanawiasz się, w jakiej kolejności najlepiej je dzwonić.

Kombinacja to wybór dzwonów. Wybierasz dzwony, które mają dzwonić. Gdybyś miał zbyt wiele dzwonów, najpierw byś je wybrał, a potem zastanawiał się nad ich uporządkowaniem.

To daje początek znanej tożsamości: (n P r) = (n C r) * r!

Sposób na uporządkowanie r przedmiotów z n polega na tym, że najpierw wybieramy r przedmiotów z n, a następnie porządkujemy r przedmiotów (r! )

A to oznacza (n P r) = n! / (n-r)! i (n C r) = n! / ( (n-r)! * r! )

Ale czy chcesz wiedzieć, jak to zapamiętać na zawsze?

Jestem wielkim fanem myślenia według pierwszych zasad. Aby zrozumieć problem, należy dotrzeć do jego sedna i stamtąd rozumować w górę.

Nie robienie tego jest zwykle źródłem zamieszania: jeśli nie rozumiem, jak rzeczy działają, nie wiem, gdzie zawiesić koncepcje. Moje ramy umysłowe nie są kompletne, więc postanawiam je po prostu zapamiętać.

Jak możesz sobie wyobrazić, nie jest to idealne rozwiązanie. Więc, od czasu do czasu, oddaję się ćwiczeniu wyprowadzania rzeczy ze źródła, i budowania intuicji jak rzeczy działają.

Tym razem dookoła, budujemy intuicję dla permutacji i kombinacji.

Na przykład, czy wiesz dlaczego wzór na kombinację to (n C r)? Skąd to się wzięło? I dlaczego są tu używane współczynniki?

Zacznijmy od źródła. Czynniki, permutacje i kombinacje zrodziły się z matematyków bawiących się razem, podobnie jak Steve Jobs i Steve Wozniak założyli Apple, bawiąc się razem w garażu.

Tak jak Apple stało się pełnoprawną, dochodową firmą, prosty czynnik, !, stał się atomem całej dziedziny matematyki: kombinatoryki.

Zapomnijmy o wszystkim, zacznijmy myśleć od dołu do góry.

Pierwszy znany interesujący przypadek użycia pochodził z kościołów w XVII wieku.

Czy zastanawiałeś się, jak dzwony biją w kościołach? Jest tam maszyna, która „dzwoni” je w kolejności. Przerzuciliśmy się na maszyny, ponieważ dzwony są zbyt duże. Ponadto, jest mnóstwo dzwonów.

Jak ludzie wymyślili najlepszą sekwencję do dzwonienia nimi? A jeśli chcieli coś zmienić? Jak mogli znaleźć najlepszy dźwięk? Każda dzwonnica miała do 16 dzwonów!

Nie można było zmienić szybkości dzwonienia – maszyny biły tylko jeden dzwon na sekundę. Jedyne, co mogłeś zrobić, to zmienić kolejność dzwonów. Więc to wyzwanie polegało na ustaleniu najlepszej kolejności.

Czy po drodze moglibyśmy również poznać wszystkie możliwe kolejności? Chcemy poznać wszystkie możliwe zamówienia, aby dowiedzieć się, czy warto ich wszystkich spróbować.

Dzwonnik Fabian Stedman podjął to wyzwanie.

Zaczął od 2 dzwonów. W jakiej kolejności mógłby dzwonić tymi dzwonami?

1 i 2.
lub
2 i 1.

To miało sens. Nie było innego sposobu.

A może z 3 dzwonkami?

1, 2, i 3.
1, 3, i 2.

Potem zaczynając od drugiego dzwonka,

2, 1, i 3.
2, 3, i 1.

Potem zaczynając od trzeciego dzwonka,

3, 1, i 2.
3, 2, i 1.

Łącznie 6.

Potem zdał sobie sprawę, że jest to bardzo podobne do dwóch dzwonów!

Jeśli naprawił pierwszy dzwon, to liczba sposobów na uporządkowanie pozostałych dwóch dzwonów zawsze wynosiła dwa.

Na ile sposobów mógł naprawić pierwszy dzwon? Każdy z 3 dzwonów mógł być tym jedynym!

Dobrze, kontynuował. Doszedł do 5 dzwonów.

W tym momencie zdał sobie sprawę, że robienie rzeczy ręcznie jest nieporęczne. Masz tylko tyle czasu w ciągu dnia, musisz dzwonić dzwonami, nie możesz utknąć w rysowaniu wszystkich możliwych dzwonów. Czy istniał sposób, żeby to szybko rozgryźć?

Powrócił do swojego spostrzeżenia.

Jeśli miał 5 dzwonów, i naprawił pierwszy dzwon, wszystko co musiał zrobić, to dowiedzieć się, jak zamówić 4 dzwony.

Dlaczego 4 dzwony? Cóż, jeśli miał 4 dzwony i naprawił pierwszy dzwon, wszystko, co musiał zrobić, to dowiedzieć się, jak zamówić 3 dzwony.

A on wiedział, jak to zrobić!

Więc, zamówienie 5 dzwonów = 5 * zamówienie 4 dzwonów.

Zamówienie 4 dzwonów = 4 * zamówienie 3 dzwonów

Zamówienie 3 dzwonów = 3 * zamówienie 2 dzwonów.

… Widzisz wzór, prawda?

Fun Fact: To jest klucz do techniki programowania zwanej rekurencją.

On też to zrobił. Chociaż zajęło mu to znacznie więcej czasu, ponieważ nikt w jego pobliżu już tego nie odkrył.

W ten sposób doszedł do wniosku, że uporządkowanie 5 dzwonów = 5 * 4 * 3 * 2 * 1.

Ta formuła uporządkowania, w 1808 roku, stała się znana jako czynnikowa.

Myślimy o notacji czynnikowej jako o podstawie, ale pomysł istniał na długo przed tym, zanim miał nazwę. Dopiero gdy francuski matematyk Christian Kramp zauważył, że jest on używany w kilku miejscach, nazwał go faktorią.

Takie uporządkowanie dzwonków nazywa się permutacją.

Permutacja to uporządkowanie elementów.

Przy uczeniu się czegoś, myślę, że pomaga spojrzeć na rzeczy z każdej strony, aby ugruntować zrozumienie.

A gdybyśmy spróbowali wyprowadzić powyższy wzór bezpośrednio, nie próbując zredukować problemu do mniejszej liczby dzwonków?
Mamy 5 miejsc, prawda?

Na ile sposobów możemy wybrać pierwszy dzwonek? 5, bo tyle mamy dzwonków.

Drugi dzwonek? Cóż, zużyliśmy jeden dzwonek, gdy umieściliśmy go na pierwszej pozycji, więc zostały nam 4 dzwony.

Trzeci dzwonek? Cóż, wybraliśmy już dwa pierwsze, więc zostały nam tylko 3 dzwony do wyboru.

Czwarty dzwonek? Zostały tylko 2 dzwony, więc 2 opcje.
Piąty dzwonek? Pozostał tylko 1, więc 1 opcja.

I oto mamy, całkowita liczba zamówień wynosi 5 * 4 * 3 * 2 * 1

Tym samym mamy nasz pierwszy wzór ogólny.

Liczba sposobów zamawiania N przedmiotów wynosi N!

Teraz stajemy przed innym problemem. Król kazał zrobić nowe dzwony do każdego kościoła. Niektóre są ładne, inne w porządku, a jeszcze inne sprawią, że ogłuchniesz. Ale każdy z nich jest wyjątkowy. Każdy wydaje swój własny dźwięk. Głuchy dzwon otoczony ładnymi dzwonami może brzmieć majestatycznie.

Ale nasza dzwonnica nadal mieści 5 dzwonów, więc musimy wymyślić najlepsze zamówienie spośród 8 dzwonów, które wykonali wykwalifikowani dzwonnicy.

Korzystając z powyższej logiki, możemy przystąpić do działania.

Dla pierwszego dzwonu możemy wybrać dowolny z 8 dzwonów.

Dla drugiego dzwonu możemy wybrać dowolny z pozostałych 7 dzwonów… i tak dalej.

W końcu otrzymujemy 8 * 7 * 6 * 5 * 4 możliwych uporządkowań 8 dzwonów w 5 przestrzeniach.

Jeśli znasz wersję wzoru na (n P r), która wynosi n! / (n-r)!, nie martw się, to też wkrótce wyprowadzimy!

Jednym ze złych sposobów na jego wyprowadzenie jest pomnożenie licznika i mianownika przez 3! w naszym powyższym przykładzie –

otrzymamy 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1 = 8! / 3!.

Ale to nie pomoże nam zrozumieć, dlaczego ta formuła działa. Zanim do tego dojdziemy, przyjrzyjmy się wybieraniu rzeczy, czyli Kombinacji.

Kombinacja

Teraz, gdy wiemy, jak porządkować rzeczy, możemy dowiedzieć się, jak je wybierać!

Rozważmy ten sam problem. Jest tam dzwonnica z 5 dzwonami, a ty masz 8 dzwonów. Jednak w tej chwili nie chcesz ustalać kolejności dzwonów (pamiętaj, że to właśnie jest permutacja).

Zamiast tego chcesz wybrać 5 najlepszych dzwonów i pozwolić komuś innemu, kto ma lepszy gust muzyczny, ustalić kolejność. W efekcie rozkładamy problem na części: Najpierw zastanawiamy się, które dzwonki wybrać. Następnie zastanawiamy się, jak uporządkować wybrane dzwony.

Jak wybrać dzwony? To jest właśnie „kombinacja” z permutacji i kombinacji.

Kombinacja jest wyborem. Jesteś selektywny. Wybierasz 5 dzwonów z 8, które wykonali Twoi rzemieślnicy.

Ponieważ wiemy, jak zamawiać dzwony, wykorzystamy tę informację, aby dowiedzieć się, jak wybrać dzwony. Wydaje się niemożliwe? Poczekaj, aż zobaczysz piękną matematykę z tym związaną.

Wyobraźmy sobie, że wszystkie dzwonki są w linii.

Przed znalezieniem wszystkich sposobów wyboru dzwonków, skupmy się na jednym sposobie wyboru dzwonków.

Jednym ze sposobów jest wybranie losowo 5 dowolnych. Nie pomaga nam to zbytnio w rozwiązaniu problemu, więc spróbujmy innego sposobu.

Układamy dzwonki w szeregu i wybieramy 5 pierwszych. Jest to jeden ze sposobów wyboru dzwonków.

Zauważmy, że nawet jeśli zmienimy położenie pierwszych 5 dzwonków, wybór się nie zmienia. To wciąż ten sam jeden sposób na wybór 5 wyjątkowych dzwonów.

Tak samo jest z ostatnimi trzema dzwonami.

Teraz piękna sztuczka matematyczna – dla tego jednego sposobu na wybór 5 dzwonów, jakie są wszystkie uporządkowania 8 dzwonów, w których wybieramy dokładnie te 5 dzwonów? Z powyższego obrazka wynika, że są to wszystkie uporządkowania 5 dzwonów (5!) i wszystkie uporządkowania pozostałych trzech dzwonów (3!).

Tak więc dla każdego pojedynczego sposobu wyboru 5 dzwonów mamy (5! * 3!) uporządkowań 8 dzwonów.

Jakie są całkowite możliwe uporządkowania 8 dzwonów? 8!.

Pamiętajmy, że dla każdego wyboru pierwszych 5 dzwonków mamy (5! * 3!) uporządkowań 8 dzwonków, które dają ten sam wybór.

Wtedy, jeśli pomnożymy liczbę sposobów wyboru pierwszych 5 dzwonków przez wszystkie możliwe uporządkowania jednego wyboru, powinniśmy otrzymać całkowitą liczbę uporządkowań.

Ways to choose 5 bells * orderings of one choice = Total orderings

Więc,

Ways to choose 5 bells = the total possible orderings / total orderings of one choice.

W matematyce staje się to:

(8 C 5) = 8! / ( 5! * 3!)

No i oto znaleźliśmy intuicyjne wyjaśnienie, jak wybrać 5 rzeczy z 8.

Teraz możemy to uogólnić. Jeśli mamy N rzeczy, i chcemy wybrać R z nich, to znaczy, że rysujemy linię na R.

Co oznacza, że pozostałych przedmiotów będzie N-R. Zatem dla jednego wyboru R przedmiotów mamy R! * (N-R)! uporządkowań, które dają te same R przedmioty.

Dla wszystkich sposobów wyboru R przedmiotów mamy N! / (R! * (N-R)!) możliwości.

Liczba sposobów na wybranie r elementów z n wynosi (n C r) = n! / (r! * (n-r)!)

W potocznym rozumieniu, (n C r) wymawia się również n choose r, co pomaga ugruntować myśl, że kombinacje służą do wybierania elementów.

Permutacja – rewizja

Z kombinacją zrobioną i odkurzoną, wróćmy do części 2 naszego zadania. Nasz drogi przyjaciel wybrał najlepsze 5 dzwonów poprzez określenie wszystkich możliwych kombinacji 5 dzwonów.

Naszym zadaniem jest teraz znalezienie idealnej melodii poprzez określenie liczby zamówień.

Ale to jest łatwy kawałek. Wiemy już, jak zamówić 5 elementów. To 5!, i gotowe.

Więc, aby permutować (zamówić) 5 elementów z 8, najpierw wybieramy 5 elementów, a następnie zamawiamy 5 elementów.

Innymi słowy,

(8 P 5) = (8 C 5) * 5!

I jeśli rozszerzymy formułę, (8 P 5) = (8! / ( 5! * 3!)) * 5!

(8 P 5) = 8! / 3!.

I, zatoczyliśmy pełne koło do naszej oryginalnej formuły, wyprowadzonej prawidłowo.

Liczba sposobów na uporządkowanie r elementów z n wynosi (n P r) = n! / (n-r)!

Różnica między permutacją a kombinacją

Mam nadzieję, że dzięki temu różnica między permutacjami a kombinacjami jest krystalicznie czysta.

Permutacje to uporządkowania, natomiast kombinacje to wybory.

Aby uporządkować N elementów, znaleźliśmy dwa intuicyjne sposoby na rozgryzienie odpowiedzi. Oba prowadzą do odpowiedzi, N!.

Aby permutować 5 z 8 elementów, musisz najpierw wybrać 5 elementów, a następnie je uporządkować. Wybierasz używając (8 C 5), a następnie porządkujesz 5 używając 5!.

A intuicja wyboru R z N to rozgryzienie wszystkich porządków (N!) i podzielenie przez porządki, w których pierwszy R i ostatni N-R pozostają takie same (R! i (N-R)!).

I to już wszystko, jeśli chodzi o permutacje i kombinacje.

Każda zaawansowana permutacja i kombinacja używa tego jako podstawy. Kombinacja z wymianą? Ten sam pomysł. Permutacja z identycznymi elementami? Ten sam pomysł, tylko liczba zamówień się zmienia, ponieważ niektóre elementy są identyczne.

Jeśli jesteś zainteresowany, możemy przejść do złożonych przypadków w innym przykładzie. Daj mi znać na Twitterze.

Check out more posts on my blog, and join the weekly mailing list.

End notes

1. This is how I imagine he figured things out. Nie traktuj tego jako lekcji historii.
2. Hindusi mieli, w XII wieku, 400 lat przed nim.