Permutacija vs kombinacija: Koja je razlika između formule permutacije i kombinacije formule?

Evo kratke verzije.

Uzmimo za primjer zvonjavu u crkvi.

Permutacija je poredak zvona. Otkrivate koji je najbolji red za njihovo pozivanje.

Kombinacija je izbor zvona. Birate zvona koja će zvoniti. Ako imate previše zvona, prvo biste ih odabrali, a zatim razmislite o naručivanju.

Iz toga nastaje poznati identitet: (n P r) = (n C r) * r!

Način naručivanja rpredmeta nje prvo odabir rpredmeta n, a zatim naručivanje rpredmeta ( r!)

A, to znači (n P r) = n! / (n-r)!i(n C r) = n! / ( (n-r)! * r! )

Ali želite li znati kako to zauvijek pamtiti?

Veliki sam ljubitelj razmišljanja o prvim principima. Da biste razumjeli problem, uđite u njegovu srž i razložite ga od tamo.

Nečinjenje je obično izvor zabune: ako ne razumijem kako stvari funkcioniraju, ne znam kamo objesiti koncepte. Moj mentalni okvir nije potpun, pa se odlučim samo sjetiti.

Kao što možete zamisliti, ovo nije idealno. Zato se s vremena na vrijeme prepustim vježbi izvođenja stvari iz izvora i izgrađujem intuiciju kako stvari funkcioniraju.

Ovaj put gradimo intuiciju za permutacije i kombinacije.

Na primjer, znate li zašto je formula za kombinaciju (n C r)? Odakle ovo? I zašto se ovdje koriste činjenice?

Krenimo od izvora. Činjenice, permutacije i kombinacije rođeni su iz matematičara koji su se zajedno igrali, slično kao što su Steve Jobs i Steve Wozniak osnovali Apple, igrajući zajedno u njihovoj garaži.

Baš poput toga kako je Apple postao punopravna profitabilna tvrtka, jednostavni faktor !, postao je atom cijelog područja matematike: kombinatorike.

Zaboravite sve, krenimo razmišljati odozdo prema gore.

Prvi poznati zanimljivi slučaj upotrebe došao je iz Crkava u 17. stoljeću.

Jeste li se pitali kako se zvone u crkvama? Postoji stroj koji ih "zvoni" redom. Prešli smo na strojeve jer su zvona prevelika. Također, tu su i zvona na tone.

Kako su ljudi pronašli najbolji slijed u kojem će ih pozvoniti? Što ako su htjeli zamijeniti stvari? Kako su mogli pronaći najbolji zvuk? Svaki je zvonik imao do 16 zvona!

Nisi mogao promijeniti koliko brzo možeš zazvoniti - strojevi su zvonili samo jedno zvono svake sekunde. Jedino što si mogao učiniti bilo je promijeniti redoslijed zvona. Dakle, ovaj izazov se odnosio na pronalaženje najboljeg reda.

Možemo li usput saznati i sve moguće narudžbe? Želimo znati sve moguće narudžbe kako bismo shvatili vrijedi li ih sve isprobati.

Zvonar, Fabian Stedman prihvatio se ovog izazova.

Počeo je s 2 zvona. U kojim je različitim redoslijedima mogao pozvoniti na ova zvona? [1]

1 i 2.

ili

2 i 1.

Ovo je imalo smisla. Nije bilo drugog načina.

Može sa 3 zvona?

1, 2 i 3.

1, 3 i 2.

Zatim počevši od drugog zvona,

2, 1 i 3.

2, 3 i 1.

Zatim počevši od trećeg zvona,

3, 1 i 2.

3, 2 i 1.

Ukupno, 6.

Tada je shvatio da je ovo vrlo slično dvama zvonima!

Ako je popravio prvo zvono, tada je uvijek bilo dva načina za naručivanje preostala dva zvona .

Na koliko je načina mogao popraviti prvo zvono? Bilo koje od 3 zvona može biti jedno!

U redu, nastavio je. Tada je stigao do 5 zvona.

Tada je shvatio da je ručno raditi nezgrapno. Imate samo toliko vremena u danu, morate zvoniti, ne možete zaglaviti u izvlačenju svih mogućih zvona. Je li postojao način da se to brzo shvati?

Vratio se svom uvidu.

Ako je imao 5 zvona, a popravio je prvo zvono, trebalo je samo smisliti kako naručiti 4 zvona.

Za 4 zvona? Pa, ako je imao 4 zvona i popravio prvo zvono, sve što je trebao učiniti bilo je smisliti kako naručiti 3 zvona.

I znao je to učiniti!

Dakle, naručivanje 5 zvona = 5 * naručivanje 4 zvona.

Naručivanje 4 zvona = 4 * naručivanje 3 zvona

Naručivanje 3 zvona = 3 * naručivanje 2 zvona.

.. Vidiš obrazac, zar ne?

Zabavna činjenica: Ovo je ključ za tehniku ​​programiranja koja se naziva rekurzija.

I on je to učinio. Iako mu je trebalo puno više, jer to nitko u njegovoj blizini još nije otkrio. [2]

Dakle, shvatio je da je naručivanje 5 zvona = 5 * 4 * 3 * 2 * 1.

Ova formula za naručivanje 1808. godine postala je poznata kao faktor.

Faktorijalnu notaciju smatramo bazom, ali ideja je postojala mnogo prije nego što je dobila ime. Tek kad je francuski matematičar Christian Kramp primijetio da se koristi na nekoliko mjesta, nazvao ga je faktorijelom.

Ovo slaganje zvona naziva se permutacija.

Permutacija je poredak stavki.

Kad nešto učim, mislim da pomaže gledati na stvari iz svakog drugog kuta, da učvrsti razumijevanje.

Što ako bismo gornju formulu pokušali izvesti izravno, ne pokušavajući svesti problem na manji broj zvona?

Imamo 5 prostora, zar ne?

Na koliko načina možemo odabrati prvo zvono? 5, jer to je broj zvona koje imamo.

Drugo zvono? Pa, iskoristili smo jedno zvono kad smo ga postavili na prvo mjesto, tako da su nam ostala 4 zvona.

Treće zvono? Pa, izabrali smo prva dva, tako da preostaju samo 3 zvona.

Četvrto zvono? Preostala su samo 2 zvona, dakle 2 mogućnosti.

Peto zvono? Preostala je samo 1, dakle 1 opcija.

I tu smo, ukupan broj narudžbi je 5 * 4 * 3 * 2 * 1

Dakle, imamo svoju prvu opću formulu.

Broj načina naručivanja Npredmeta jeN!

Permutacija

Sad smo suočeni s drugim problemom. Kralj je naredio da se za svaku crkvu naprave nova zvona. Neki su simpatični, neki dobro, neki će vas oglušiti. Ali svaki je jedinstven. Svaka stvara svoj zvuk. Zaglušujuće zvono okruženo lijepim zvonima može zvučati veličanstveno.

Ali, naš zvonik još uvijek sadrži 5 zvona, tako da moramo smisliti najbolju narudžbu od 8 zvona koje su napravili vješti izrađivači zvona.

Koristeći gornju logiku, možemo nastaviti.

Za prvo zvono možemo odabrati bilo koje od 8 zvona.

Za drugo zvono možemo odabrati bilo koje od preostalih 7 zvona ... i tako dalje.

Na kraju dobivamo 8 * 7 * 6 * 5 * 4moguće narudžbe 8 zvona u 5 prostora.

Ako ste upoznati s verzijom formule (n P r), koja jest n! / (n-r)!, ne brinite, i to ćemo izvesti dovoljno brzo!

Jedan od loših načina za izvođenje je množenje brojnika i nazivnika s 3! u našem gornjem primjeru -

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

Ali to nam ne pomaže razumjeti zašto ova formula djeluje. Prije nego što stignemo tamo, pogledajmo odabir stvari ili kombinaciju.

Kombinacija

Sad kad znamo kako naručiti stvari, možemo shvatiti kako odabrati stvari!

Razmotrimo isti problem. Tu je zvonik s 5 zvona, a vi imate 8 zvona. Međutim, trenutno ne želite shvatiti redoslijed zvona (sjetite se da je to ono što je permutacija).

Umjesto toga, želite odabrati 5 najboljih zvona, a netko drugi s boljim glazbenim ukusom neka shvati narudžbu. Zapravo problem dijelimo na dijelove: Prvo utvrdimo koja zvona odabrati. Dalje, shvatit ćemo kako naručiti odabrana zvona.

Kako birate zvona? Ovo je "kombinacija" iz permutacija i kombinacija.

Kombinacija je izbor. Birate selektivni. Birate 5 zvona od 8 vaših majstora.

Budući da znamo kako naručiti zvona, upotrijebit ćemo ove podatke kako bismo shvatili kako odabrati zvona. Zvuči nemoguće? Pričekajte dok ne vidite lijepu matematiku.

Zamislimo da su sva zvona u nizu.

Prije pronalaska svih načina odabira zvona, usredotočimo se na jedan način odabira zvona.

Jedan od načina je slučajnim odabirom bilo kojih 5. To nam ne pomaže u rješavanju problema puno, pa pokušajmo na drugi način.

Zvona stavljamo u red i biramo prvih 5. Ovo je jedan od načina za odabir zvona.

Primijetite da se, čak i ako promijenimo položaj prvih 5 zvona, izbor ne mijenja. I dalje su na jedan način odabrali 5 jedinstvenih zvona.

To vrijedi i za zadnja tri zvona.

E sad, prekrasan matematički trik - za ovaj jedan način odabira 5 zvona, koje su sve narudžbe 8 zvona gdje odabiremo točno ovih 5 zvona? Na gornjoj slici prikazani su svi redoslijed 5 zvona ( 5!) i svi redoslijed preostala tri zvona ( 3!).

Dakle, za svaki pojedini način odabira 5 zvona imamo ( 5! * 3!) narudžbe od 8 zvona.

Koji su ukupni mogući redoslijedi 8 zvona? 8!.

Zapamtite, za svaki izbor prvih 5 zvona imamo ( 5! * 3!) narudžbe od 8 zvona koja daju isti izbor.

Zatim, ako pomnožimo broj načina odabira prvih 5 zvona sa svim mogućim narudžbama jednog izbora, trebali bismo dobiti ukupan broj narudžbi.

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

Tako,

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

U matematici to postaje:

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

Evo i pronašli smo intuitivno objašnjenje kako odabrati 5 od 8 stvari.

Sada to možemo generalizirati. Ako imamo N stvari, a želimo odabrati R od njih, to znači da podvlačimo crtu na R.

Što znači da će preostali predmeti biti N-R. Dakle, za jedan izbor Rpredmeta imamo R! * (N-R)!narudžbe koje daju iste Rstavke.

Za sve načine odabira Rpredmeta imamo N! / (R! * (N-R)!)mogućnosti.

Broj načina za odabir rpredmeta nje(n C r) = n! / (r! * (n-r)!)

U razgovornom smislu, (n C r) je također izražen n choose r, što pomaže učvrstiti ideju da su kombinacije za odabir predmeta.

Permutacija - ponovno posjećeno

S gotovom i zaprašenom kombinacijom, vratimo se na 2. dio našeg posla. Naš dragi prijatelj odabrao je najboljih 5 zvona odgonetnuvši sve moguće kombinacije 5 zvona.

Naš je posao sada pronaći savršenu melodiju utvrđivanjem broja narudžbi.

Ali, ovo je lagano. Već znamo kako naručiti 5 predmeta. Gotovo je 5!i završili smo.

Dakle, da bismo permutirali (naručili) 5 stavki od 8, prvo biramo 5 predmeta, a zatim naručimo 5 predmeta.

Drugim riječima,

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

A ako proširimo formulu, (8 P 5) = (8! / ( 5! * 3!)) * 5!

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

I, puni smo krug do izvorne formule, izvedene pravilno.

Broj načina za naručivanje rpredmeta nje:(n P r) = n! / (n-r)!

Razlika između permutacije i kombinacije

Nadam se da će to učiniti razliku između permutacija i kombinacija kristalno jasnom.

Permutacije su redoslijed, dok su kombinacije izbor.

Da bismo naručili N elemenata, pronašli smo dva intuitivna načina da dokučimo odgovor. Obje vode do odgovora, N!.

Da biste permutirali 5 od 8 elemenata, prvo morate odabrati 5 elemenata, a zatim ih naručiti. Vi odaberete upotrebu (8 C 5), a zatim naručite 5 pomoću 5!.

A intuicija za odabir Riz Nfiguring out sve orderings ( N!) i dijeljenjem s orderings gdje je prvi Ri zadnji N-Rostati isti ( R!i (N-R)!).

I to je sve što se tiče permutacija i kombinacija.

Svaka napredna permutacija i kombinacija koristi ovo kao bazu. Kombinacija s zamjenom? Ista ideja. Permutacija s identičnim stavkama? Ista ideja, mijenja se samo broj narudžbi, jer su neke stavke identične.

Ako ste zainteresirani, u sljedeći primjer možemo ući u složene slučajeve. Javite mi na Twitteru.

Provjerite još postova na mom blogu i pridružite se tjednoj popisu e-pošte.

Završne bilješke

  1. Ovako zamišljam da je shvatio stvari. Ne uzimajte to kao lekciju iz povijesti.
  2. Indijanci su u 12. stoljeću imali 400 godina prije njega.