Hogyan tudnám jól megérteni a Kombinatorikát,Permutációt,Variációt. Mi a permutáció és a variáció közt a különbség? Hogy tudnám minnél egyszerűbben kiszámolni a lehetőségeket?

Permutáció - tornasor az iskolában

Variáció - futóverseny eredménye

Nagyon röviden:

A permutáció (ismétlés nélküli)az összes elem lehetséges sorrendjeinek száma. Pl. a hét törpe összes sorrendje: 7*6*5*4*3*2*1=7! (faktoriális)

A variáció (ismétlés nélkül) pedig nem az összes elem, hanem pl. a dobogós helyezések száma egy 8 fős úszódöntőben: 8*7*6

De ennyiből nem lehet megtanulni a kombinatorikát.

Egyébként magántanárként észlelem, hogy a kombinatorikát szinte mindenhol rossz módszerrel tanítják, és a legtöbb helyen kis ideig valamikor év végére tolva.

Valami rejtélyes okoknál fogva a definíciók lediktálásával kezdik, és ebben a sorrendben: permutáció, variáció, kombináció. Így ezt nem lehet megtanulni.

Holott az ésszerű és hatékony sorrend ez lenne:

(0) egyedi felsorolós feladatok

(1) ism. nélküli variáció (totó, PIN-kód)

(2) ismétléses variáció (dobogós helyek)

(3) ism. nélküli permutáció (faktoriális)

(4) ismétléses permutáció (gyöngyfűzés, anagramma)

(5) ism. nélküli kombináció (küldöttségválasztás)

(6) ismétléses kombináció (fagylaltkehely...)

(7) ugyanezek mindenféle feltételekkel

Én így tanítom sok-sok éve, rengeteg gyakorló feladattal és nem év végére kitolva, elkapkodva. Az én tanítványaimnak pont a kombinatorika okozza a legkevesebb problémát.

(Annyit megsúgok, hogy sok matektanár nem is kedveli a kombinatorikát és a valószínűségszámítást, mert nem egészen biztosak a megoldásokban. Az egykori évfolyamtársaim nagyobb része olyannyira nem értett a valszámhoz, hogy úgy kellett lesúgni a vizsgát az egyetemen.

Több iskolában is tapasztaltam ezt kollégáknál, volt aki bevallja, volt, aki nem. Emiatt halogatják, az év végefelé gyorsan átnyomják ami a tankönyvben van, se többet, se kevesebbet, mert annak megvannak a megoldásai. Sok emelt előkészítős tanítványom a kapott feladatot a tanára segítségével oldotta meg .... rosszul.)

Nagyon egyszerű, azt kell átgondolni hozzá, hogy miről van szó. Van az ismétlés nélküli és az ismétléses, és mindkettőből van permutáció, variáció, kombináció is (összesen 6 féle).

A kombinatorika alapja, hogy ha van 2 helyem, egyikre n másikra m dologból választhatok _egymástól_függetlenül_ (ez nagyon fontos), akkor a kettő szorzata lesz az összes lehetőség. A másik, hogy ha n dolgot választhatok k helyre, és minden helyre minden lehetőség adott, akkor n^k (n a káadikon, szóval hatvány, n*n*n*...*n összesen k-szor) a lehetőségek száma.

Feladatnál mindenképp meg kell állapítanod először, hogy van-e (és ha igen, mik között) összefüggés, illetve hogy az ismétléssel mi a helyzet (választhatod-e ugyanazt többször). Mondjuk lehet, hogy egy ideális focicsapat egy jó kapusból állna meg 10 Messiből, de 1 van belőle összesen (itt nem választhatunk egy ember többször).

Az (ismétlés nélküli) permutáció dolgok sorrendjéről szól, a variáció arról, hogy kiválasztunk dolgokat, és számít ezek sorrendje is, a kombináció meg arról, hogy a sorrend nem számít. Mondjuk egy halmazban nem számít az elemek sorrendje, egy szóban a betűké igen. Versenynél fontos, hogy ki lett az első, ki a második, lottóhúzásnál viszont nem számít hanyadikként húztak ki egy adott számot (vagy hanyadikként X-elted be).

Ismétlés nélküli permutáció: van n dolgunk, hányféle módon tudjuk őket sorbatenni. Ugye az első helyre n lehetőségünk van, másodikra n-1 (elsőt nem választhatjuk, de mindig pontosan 1 esik ki), harmadikra n-2, stb.. utolsó előttire 2 marad, utolsóra meg marad 1, ami egészen addig kimaradt. Ez összesen n*(n-1)*(n-2)*...*2*1, azaz n! (n faktoriális). Ez a másik ilyen alap, amire a többit vissza lehet vezetni.

Pl.:Mondjuk a "NYUSZI" szó karaktereinek (nem betűinek, abból a dupla betűk miatt 4 van) sorrendje 6! lesz.

Ismétléses permutáció: Van n elemünk, ezeket akarjuk sorrendbe állítani, de vannak köztük azonosak. Ha nem a "NYUSZI", hanem a "CICA" lenne a szavunk, egy csomót duplán számolnánk, ahol csak a két C betűnek a sorrendje tér el. Ha az "ABBA" szó lenne, a helyzet még rosszabb: itt két-két egyező betűnk van. Hogy lehet ezt megoldani? Szerencsére egy ilyen betűduplázásnál minden szót pontosan kétszer számoltunk, szóval le tudjuk osztani vele. A cicánál hányféleképpen lehet a 2 C betű sorrendje? 2! sorrend lehet (vagy ha 3 azonos van, 3!=6, 4 azonosnál 4!=4, stb.). Ha több duplázás/triplázás van (pl. ABBA), akkor leosztjuk mindkettővel. Kicsit általánosabban (és képlettel): van n dolgunk, ebből k_1 (k, utána 1 alsóindexben), k_2, stb. k_r (r dolog, most mondjuk ezzel jelölöm) azonos. Ezek k_1!, k_2!, ..., k_r! féle sorrendben lehetnének _egymástól_függetlenül_. Szóval először úgy vesszük, mint ha n különböző betűnk lenne, aztán leosztogatjuk ezek sorrendjével. A vége ez lesz: n!/(k_1! * k_2! * ... * k_r!)

Ismétléses variáció: n dologból k helyre választhatunk dolgokat, egymástól függetlenül (első választás nem befolyásolja a következőt), ez ugye a hsz elején kifejtett gondolatmenet miatt n^k.

Pl.: pin kód, 10 számjegyből választhatunk pontosan 4-et, nem kell, hogy különbözzenek, a sorrendje viszont számít. 10^4=10000 pin kódunk lehet.

Ismétlés nélküli variáció: n dologból k darabot választunk, számít a sorrend, de amit már kiválasztottunk egyszer, azt nem választhatjuk újra. Pl.: dobogós helyek. Legyen futóverseny, ott 8 pálya van 8 indulóval a legegyszerűbb esetben, és a 3 dobogós érdekel. Itt kétféle módon okoskodhatunk: Az egyik, hogy azt mondjuk, első helyre 8 embert választhatunk, 2. helyre már csak 7-et (az első nem lehet második is), 3. helyre 6 maradt, ezek szorzata 8*7*6. A másik, hogy trükközünk: hány sorrend lehet összesen, mind a 8 indulót figyelembe véve? 8! természetesen (8 elem sorrendje, ld. ism. nélküli permutáció, nagyon hasznos). Ebból ugye 3 érdekel, a maradék 5 induló nem. De a 8! ezeket is figyelembe vette, vajon hányszor? Mindegyik 5!-féle módon lehet, szóval ennyiszer. Ha a 8 faktoriálisát leosztjuk az 5 faktoriálisával, egy csomó kiesik belőle. Ugye úgy nézne ki, hogy (8*7*6*5*4*3*2*1)/(5*4*3*2*1). Az 5 és azutániak kiesnek, marad a 8*7*6, ami pont ugyanaz, mint a másik gondolatmenetnél.

Általánosan: Van n dolgunk, k dolgot választhatunk, ezek sorrendje számít , amit nem választottunk, azok sorrendje értelemszerűen nem. Ugyanazzal a gondolatmenettel a megoldás: n!/((n-k)!), mert n-k dolgot nem választottunk, ezek sorrendje van a nevezőben (az 5 "futottak még" versenyző, akire nem voltunk kíváncsiak).

Ismétlés nélküli kombináció: ez a másik "alap", ami nagyon fontos. Van n dolgunk, ebből k különböző dolgot választunk, de ezek sorrendje nem számít. Az "n elemű halmaz k elemű részhalmazainak száma", ez van a Pascal-háromszögben is, előjön a nevezetes azonosságoknál, és csomó másik helyen.

Az ismétlés nélküli variáció ugye hasonlít hozzá, annyi, hogy itt a kiválasztott k elem sorrendje sem számít. Akkor ha ki akarjuk számolni ezt, egyszerűen leosztjuk annak a k elemnek a sorrendjével (k! ugye), és kész is vagyunk. Emiatt n!/((n-k)!*k!) lesz. Ezt szokták úgy is hívni, hogy n alatt a k. Leírnak egymás alá egy n-et és k-t, és ezeket bezárójelezik.

pl: erre rengeteg van, mondjuk az n elemű halmaz k elemű részhalmazainak száma. Van 5 különböző golyónk, hányféleképp választhatunk ki belőle 3-at? 5 alatt a 3, ami kis számolással 10 lesz. Ugye azt is kérdezhetnénk, hogy 2-t hányféleképp NEM választhatunk ki belőle (mert a másik 3-at igen), ami rögtön megmutatja a Pascal-háromszög szimmetriáját is. Az n és k szerepét is mutatja, ha k nagyobb, mint n (hogy tudunk 5 golyóból 8-at választani? 0-féle módon, mert nem lehet), akkor 0 lesz a megoldás - az ismétléses ebben lényegesen el fog térni.

Ismétléses kombináció. Ez a legnehezebb, erre a klasszikus példa a fagyizó, én is szeretem így elmagyarázni. Hányféleképpen választhatunk ki n elemből k darabot, ha választhatunk többször is ugyanabból. Elmegyünk fagyizni, van 4-féle fagyi (csoki, vanília, citrom, eper - a pisztácia épp elfogyott, de csoki van!). Szeretnénk 3 gombócot enni, de kérhetünk 3 vaníliát vagy 3 csokit is. A sorrendjük viszont nem számít (ellentétben a variációval), simán lehet, hogy egymás mellé teszik, aztán olyan sorrendben esszük, ahogy épp forgatjuk.

Itt szeretném felhívni a figyelmet, hogy a gombóc fagyi az kerek, mint a 0. A fagyizóban a rekeszek közti elválasztó meg egyenes, mint az 1. A csoki-vanília-citrom-eper meg egymás mellett van, ilyen sorrendben. Köztük 3 elválasztórekesz van, az pont elég a 4-féle fagyira.

Ha lenne egy matematikailag kényelmes ábrázolás, azzal meg tudnánk oldani ezt a feladatot. 3 gombócot szeretnénk enni, ez 000, és 3 elválasztó van, ez 111. 3 darab 0-ást és 3 darab 1-est tartalmazó 0-1 sorozat mondjuk a 000111, a 101010, a 001101 és társai (több van, majd megállapítjuk mindjárt, hogy mennyi). Azt állítom, hogy minden fagyiválasztáshoz pontosan egy ilyen sorozat van, és minden ilyen sorozat egy fagyiválasztást reprezentál. A 000111 azt jelenti, hogy az elsőből választok 3-at, aztán rekeszhatár-rekeszhatár-rekeszhatár van, szóval ez a 3 csoki lesz. A 001101 azt jelenti, hogy 2 csokit kérek, aztán rekeszhatárnál átugrok a vaníliára, de ebből nem kérek, újabb rekeszhatár, a citromnál tartok, itt van egy 0 (gombóc), szóval ebből kérek egyet, és újabb rekeszhatár (eper), aminél nincs gombóc, ebből nem kérek (2 csoki 1 eper a vége). A 101010 esetén ugyanilyen logikával nem kérek csokit, a többiből viszont 1-1 gombócot igen, vanília, citrom, eper lesz a vége. Látszik, hogy a 3 elválasztó (1-es) a 4 fagyifajtához és a 3 gombóc (0-ás) pont jó lesz.

Nézzük hány ilyen 0-1 sorozat létezik? 3 darab 0-ból és 3 darab 1-ből áll, szóval 6 hosszú. Ez a permutációk miatt 6! lenne, de így sok lehetőséget többször számoltunk. A 3 darab 0-ást 3!, a 3 darab 1-est is 3!-szor (összesen 6*6). Emiatt ezzel le kell osztani, 6!/(3!*3!) lesz a feladat megoldása. (ez lényegében az ismétléses permutáció)

Általánosságban n dologból választunk k darabot. Az n dologhoz n-1 darab elválasztó kell, n-1+k hosszú lesz a 0-1 sorozat, n-1 darab 1-essel, és k darab 0-ással. A megoldás (n-1+k)!/((n-1)!*k!) lesz. Az is látszik, hogy itt nem baj, ha több dolgot kérünk, mint a lehetőségek száma, mert kérhetünk ugyanabból többször.

Jórészt fejből írtam, de gondolom a kommentelők majd kijavítanak. Valószínűleg lesznek benne hibák.

#7: A ciklikus permutáció kb. triviálisan visszavezethető a simára.

Van n ember, az a kérdés, hogy egy kör alakú (ezért ciklikus) asztalhoz hány sorrendben ülhetnek le? A sorrendjük számít, de nincs senkinek kitűntetett szerepe.

Ugye a sima ism. nélküli permutációnál n! lenne, de ott számított a sorrend, és volt "eleje" a padnak, a kör alakú asztalnak meg nincsen.

Azt viszont megtehetjük, hogy van Béla, és van az n-1 haverja. Bélához viszonyítunk, neki lesz kitűntetett szerepe, az n-1 haverja meg (n-1)! sorrendben ülhet le mellé (az utolsó meg pont a másik oldalára).