Permutace vs. kombinace: Jaký je rozdíl mezi permutačním a kombinačním vzorcem?

Permutace vs. kombinace: Jaký je rozdíl mezi permutačním a kombinačním vzorcem?

Tady je stručná verze.

Vezměme si jako příklad zvonění zvonů v kostele.

Permutace je uspořádání zvonů. Zjišťujete, v jakém pořadí je nejlépe zvonit.

Kombinace je výběr zvonů. Vybíráš zvony, na které se má zvonit. Pokud máte příliš mnoho zvonků, nejprve je vyberete a pak přemýšlíte o jejich pořadí.

Tím vzniká známá identita: (n P r) = (n C r) * r!

Způsob, jak uspořádat r předmětů z n, je takový, že nejprve vyberete r předmětů z n a pak uspořádáte r předmětů (r! )

A to znamená (n P r) = n! / (n-r)! a (n C r) = n! / ( (n-r)! * r! )

Ale chcete vědět, jak si to navždy zapamatovat?

Jsem velkým příznivcem myšlení podle prvního principu. Chci-li pochopit problém, dostanu se k jeho jádru a odtud usuzuji nahoru.

Když to nedělám, je to obvykle zdrojem zmatku: když nechápu, jak věci fungují, nevím, kam zavěsit pojmy. Můj myšlenkový rámec není úplný, a tak se rozhodnu, že si ho prostě zapamatuji.

Jak si dokážete představit, není to ideální. Čas od času si tedy dopřeji cvičení, při kterém odvozuji věci od zdroje a buduji si intuici pro to, jak věci fungují.

Tentokrát si budujeme intuici pro permutace a kombinace.

Víte například, proč je vzorec pro kombinaci (n C r)? Odkud se to vzalo? A proč se zde používají faktoriály?

Začněme u zdroje. Faktoriály, permutace a kombinace se zrodily z matematiků, kteří si spolu hráli, podobně jako Steve Jobs a Steve Wozniak založili Apple, když si spolu hráli v garáži.

Stejně jako se Apple stal plnohodnotnou ziskovou společností, stal se jednoduchý faktoriál, !, atomem celého oboru matematiky: kombinatoriky.

Zapomeňte na všechno, začněme přemýšlet zdola nahoru.

První známý zajímavý případ použití pochází z kostelů ze 17. století.

Přemýšleli jste, jak se zvoní v kostelech? Existuje stroj, který je „rozeznívá“ v daném pořadí. Na stroje jsme přešli, protože zvony jsou příliš velké. Také jsou tam tuny zvonů.

Jak lidé přišli na to, v jakém pořadí je nejlépe zvonit? Co když je chtěli prohodit? Jak mohli najít nejlepší zvuk? Vždyť každá zvonice měla až 16 zvonů!“

Nemohli jste měnit rychlost zvonění – stroje zvonily každou sekundu jen jedním zvonem. Jediné, co jsi mohl udělat, bylo změnit pořadí zvonění. V tomto úkolu šlo tedy o to, zjistit nejlepší pořadí.

Mohli bychom cestou také zjistit všechna možná pořadí? Chceme znát všechna možná pořadí, abychom zjistili, zda má cenu je všechny vyzkoušet.

Tuto výzvu přijal zvoník Fabian Stedman.

Začal se dvěma zvony. V jakém pořadí by mohl na tyto zvony zvonit?“

1 a 2.
nebo
2 a 1.

To dávalo smysl. Jiný způsob neexistoval.

A co takhle se třemi zvony?

1, 2 a 3.
1, 3 a 2.

Tak začít druhým zvonem,

2, 1 a 3.
2, 3 a 1.

Tak začít třetím zvonem,

3, 1 a 2.

Tak začít druhým zvonem,

2, 1 a 3.
2, 3 a 1.

Tak začít třetím zvonem,

3, 1 a 2.
3, 2 a 1.

Celkem 6.

Poté si uvědomil, že je to velmi podobné dvěma zvonům!

Pokud opravil první zvon, pak počet způsobů, jak uspořádat zbývající dva zvony, byl vždy dva.

Kolik způsobů mohl opravit první zvon? Kterýkoli ze tří zvonů mohl být ten pravý!“

Dobře, pokračoval. Pak se dostal k pěti zvonkům.

Tehdy si uvědomil, že dělat věci ručně je těžkopádné. Máš jen tolik času za den, že musíš zvonit, nemůžeš se zdržovat vytahováním všech možných zvonů. Existoval způsob, jak to rychle vyřešit?“

Vrátil se ke svému vhledu.

Pokud měl 5 zvonů a opravil první zvon, stačilo vymyslet, jak objednat 4 zvony.

Pro 4 zvony? No, kdyby měl 4 zvony a opravil první zvon, stačilo by mu vymyslet, jak objednat 3 zvony.

A on věděl, jak to udělat!

Takže objednání 5 zvonů = 5 * objednání 4 zvonů.

Objednání 4 zvonů = 4 * objednání 3 zvonů

Objednání 3 zvonů = 3 * objednání 2 zvonů.

…

. Vidíte tu zákonitost, že?“

Zábavný fakt: Toto je klíč k programovací technice zvané rekurze.

Také on. I když mu to trvalo mnohem déle, protože to nikdo v jeho okolí ještě neobjevil.

Tak přišel na to, že pořadí 5 zvonků = 5 * 4 * 3 * 2 * 1.

Tento vzorec pro pořadí v roce 1808 vešel ve známost jako faktoriál.

Zápis faktoriálu považujeme za základ, ale myšlenka existovala dávno předtím, než měla jméno. Teprve když si francouzský matematik Christian Kramp všiml, že se používá na několika místech, pojmenoval ho faktoriál.

Toto uspořádání zvonků se nazývá permutace.

Permutace je uspořádání položek.

Když se něco učíme, myslím, že nám pomáhá podívat se na věc z každého úhlu pohledu, abychom si upevnili porozumění.

Co kdybychom se pokusili odvodit výše uvedený vzorec přímo, aniž bychom se snažili problém redukovat na menší počet zvonků.
Máme přece 5 míst.

Kolika způsoby můžeme vybrat první zvonek? 5, protože právě tolik zvonků máme.

Druhý zvonek? No, jeden zvonek jsme spotřebovali, když jsme ho umístili na první pozici, takže nám zbývají 4 zvonky.

Třetí zvonek? No, vybrali jsme první dva zvonky, takže nám zbývají už jen 3.

Čtvrtý zvonek? Zbývají už jen 2 zvony, takže 2 možnosti.
Pátý zvonek? Zbývá už jen 1, takže 1 možnost.

A máme to, celkový počet pořadí je 5 * 4 * 3 * 2 * 1

Tím máme náš první obecný vzorec.

Počet způsobů uspořádání N položek je N!

Nyní stojíme před jiným problémem. Král nařídil vyrobit nové zvony pro každý kostel. Některé jsou pěkné, některé jsou v pořádku, z některých ohluchnete. Ale každý z nich je jedinečný. Každý vydává svůj vlastní zvuk. Ohlušující zvon obklopený pěknými zvony může znít majestátně.“

Naší zvonici je však stále 5 zvonů, takže musíme vymyslet nejlepší pořadí z 8 zvonů, které šikovní zvonaři vyrobili.

Podle výše uvedené logiky můžeme postupovat.

Pro první zvon můžeme vybrat kterýkoli z 8 zvonů.

Pro druhý zvon můžeme vybrat kterýkoli ze zbývajících 7 zvonů… a tak dále.

Nakonec dostaneme 8 * 7 * 6 * 5 * 4možných uspořádání 8 zvonků na 5 místech.

Pokud znáte verzi vzorce (n P r), která je n! / (n-r)!, nebojte se, i tu brzy odvodíme!

Jedním ze špatných způsobů odvození je vynásobení čitatele i jmenovatele číslem 3! v našem příkladu výše –

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

To nám ale nepomůže pochopit, proč tento vzorec funguje. Než se k němu dostaneme, podívejme se na výběr věcí neboli Kombinaci.

Kombinace

Teď, když víme, jak věci uspořádat, můžeme přijít na to, jak věci vybrat!

Uvažujme stejný problém. Máme zvonici s 5 zvonky a ty máš 8 zvonků. Právě teď však nechcete vymýšlet pořadí zvonů (nezapomeňte, že to je permutace).

Místo toho chcete vybrat 5 nejlepších zvonů a nechat někoho jiného s lepším hudebním vkusem, aby vymyslel pořadí. V podstatě rozkládáme problém na části: Nejprve zjistíme, které zvony vybrat. Dále vymyslíme, jak vybrané zvony seřadit.

Jak zvony vybrat? To je „kombinace“ z permutací a kombinací.

Kombinace je výběr. Provádíš výběr. Vybíráš 5 zvonů z 8, které vyrobili tvoji řemeslníci.

Protože víme, jak zvony objednat, použijeme tuto informaci k tomu, abychom zjistili, jak zvony vybrat. Zní to nemožně? Počkejte, až uvidíte tu krásnou matematiku, která s tím souvisí.

Představme si, že všechny zvony jsou v řadě.

Než zjistíme všechny způsoby, jak zvony vybrat, zaměříme se na jeden způsob výběru zvonů.

Jedním ze způsobů je náhodný výběr libovolných 5 zvonů. To nám ale při řešení úlohy příliš nepomůže, proto zkusíme jiný způsob.

Zvonky seřadíme do řady a vybereme prvních 5 zvonků. To je jeden ze způsobů výběru zvonků.

Všimněte si, že i když prohodíme pozice prvních 5 zvonků, výběr se nezmění. Stále se jedná o stejný jeden způsob výběru 5 jedinečných zvonků.

To platí i pro poslední tři zvonky.

Teď krásný matematický trik – pro tento jeden způsob výběru 5 zvonků, jaká jsou všechna pořadí 8 zvonků, kde vybereme právě těchto 5 zvonků? Z obrázku výše to jsou všechna pořadí 5 zvonků (5!) a všechna pořadí zbývajících tří zvonků (3!).

Pro každý jednotlivý způsob volby 5 zvonků tedy máme (5! * 3!) pořadí 8 zvonků.

Jaké je celkové možné pořadí 8 zvonků? 8!.

Pamatujme, že pro každou volbu prvních 5 zvonků máme (5! * 3!) uspořádání 8 zvonků, která dávají stejnou volbu.

Pokud tedy vynásobíme počet způsobů volby prvních 5 zvonků všemi možnými uspořádáními jedné volby, měli bychom dostat celkový počet uspořádání.

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

Takže,

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

V matematice to bude:

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

Hle, našli jsme intuitivní vysvětlení, jak vybrat 5 věcí z 8.

Nyní to můžeme zobecnit. Máme-li N věcí a chceme-li z nich vybrat R, znamená to, že na R nakreslíme čáru.

Což znamená, že zbývajících věcí bude N-R. Tedy pro jeden výběr R věcí máme R! * (N-R)! uspořádání, která dávají stejných R věcí.

Pro všechny způsoby výběru R věcí máme N! / (R! * (N-R)!) možností.

Počet způsobů, jak vybrat r položek z n, je (n C r) = n! / (r! * (n-r)!)

V hovorové řeči se (n C r) vyslovuje také n choose r, což pomáhá upevnit myšlenku, že kombinace slouží k výběru položek.

Permutace – znovu

Když máme kombinaci za sebou, vraťme se k druhé části naší práce. Náš milý přítel vybral nejlepších 5 zvonků tak, že zjistil všechny možné kombinace 5 zvonků.

Naším úkolem je nyní najít dokonalou melodii tak, že zjistíme počet pořadí.

Ale, to je ta snadnější část. Už víme, jak objednat 5 položek. Je to 5! a máme hotovo.

Chceme-li tedy permutovat (seřadit) 5 položek z 8, nejprve vybereme 5 položek, pak seřadíme těchto 5 položek.

Jinými slovy,

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

A když vzorec rozšíříme, dostaneme (8 P 5) = (8! / ( 5! * 3!)) * 5!

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

A jsme v plném kruhu u našeho původního vzorce, který jsme správně odvodili.

Počet způsobů uspořádání r prvků z n je (n P r) = n! / (n-r)!

Rozdíl mezi permutací a kombinací

Doufám, že tím je rozdíl mezi permutací a kombinací zcela jasný.

Permutace jsou uspořádání, zatímco kombinace jsou volby.

Pro uspořádání N prvků jsme našli dva intuitivní způsoby, jak zjistit odpověď. Oba vedou k odpovědi N!.

Chceme-li permutovat 5 z 8 prvků, musíme nejprve vybrat 5 prvků a pak je seřadit. Vyberete pomocí (8 C 5), pak seřadíte 5 pomocí 5!.

A intuice pro výběr R z N spočívá v tom, že zjistíte všechna pořadí (N!) a vydělíte pořadí, kde první R a poslední N-R zůstávají stejné (R! a (N-R)!).

A to je vše, co se týká permutací a kombinací.

Každá pokročilá permutace a kombinace používá tento základ. Kombinace s nahrazením? Stejná myšlenka. Permutace se stejnými předměty? Stejná myšlenka, jen se mění počet pořadí, protože některé položky jsou totožné.

Pokud máte zájem, můžeme se složitějším případům věnovat v jiném příkladu. Dejte mi vědět na Twitteru.

Podívejte se na další příspěvky na mém blogu a přidejte se do týdenního mailing listu.

Poznámky na závěr

1. Takhle si představuji, že na to přišel. Neberte to jako lekci z dějepisu.
2. Indiáni měli ve 12. století 400 let před ním.

.