Kombinatorika
Tudni szeretnéd, hányféleképpen választhatsz ki öt kártyát egy 32 lapos pakliból? Pontosan ilyen feladatokkal foglalkozik a kombinatorika. Két alapvető kombinatorikai szabály van – az összegszabály és a szorzatszabály. Az összes többi módszer csak ezeknek az alapelveknek a kiterjesztése.
A kombinatorikai összegszabály
Az összegszabály nagyon egyszerű. Azt mondja, hogy ha adott az A, B halmaz, amelyeknek nincs közös elemük, akkor az A ∪ B unióból egy elem kiválasztásának összes lehetséges módja |A| + |B|, vagyis a halmazok elemszámának összege.
Kezdjük egy könnyű példával. Van 6 piros és 8 kék golyónk. A golyókat egy urnába öntjük. Összesen hány lehetőségünk van, ha egy golyót húzunk ki? Az elején volt a piros golyók halmaza, ezt jelöljük A-val, majd a kék golyók halmaza, ezt jelöljük B-vel. Ez a két halmaz diszjunkt, vagyis nincs egyetlen közös golyójuk. Egy golyót akarunk kihúzni, ezért összesen |A| + |B| = 6 + 8 = 14 lehetőségünk van. Ennyi az egész.
A kombinatorikai szorzatszabály
Megint két halmazunk van, L és F. Az L halmaz három lányt, az F halmaz négy fiút tartalmaz. Most azt kérdezzük, hány különböző fiú–lány párt alkothatunk ezekből a halmazokból. Úgy járunk el, hogy mindig kiveszünk egy lányt, és hozzárendelünk egy fiút. A párok számát így számoljuk ki: vesszük az egyik lányt, Katit, és sorra hozzárendeljük az összes fiút. Így 4 különböző párt kapunk, mert mellé összesen 4 különböző fiút választhatunk. Ugyanezt megcsináljuk a másik két lánnyal is, ők is mindig újabb 4 párt adnak. És ennyi, összesen 4 + 4 + 4 = 12 párunk van.
Mit csináltunk valójában? Összeszoroztuk a két halmaz elemszámát. 3 lányunk és 4 fiúnk volt, a párok száma tehát 3 · 4 = 12. Innen a kombinatorikai szorzatszabály neve. Ha tehát van két halmazunk, amelyekből párokat alkotunk, egyszerűen összeszorozzuk az egyik halmaz elemszámát a másik halmaz elemszámával.
Az alábbiakban meg is nézheted, hogy ez valóban így van. Itt van az összes pár, amelyet 3 lányból és 4 fiúból alkothatunk. Minden sor az egyik lány lehetőségeit, minden oszlop az egyik fiú lehetőségeit mutatja. Három sorunk és négy oszlopunk van, összesen tehát sorok · oszlopok lehetőség.
Megoldott példák
- Hány különböző kétjegyű szám van? Hogyan néz ki egy ilyen kétjegyű szám? Az első helyen az 1, …, 9 számjegyek egyike áll, a második helyen viszont már a nulla is szerepelhet: 0, …, 9. Az első halmazban tehát 9 számjegyünk van, a másodikban 10. Alkalmazzuk a kombinatorikai szorzatszabályt, és megkapjuk a végeredményt: 9 · 10 = 90.
- Hány olyan háromjegyű szám van, amelyben egyik számjegy sem szerepel kétszer? Az első helyen megint kilenc számjegy állhat, nullával a szám nem kezdődhet. A második helyen az összes számjegy állhat, a nullát is beleértve, de nem állhat ott az, amelyik az első helyen van, ezért a tíz lehetséges számjegyből levonunk egyet (például ha a háromjegyű számunk éppen négyessel kezdődik, nyilvánvaló, hogy a második helyen már nem lehet négyes, mert akkor kétszer szerepelne a számban). A harmadik helyen megint az összes számjegy állhat, de nem állhat ott az, amelyik az első vagy a második helyen van. Az ok ugyanaz. Ha az első helyen a 4-es, a másodikon a 7-es számjegy áll, akkor a harmadik helyre a {0, …, 9} ∖ {4, 7} halmaz egy számjegyét írhatjuk. A tíz számjegyből ilyenkor kettőt kell levonnunk. Most már csak összeszorozzuk: 9 · 9 · 8 = 648. Összesen tehát 648 ilyen szám van.
- Kétszer egymás után feldobunk egy hagyományos dobókockát. Hány különböző eredményt kaphatunk? Az első dobásnál 6 különböző eredmény lehet. A másodiknál szintén, így a lehetőségek száma 6 · 6 = 36.
- Kétszer egymás után feldobunk egy dobókockát. Hány különböző eredményt kaphatunk, ha az első dobás páros szám lett? Az első dobásnál páros szám esett, vagyis a 2, 4, 6 számok egyike, ez összesen 3 lehetőség. A második dobásnál már bármelyik szám eshet, így összesen 3 · 6 = 18 lehetőségünk van.
Fejezetek: Kombinatorika, Variációk, Permutációk, Kombinációk, Ismétléses variációk, Ismétléses kombináció, Hányféle PIN-kód létezik?
