Permutáció vs kombináció: Mi a különbség a permutációs képlet és a kombinációs képlet között?
Itt a rövid változat.
Mondjuk példának a harangok harangozását egy templomban.
A permutáció a harangok rendezése. Kitalálod, hogy melyik a legjobb sorrend a harangozáshoz.
A kombináció a harangok kiválasztása. Kiválasztod a harangokat, amiket megkongatsz. Ha túl sok harangod van, akkor először kiválasztod őket, és csak utána gondolkodsz a sorrendjükön.
Ebből adódik az ismert azonosság: (n P r) = (n C r) * r!
Az n elemekből r elemet úgy tudsz rendezni, hogy először n elemekből r elemet választasz ki, majd a r elemeket (r! )
És ez azt jelenti, hogy (n P r) = n! / (n-r)! és (n C r) = n! / ( (n-r)! * r! )
De akarod tudni, hogyan lehet ezt örökre megjegyezni?
Az első elvű gondolkodás nagy híve vagyok. Ahhoz, hogy megértsek egy problémát, jussak el a lényegéig, és onnan érveljek felfelé.”
Az, hogy nem ezt teszem, általában a zavar forrása: ha nem értem, hogyan működnek a dolgok, nem tudom, hová akasszam a fogalmakat. A mentális keretrendszerem nem teljes, ezért úgy döntök, hogy csak emlékszem rá.
Amint elképzelheted, ez nem ideális. Ezért időről időre engedek magamnak egy olyan gyakorlatot, amelyben levezetem a dolgokat a forrásból, és intuíciót építek a dolgok működésére.
Ezúttal a permutációk és kombinációk intuícióját építjük fel.
Tudod például, hogy a kombináció képlete miért (n C r)? Honnan származik ez? És miért használnak itt faktoriálisokat?
Kezdjük a forrásnál. A faktoriálisok, a permutációk és a kombinációk matematikusok közös játékából születtek, hasonlóan ahhoz, ahogy Steve Jobs és Steve Wozniak a garázsukban együtt játszva alapították meg az Apple-t.
Amint ahogy az Apple-ből egy teljes értékű, nyereséges vállalat lett, az egyszerű faktoriális, ! egy egész matematikai terület atomja lett: a kombinatorika.
Felejtsünk el mindent, kezdjünk el alulról felfelé gondolkodni.
Az első ismert érdekes felhasználási eset az egyházakból származik a 17. századból.
Elgondolkodott már azon, hogyan szólnak a harangok a templomokban? Van egy gép, ami sorrendben “kongatja” őket. Azért tértünk át a gépekre, mert a harangok túl nagyok. Ráadásul rengeteg harang van.
Hogyan találták ki a legjobb sorrendet a harangozáshoz? Mi van, ha váltogatni akarták a dolgokat? Hogyan tudták megtalálni a legjobb hangot? Minden harangtoronyban akár 16 harang is lehetett!
Nem lehetett változtatni azon, hogy milyen gyorsan lehetett harangozni – a gépek másodpercenként csak egy harangot szólaltattak meg. Az egyetlen dolog, amit megtehettél, az a harangok sorrendjének megváltoztatása volt. Tehát ez a kihívás arról szólt, hogy kitaláljuk a legjobb sorrendet.
Mehetnénk-e útközben az összes lehetséges sorrendet is kitalálni? Meg akarjuk ismerni az összes lehetséges sorrendet, hogy kitaláljuk, érdemes-e mindet kipróbálni.
Egy harangozó, Fabian Stedman vállalta ezt a kihívást.
Elkezdte 2 haranggal. Milyen sorrendben tudná ezeket a harangokat megszólaltatni?
1 és 2.
vagy
2 és 1.
Ezeknek volt értelme. Nem volt más lehetőség.
Hogyan lenne 3 haranggal?
1, 2 és 3.
1, 3 és 2.
A második haranggal kezdve,
2, 1 és 3.
2, 3 és 1.
A harmadik haranggal kezdve,
3, 1 és 2.
3, 2, és 1.
összesen, 6.
Ezután rájött, hogy ez nagyon hasonlít a két harangra!
Ha az első harangot rögzítette, akkor a maradék két harang rendezésének módja mindig kettő.
Hányféleképpen tudta rögzíteni az első harangot? A három harang közül bármelyik lehetett az!
Oké, folytatta. Aztán eljutott az 5 harangig.
Ekkor jött rá, hogy kézzel csinálni a dolgokat nehézkes. Csak annyi időd van a nap folyamán, hogy csengetned kell, nem ragadhatsz le azzal, hogy az összes lehetséges csengőt kihúzod. Volt rá mód, hogy ezt gyorsan kitalálja?
Visszatért a belátásához.
Ha 5 harangja volt, és az elsőt megjavította, már csak ki kellett találnia, hogyan rendeljen 4 harangot.
Négy harangért? Nos, ha 4 harangja volt, és megjavította az első harangot, akkor csak ki kellett találnia, hogyan rendeljen 3 harangot.
És ő tudta, hogyan kell ezt csinálni!
Szóval, 5 harang rendelése = 5 * 4 harang rendelése.
4 harang rendelése = 4 * 3 harang rendelése
3 harang rendelése = 3 * 2 harang rendelése.
… Látod a mintát, ugye?
Fun Fact: Ez a rekurziónak nevezett programozási technika kulcsa.
Ő is látta. Bár neki sokkal tovább tartott, mivel a közelében senki sem fedezte ezt még fel.
Így jött rá, hogy 5 harang rendezése = 5 * 4 * 3 * 2 * 1.
Ezt a rendezési képletet 1808-ban faktoriálisnak nevezték el.
Mi a faktoriális jelölést alapnak gondoljuk, de az ötlet már jóval azelőtt létezett, hogy neve lett volna. Csak amikor Christian Kramp francia matematikus észrevette, hogy néhány helyen használják, nevezte el faktoriálnak.
A harangok ezen rendezését permutációnak nevezzük.
A permutáció elemek rendezése.
Amikor valamit tanulunk, azt hiszem, segít, ha a megértés megszilárdítása érdekében minden különböző szemszögből nézzük a dolgokat.
Mi lenne, ha a fenti képletet közvetlenül próbálnánk levezetni, anélkül, hogy megpróbálnánk a problémát kisebb számú harangra redukálni?
5 helyünk van, igaz?
Hányféleképpen választhatjuk ki az első harangot? 5, mert ennyi harangunk van.
A második harangot? Nos, egy harangot elhasználtunk, amikor az első helyre tettük, tehát maradt 4 harangunk.
A harmadik harang? Nos, az első kettőt már kiválasztottuk, így már csak 3 harang maradt.
A negyedik harang? Már csak 2 harang maradt, tehát 2 lehetőség.
Az ötödik harang? Már csak 1 maradt, tehát 1 lehetőség.
És meg is van, a rendelések száma összesen 5 * 4 * 3 * 2 * 1
Így megvan az első általános képletünk.
Az
Ntétel rendelési módjainak számaN!
Most egy másik problémával állunk szemben. A király elrendelte, hogy minden templomba új harangokat készíttessenek. Némelyik szép, némelyik rendben van, némelyiktől megsüketülsz. De mindegyik egyedi. Mindegyik a saját hangját adja. Egy süketítő harang szép harangokkal körülvéve fenségesen szólhat.
De a harangtornyunkban még mindig 5 harang van, ezért ki kell találnunk a legjobb sorrendet a 8 harang közül, amit az ügyes harangkészítők készítettek.
A fenti logikát alkalmazva továbbléphetünk.
Az első haranghoz a 8 harang közül bármelyiket választhatjuk.
A második haranghoz a maradék 7 harang közül bármelyiket választhatjuk… és így tovább.
A végén kapunk 8 * 7 * 6 * 5 * 4 lehetséges elrendezéseket 8 harangra 5 térben.
Ha ismered az (n P r) képletváltozatát, ami n! / (n-r)!, ne aggódj, hamarosan azt is levezetjük!
Egy rossz módja a levezetésnek, ha mind a számlálót, mind a nevezőt megszorozzuk 3-mal! a fenti példánkban –
a 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1 = 8! / 3! kapjuk.
De ez nem segít megérteni, miért működik ez a képlet. Mielőtt erre rátérnénk, nézzük meg a dolgok kiválasztását, vagyis a kombinációt.
A kombináció
Most, hogy tudjuk, hogyan kell elrendezni a dolgokat, rájöhetünk, hogyan kell kiválasztani a dolgokat!
Mondjuk meg ugyanezt a problémát. Van egy harangláb 5 haranggal, és neked 8 harangod van. Most azonban nem akarod kitalálni a harangok sorrendjét (ne feledd, hogy ez a permutáció).
Ehelyett ki akarod választani az 5 legjobb harangot, és hagyod, hogy más, jobb zenei ízlésű ember találja ki a sorrendet. Gyakorlatilag részekre bontjuk a problémát: Először is, kitaláljuk, hogy melyik harangot válasszuk. Ezután kitaláljuk, hogyan rendezzük a kiválasztott harangokat.
Hogyan válasszuk ki a harangokat? Ez a “kombináció” a permutációkból és a kombinációból.
A kombináció egy kiválasztás. Te válogatsz. Kiválasztasz 5 harangot abból a 8 harangból, amit a mesterembereid készítettek.
Mivel tudjuk, hogyan kell harangokat rendelni, ezt az információt felhasználjuk arra, hogy kitaláljuk, hogyan válasszuk ki a harangokat. Lehetetlenül hangzik? Várj, amíg meglátod, milyen gyönyörű matematika áll mögötte.
Tegyük fel, hogy az összes harang egy sorban van.
Mielőtt kitalálnánk az összes módját a harangok kiválasztásának, koncentráljunk egy módra.
Az egyik mód az, hogy véletlenszerűen választunk ki 5 tetszőlegeset. Ez nem sokat segít a feladat megoldásában, ezért próbáljunk meg egy másik módszert.
Tegyük a csengőket egy sorba, és válasszuk ki az első 5-öt. Ez az egyik módja a csengők kiválasztásának.
Megfigyelhetjük, hogy még akkor sem változik a választás, ha az első 5 csengő helyét megváltoztatjuk. Még mindig ugyanaz az egyféleképpen választhatunk 5 egyedi harangot.
Ez igaz az utolsó három harangra is.
Most jön a szép matematikai trükk – az 5 harang kiválasztásának erre az egyféle módjára nézve, mi a 8 harang összes olyan sorrendje, ahol pontosan ezt az 5 harangot választjuk? A fenti kép alapján az 5 harang összes rendezése (5!) és a maradék három harang összes rendezése (3!).
Így az 5 harang kiválasztásának minden egyes módjára van (5! * 3!) 8 harang rendezése.
Mi a 8 harang összes lehetséges rendezése? 8!.
Megjegyezzük, hogy az első 5 harang minden egyes választási lehetőségére van (5! * 3!) 8 harang olyan elrendezése, amely ugyanazt a választást adja.
Ezután, ha az első 5 harang választási módjainak számát megszorozzuk egy választás összes lehetséges elrendezésével, akkor meg kell kapnunk az összes elrendezések számát.
Ways to choose 5 bells * orderings of one choice = Total orderingsÍgy,
Ways to choose 5 bells = the total possible orderings / total orderings of one choice.Matematikailag ez így lesz:
(8 C 5) = 8! / ( 5! * 3!)Láss csodát, találtunk egy intuitív magyarázatot arra, hogyan választhatunk 5 dolgot a 8-ból.
Most, ezt általánosíthatjuk. Ha N dolgunk van, és ezek közül R dolgot akarunk kiválasztani, akkor ez azt jelenti, hogy húzunk egy vonalat R-nél.
Ami azt jelenti, hogy a fennmaradó elemek N-R lesznek. Tehát R tárgyak egy választása esetén R! * (N-R)! olyan rendezésünk van, amely ugyanazt a R tárgyat adja.
Az összes R tárgy választási módra vonatkozóan N! / (R! * (N-R)!) lehetőségünk van.
Az
ntételbőlrtétel kiválasztásának módjainak száma(n C r) = n! / (r! * (n-r)!)
A köznyelvben az (n C r) kiejtése is n choose r, ami segít megszilárdítani a gondolatot, hogy a kombinációk a tételek kiválasztására szolgálnak.
A permutáció – újragondolva
Mivel a kombinációval végeztünk, térjünk vissza feladatunk második részéhez. Kedves barátunk úgy választotta ki a legjobb 5 harangot, hogy kiszámolta az 5 harang összes lehetséges kombinációját.
A mi feladatunk most az, hogy a sorrendek számának kiszámításával megtaláljuk a tökéletes dallamot.
De, ez a könnyű rész. Már tudjuk, hogyan kell 5 darabot rendelni. Ez 5!, és kész is vagyunk.
Azért, hogy 8-ból 5 elemet permutáljunk (rendezzünk), először kiválasztunk 5 elemet, majd az 5 elemet rendezzük.
Más szóval,
(8 P 5) = (8 C 5) * 5!És ha kibővítjük a képletet, (8 P 5) = (8! / ( 5! * 3!)) * 5!
(8 P 5) = 8! / 3!.
És máris teljes a kör az eredeti, helyesen levezetett képletünkhöz.
A
nelembőlrelem rendezésének módjainak száma(n P r) = n! / (n-r)!
A permutáció és a kombináció közötti különbség
Remélem, ezzel kristálytisztán érthetővé vált a permutációk és a kombinációk közötti különbség.
A permutációk rendezések, míg a kombinációk választási lehetőségek.
N elem rendezéséhez két intuitív módszert találtunk a válasz kiszámítására. Mindkettő a N! válaszhoz vezet.
Hogy 8 elemből 5 elemet permutáljunk, először ki kell választanunk az 5 elemet, majd rendezni kell őket. A (8 C 5) segítségével választasz, majd a 5!.
Az N-ból R kiválasztásának intuíciója pedig az, hogy kitalálod az összes rendezést (N!), és osztasz azokkal a rendezésekkel, ahol az első R és az utolsó N-R ugyanaz marad (R! és (N-R)!).
És ennyi a permutációk és kombinációk alapja.
Minden haladó permutáció és kombináció ezt használja alapként. Kombináció helyettesítéssel? Ugyanaz az ötlet. Permutáció azonos elemekkel? Ugyanaz az ötlet, csak a sorrendek száma változik, mivel néhány elem azonos.
Ha érdekel, egy másik példában belemehetünk az összetett esetekbe. Szólj nekem a Twitteren.
Nézz meg még több bejegyzést a blogomon, és csatlakozz a heti levelezőlistához.
Végjegyzetek
- Így képzelem, hogy kitalálta a dolgokat. Ne vedd történelmi leckének.
- Az indiánok a 12. században, 400 évvel előtte
már megtették.