Itt a rövid változat.

Vegyük példának a templomban lévő harangozást.

A permutáció a harangok rendezése. Kitalálod a legjobb parancsot, hogy becsengessék őket.

A kombináció a harangok választása. A csengettyűket választod. Ha túl sok harangja van, először válassza ki őket, majd gondolkodjon el a megrendelésen.

Ez adja a megszokott identitást: (n P r) = (n C r) * r!

rElemek megrendelésének módja az n, ha először kiválasztja az relemeket, nmajd megrendeli az relemeket ( r!)

És ez azt jelenti (n P r) = n! / (n-r)!és(n C r) = n! / ( (n-r)! * r! )

De szeretnéd tudni, hogyan emlékezz erre örökre?

Nagy rajongója vagyok az első elvek gondolkodásának. A probléma megértéséhez jutjon el annak lényegéhez és érveljen fel onnan.

Ennek elmulasztása általában a zavart okozza: ha nem értem a dolgok működését, akkor nem tudom, hova akaszthatom a fogalmakat. A mentális keretem nem teljes, ezért úgy döntök, hogy csak emlékezni fogok rá.

Ahogy el lehet képzelni, ez nem ideális. Szóval időről időre elkényeztetem magam egy gyakorlattal, hogy a dolgokat a forrásból nyerjem, és építsek intuíciót a dolgok működésére.

Ezúttal intuíciót építünk a permutációk és kombinációk számára.

Például tudod, miért egy kombináció képlete (n C r)? Honnan jött ez? És miért használják itt a gyárakat?

Kezdjük a forrásnál. A tényezők, a permutációk és a kombinációk matematikusok együttes játékából születtek, hasonlóan ahhoz, ahogyan Steve Jobs és Steve Wozniak megalapították az Apple-t a közös garázsban.

Csakúgy, mint ahogy az Apple teljes értékű nyereséges vállalattá vált, az egyszerű faktoriál, !a matematika egy teljes területének atomjává vált: a kombinatorika.

Felejts el mindent, kezdjünk alulról felfelé gondolkodni.

Az első ismert érdekes eset az egyházaktól származott a 17. században.

Elgondolkodott azon, hogyan harangozzák meg a templomokban a harangokat? Van egy gép, amely "csengeti" őket rendben. Gépekre váltottunk, mert a harangok túl nagyok. Emellett rengeteg harang van.

Hogyan találták ki az emberek a legjobb sorrendet, amelyben becsengetik őket? Mi lenne, ha fel akarnák váltani a dolgokat? Hogyan tudták megtalálni a legjobb hangot? Minden harangtoronynak legfeljebb 16 harangja volt!

Nem tudta megváltoztatni, milyen gyorsan csengessen - a gépek másodpercenként csak egyet csengettek. Az egyetlen dolog, amit tehetett, az volt, hogy megváltoztatta a harangok sorrendjét. Tehát ez a kihívás a legjobb sorrend kitalálására vonatkozott.

Megtudhatnánk útközben az összes lehetséges megrendelést is? Szeretnénk tudni minden lehetséges megrendelést, hogy kiderüljön, érdemes-e mindet kipróbálni.

Fabian Stedman harangozó vette fel ezt a kihívást.

2 haranggal kezdte. Milyen sorrendben csengetheti ezeket a harangokat? [1]

1. és 2.

vagy

2. és 1.

Ennek volt értelme. Nem volt más út.

Mit szólnál 3 haranghoz?

1., 2. és 3.

1., 3. és 2.

Ezután kezdve a második csengővel,

2., 1. és 3.

2, 3 és 1.

Ezután kezdve a harmadik csengővel,

3, 1 és 2.

3, 2 és 1.

Összesen, 6.

Aztán rájött, hogy ez nagyon hasonlít két harangra!

Ha megjavította az első csengőt, akkor a maradék két harang megrendelésének módja mindig kettő volt.

Hányféleképpen tudta megjavítani az első csengőt? A 3 harang közül bármelyik lehet az egyik!

Oké, folytatta. Ezután elérte az 5 harangot.

Ekkor jött rá, hogy nehéz kézzel végezni a dolgokat. Csak annyi időd van a napban, harangoznod kell, nem ragaszkodhatsz az összes lehetséges harang kihúzásához. Volt rá mód, hogy ezt gyorsan kitaláljuk?

Visszatért az éleslátására.

Ha 5 harangja volt, és az első harangot kijavította, csak annyit kellett tennie, hogy kitalálja, hogyan rendeljen 4 harangot.

4 harangra? Nos, ha 4 harangja van, és megjavítja az első harangot, csak annyit kell tennie, hogy kitalálja, hogyan rendeljen meg 3 harangot.

És tudta, hogyan kell ezt megtenni!

Tehát 5 harang rendezése = 5 * 4 harang rendezése.

4 harang rendezése = 4 * 3 harang rendezése

3 harang rendezése = 3 * 2 harang rendezése.

.. Ugye látod a mintát?

Szórakoztató tény: Ez a rekurziónak nevezett programozási technika kulcsa.

Ő is megtette. Bár sokkal tovább tartott, mivel a közelében még senki sem fedezte fel ezt. [2]

Így kitalálta, hogy 5 harang rendezése = 5 * 4 * 3 * 2 * 1.

Ezt a megrendelési képletet 1808-ban faktoriál néven ismerték el.

A faktoriális jelölésre gondolunk, mint alapra, 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, akkor nevezte el a faktoriálnak.

A harangok ezen sorrendjét permutációnak nevezzük.

A Permutáció a tételek sorrendje.

Ha tanulok valamit, úgy gondolom, hogy segít a dolgok minden más szemszögből való szemlélésében, a megértés megszilárdításában.

Mi lenne, ha megpróbálnánk a fenti képletet közvetlenül levezetni, anélkül, hogy megpróbálnánk kisebb harangszámra csökkenteni a problémát?

5 helyünk van, igaz?

Hányféleképpen választhatjuk ki az első harangot? 5, mert ennyi harangunk van.

A második harang? Nos, egy csengőt felhasználtunk, amikor az első pozícióba helyeztük, így 4 harangunk maradt.

A harmadik harang? Nos, mi választottuk az első kettőt, így csak 3 harang maradt a választás közül.

A negyedik harang? Csak 2 harang maradt, tehát 2 lehetőség.

Az ötödik harang? Csak 1 maradt, tehát 1 lehetőség.

És itt van, a megrendelések teljes száma 5 * 4 * 3 * 2 * 1

Így megvan az első általános képletünk.

Az Nelemek megrendelésének száma : N!

A permutáció

Most egy másik problémával állunk szemben. A király minden templomhoz új harangok készítését rendelte el. Van, aki kedves, van, aki rendben van, van, aki megsüketít. De mindegyik egyedi. Mindegyik saját hangot ad ki. A szép harangokkal körülvett fülsiketítő harang fenségesen szólhat.

De harangtornyunk továbbra is 5 harangot tart, ezért ki kell találnunk a legjobb harangot a 8 harang közül, amelyet a képzett harangkészítők készítettek.

A fenti logika segítségével folytathatjuk.

Az első csengőre 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 ... stb.

Végül 8 * 7 * 6 * 5 * 48 harang lehetséges megrendelését kapjuk 5 térben.

Ha ismeri az (n P r) képletes változatát n! / (n-r)!, vagyis ne aggódjon, ezt is elég hamar levezetjük!

Ennek levezetésének egyik rossz módja, ha mind a számlálót, mind a nevezőt megszorozzuk 3-mal! a fenti példánkban -

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

De ez nem segít megérteni, miért működik ez a képlet. Mielőtt odaérnénk, vessünk egy pillantást a dolgok kiválasztására vagy a Kombinációra.

A kombináció

Most, hogy tudjuk, hogyan kell megrendelni a dolgokat, kitalálhatjuk, hogyan válasszuk ki a dolgokat!

Nézzük ugyanezt a problémát. Van harangtorony 5 haranggal, és neked 8 harang van. Azonban most nem akarja kitalálni a harangok sorrendjét (ne feledje, hogy ez a permutáció).

Ehelyett az 5 legjobb harangot szeretné kiválasztani, és hagyja, hogy valaki más, jobb zeneízléssel találja ki a sorrendet. Valójában részekre bontjuk a problémát: Először kitaláljuk, melyik harangot válasszuk. Ezután kitaláljuk, hogyan kell megrendelni a kiválasztott harangokat.

Hogyan választja meg a harangokat? Ez a "kombináció" a permutációkból és a kombinációból.

A kombináció egy válogatás. Szelektív vagy. 5 harangot választasz a kézművesek által készített 8 közül.

Mivel tudjuk, hogyan kell harangokat rendelni, ezt az információt felhasználjuk arra, hogy kitaláljuk, hogyan válasszunk harangokat. Lehetetlenül hangzik? Várjon, amíg meglátja a gyönyörű matekot.

Képzeljük el, hogy az összes harang egy vonalban van.

Mielőtt megtalálnánk a harangválasztás minden módját, koncentráljunk a harangválasztás egyik módjára.

Az egyik mód az, hogy bármelyik 5-öt véletlenszerűen választja. Ez nem segít sokat megoldani a problémát, ezért próbálkozzunk más módon.

A harangokat egy vonalba tesszük, és kiválasztjuk az első 5-öt. Ez a harangok kiválasztásának egyik módja.

Vegye figyelembe, hogy még ha az első 5 harang helyzetét is megváltoztatjuk, a választás nem változik. Még mindig ugyanaz az egyetlen módja annak, hogy 5 egyedi harangot válasszanak.

Ez igaz az utolsó három harangra is.

Most, a gyönyörű matematikai trükk - az öt harang kiválasztásának egyetlen módja szerint mi a 8 harang sorrendje, ahol pontosan ezt az 5 harangot választjuk? A fenti képen látható az 5 harang ( 5!) és a maradék három harang ( 3!) összes rendje .

Így az 5 harang kiválasztásának minden egyes módjára ( 5! * 3!) 8 harang rendelése van.

Mennyi a lehetséges 8 harang rendelése? 8!.

Ne feledje, hogy az első 5 harang minden egyes választásához ( 5! * 3!) 8 csengőből állunk ( ), amelyek ugyanazt a választást adják.

Ezután, ha megsokszorozzuk az első 5 harang kiválasztásának módjainak számát az összes választható lehetséges rendeléssel, meg kell kapnunk a megrendelések teljes 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. 

A matematikában ez lesz:

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

Íme, találtunk egy intuitív magyarázatot arra, hogyan válasszunk 5 dolgot a 8 közül.

Most ezt általánosíthatjuk. Ha N dolgunk van, és közülük R-t akarunk választani, ez azt jelenti, hogy R-re húzzunk egy vonalat.

Ami azt jelenti, hogy a fennmaradó elemek lesznek N-R. Tehát, egy választott Rterméket, van R! * (N-R)!megrendeléseknek, amelyek segítségével az azonos Relemeket.

A Rtételek kiválasztásának minden módjára N! / (R! * (N-R)!)lehetőségünk van.

A számos módon lehet választani rdarabot a njelentése(n C r) = n! / (r! * (n-r)!)

Köznyelvi értelemben az (n C r) kiejtés is megtörténik n choose r, ami segít megszilárdítani azt az elképzelést, hogy a kombinációk az elemek kiválasztására szolgálnak.

A Permutáció - áttekintve

A kész és leporolt ​​kombinációval térjünk vissza munkánk 2. részéhez. Kedves barátunk a legjobb 5 harangot választotta ki azzal, hogy kitalálta 5 harang összes lehetséges kombinációját.

Most az a feladatunk, hogy megtalálja a tökéletes dallamot a megrendelések számának kitalálásával.

De ez a könnyű darab. 5 cikk megrendelését már tudjuk. Ez van 5!, és kész.

Tehát a 8 közül 5 elem permutálásához (rendezéséhez) először 5 tételt választunk, majd megrendeljük az 5 tételt.

Más szavakkal,

(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 teljes körrel jártunk az eredeti, megfelelően levezetett képletünkhöz.

A rtermékek rendelési módjainak száma n:(n P r) = n! / (n-r)!

Különbség a permutáció és a kombináció között

Remélem, hogy ez kristálytisztavá teszi a különbséget a permutációk és a kombinációk között.

A permutációk sorrendek, 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 kitalálására. Mindkét vezető a választ, N!.

A 8 elem közül 5 permutálásához először ki kell választania az 5 elemet, majd meg kell rendelnie őket. Ön úgy dönt, hogy használja (8 C 5), majd megrendeli az 5-öt 5!.

És az az intuíció, a választott Rki Nkitalálni, minden megrendeléseknek ( N!), és elosztjuk megrendeléseknek, ahol az első Rés az utolsó N-Rugyanaz marad ( R!és (N-R)!).

És csak ennyi van a permutációknál és a kombinációknál.

Minden fejlett permutáció és kombináció ezt használja alapul. Kombináció cserével? Ugyanez az ötlet. Permutáció azonos elemekkel? Ugyanaz az elképzelés, csak a megrendelések száma változik, mivel egyes elemek azonosak.

Ha érdekel, egy másik példában részletezhetjük az összetett eseteket. Tudassa velem a Twitteren.

Nézzen meg további bejegyzéseket a blogomon, és csatlakozzon a heti levelezőlistához.

Végjegyzetek

1. Így képzelem, hogy kitalálta a dolgokat. Ne vegye a történelem tanulságának.
2. Az indiánok a 12. században 400 évvel voltak előtte.