Diszkrét matematika KOMBINATORIKA KOMBINATORIKA

Diszkrét matematika

PPKE ITK KOMBINATORIKA

KOMBINATORIKA A kombinatorika véges elemszámú halmazokat vizsgál. A fő kérdések: a halmaz elemeit hányféleképpen lehet sorbarendezni, kiválasztani közülük néhányat vagy akár mindet bizonyos feltételek mellett, stb. Ezért a kombinatorika alapját képező részt angol nyelvterületen összeszámlálási problémáknak nevezik. Nagyon gyakran alkalmazható két egyszerű szabály: az összeadási- és a szorzási szabályok. Az összeadási szabályt először két egyszerű példán keresztül világítjuk meg. Példa: 1. Egy hallgatónak az órarendjében 2 lyukas óra van. Ezért elhatározza, hogy még felvesz egy tárgyat. Az adott időpontban a kötelező szakmai tárgyak között csak kettő van, amit fel tud venni, a nem szakmai, választható tárgyak között pedig három. Hányféleképpen dönthet? A válasz elég egyszerű: a lehetséges kötelező szakmai tárgyak száma + a lehetséges nem szakmai, választható tárgyak száma, jelen esetben 5. 2. Diszkrét matematikából az évfolyam zárthelyit az első emeleti 134, a második emeleti 219, 239 és a harmadik emeleti 318, 319, 320 termekben írják. Sajnos, egy hallgató elfelejtette, hova kell mennie, és mivel elkésett, már nem is tudja ,megkérdezni senkitől sem. Hányféleképpen dönthet? A lehetőségek száma nyilvánvalóan az első emeleti., második emeleti és harmadik emeleti termek számának összege. Egyszerűen megfogalmazva az összeadási szabályt, ha x-féleképpen végezhetünk el egy dolgot, és y-féleképpen egy másik dolgot, és csak egyetlen egyet csinálhatunk, akkor ezt az egyetlen dolgot x+y féleképpen tehetjük meg. Az összeadási szabály valójában a halmazelméleti szita formula egy speciális esete, amikor páronként diszjunkt (közös elemeteket nem tartalmazó) halmazok únióját vesszük. A halmazelméleti szita (nem diszjunkt halmazokra vonatkozó) formula: Ha A1, ..., An véges elemszámú halmazok, akkor

r

© Bércesné Novák Ágnes



Összeadási szabály: Egymást kölcsönösen kizáró lehetőségeknek a száma az összes a lehetőségek számának összegével egyenlő. Másképpen: egymást kizáró halmazok uniójának elemszáma a halmazok elemszámának összege. A1A2A3…Ak= A1A2A3…Ak Szorzási szabály: Ha egy feladatot 2 olyan részfeladatra lehet bontani, hogy először az egyik, majd tőle függetlenül a másik feladat elvégezhető, akkor ha az első x-féleképpen, a második y-féleképpen hajtható végre, akkor az egész feladat x*y féleképpen hajtható végre. Halmazokkal fogalmazva, ha két halmazból kell egymástól függetlenül választanunk, melyeknek számossága x és y, akkor az összes választási lehetőség x.yPélda: A menzán 2-féle leves és mellé 4-féle főétel közül lehet választani. Hányféle menü állítható össze? Levesek→ Főételek 

Húsleves

Gyümölcs leves

Rántott hús krumplival Túrós tészta Sólet Rakott káposzta

1 3 5 7

2 4 6 8

Megoldás: 2*4 = 8, tehát 8-féle menü állítható össze. Ez a kék dupla szegélyű téglalap területe. Szorzási szabály általánosítása: Ha egy feladatot k db olyan részfeladatra lehet bontani, hogy minden részfeladat a többitől függetlenül elvégezhető, és ezek mindegyike x1, x2, x3, … xk - féleképpen hajtható végre, akkor az egész feladatot x1*x2* x3 *…* xk –féleképpen lehet megoldani. Feladatok: - A menüben nemcsak leves és főétel, de desszert és ital is szerepelhet. Hányféle menü állítható össze, ha ötfajta ital és háromfajta desszert választható? - Fogalmazza meg a szorzási szabály általánosítását halmazokkal! - Hány három sávos zászló készíthető 6 színből? - Hány három színű zászló készíthető 6 színből? Az összeszámlálási problémák egy része típusokba sorolható, s ezen típusfeladatok általánosan megoldhatók. A szokásos típus feladatok: -

Permutáció: n különböző elemnek hányféle sorbarendezése lehetséges? Kombináció: n elemből hányféleképpen választható ki k elem, ha a sorrend nem számít? Variáció: n elemből hányféleképpen választható ki k elem, ha a sorrend nem számít?




Az alábbiakban ismertetjük ezen típusfeladatok megoldásait, kitérve az ún. ismétléses esetekre is. Az egyik legegyszerűbb tehát feladat n különböző személy, tárgy sorrendbe rendezése. Magát a sorrendet, de az eljárást is, (ismétlés nélküli) permutációnak nevezzük. Példa: Az a,b,c, d elemek két különböző permutációja: a b c d és b a c d A kérdés az, hogy n különböző elemnek hány permutációja van? Jelölés: A permutációk számát jelöljük P-vel és az alsó indexbe írjuk, hogy hány elemet akarunk sorbarendezni: Pn. Egy elemnek nyilván 1, kettőnek: a, b és b, a, vagyis kettő permutációja van: P1=1, P2= 2 A továbbiak miatt ezen utóbbit célszerű úgy felfogni, hogy az első helyre választott elem vagy a, vagy b. A maradék helyre pedig egy-egy elem választható, ezeket az A és a B halmazokba (a kezdő elem neve szerint) csoportosítottuk: A ab

B ba

E két halmaz elemei a permutációk (nem az a, és b elemek!), ezért e két halmaz diszjunkt, hiszen az ab és a ba sorrendek nem egyenlők. Így az összeadási szabály alkalmazható: 1 + 1=2  1=2, tehát 2 az összes két elemű permutációk száma. Három elem összes permutációja az A, B , C halmazokba csoportosítva (a kezdő elem neve szerint): A B C abc bac cab acb bca cba Ha az első helyre az a elemet választjuk, akkor ehhez a maradék két elem kétféleképpen írható fel. Ha az első helyre a b elemet választjuk, akkor ehhez a maradék két elem kétféleképpen írható fel. Ha az első helyre a c elemet választjuk, akkor ehhez a maradék két elem kétféleképpen írható fel. Az összeadási szabály alkalmazható az A, B, C halmazokra (elemeik különbözők, hiszen mindegyik sorrend más és más). Ez tehát összesen 2 + 2 + 2 = 3  2=3  2  1=6 © Bércesné Novák Ágnes



Ha négy elem van, akkor az első helyre 4-ből választhatunk, a maradék három helyet viszont az előzőek értelmében hatféleképpen tudjuk kitölteni, s mivel mindegyik négyes különböző, a keletkező A, B, C, D halmazok diszjunktak, ezért ismét alkalmazható az összeadási szabály, csakhogy most mindegyik halmazban 6 elem van: P4=6+6+6+6=4  6=4  3  2  1=24 A abcd abdc acbd acdb adbc adcb

B bacd badc bcad bcda bdac bdca

C cabd cadb cbad cbda cdab cdba

D dabc dacb dbac dbca dcab dcba

Ezen tapasztalatok alapján általánosan az sejthető, hogy n különböző elem összes lehetséges sorrendjeinek száma 1  2  3  4…n, vagyis a számok szorzata 1-től n-ig. Fent k=1,2,3,4 esetekre bizonyítottuk. Tegyük fel, hogy Pn = 1  2  3….n. Ezt felhasználva kell azt bizonyítani a teljes indukció módszere szerint, hogy Pn+1= (n+1)!. Úgy tudunk Pn+1-re következtetni, hogy az új elemet hozzávéve, n+1 db csoportot alkothatunk, amelyek mindegyikében különböző elemek vannak (hiszen mindegyik sorrend más és más), és elemszámuk egyenlő, Pn. Ennek oka, ugyanúgy mint a 4 elemnél, hogy egy elemet elsőnek kiválasztva a maradék n elem Pn – féleképpen írható utána. Az első elemet pedig (n+1)féleképpen választhatjuk. Ezért az első elem szerint csoportosítva az egyes halmazok elemszámainak összege adja az n elem összes lehetséges permutációinak számát: Pn+1= Pn + Pn + Pn +…+ Pn =(n+1) Pn=(n+1)  n  (n-1)…3  2  1=(n+1)! Ezzel bebizonyítottuk a következő tételt. Tétel: n különböző elem permutációinak száma Pn = 1.2.3….n=n! Jelölés: A tétel megfogalmazásában bevezettünk egy új jelölést: 1.2.3…. n=n!, olvasd: n faktoriális. Előfordulhat, hogy a sorbarendezendő elemek között egyformák is vannak, pl.: a a b c. Ez az eset az ún. ismétléses permutáció, mivel ha csak egy sorrendet látunk, az tűnik fel, hogy abban egy vagy több adott elem ismétlődik. Ezt úgy kell értelmeznünk, hogy akkor az alaphalmaz pontosan annyi egyforma elemet tartalmaz, ahányszor ismétlődnek az elemek. Például, ha az aabcccddddd sorrendet tekintjük, akkor az a elemből 2 db, a b elemből 1 db., a c elemből 3 db., a d elemből pedig 5 db. van. Definíció: Ha n elem közül azonos, akkor ezek különböző sorrendjeit ismétléses k permutációnak nevezzük. Jelölése: Pn




Ekkor, ha egymás közt felcseréljük az egyforma elemeket, nem kapunk új sorrendet. A lehetséges különböző sorrendek száma így kevesebb, mintha ugyanannyi, de egymástól különböző elemet raknánk sorba. Az összeszámlálás miatt ideiglenesen különböztessük meg a két egyforma elemet: a1 a2 b c. Az a2 a1 b c eszerint ugyanaz a permutáció. Így azonban könnyebben össze tudjuk számlálni a különböző sorrendeket. Ha csak két eleme egyenlő, akkor nyilvánvaló, hogy minden ismétléses permutációból az elemek indexelésével két ismétlés nélküli permutáció származtatható. Ha az ismétléses permutációk számát x-szel jelöljük, akkor 2  x= Pn, vagyis x = Pn/2. Ha nem két, hanem k db. egyenlő elem van, akkor bármely permutációban az egyforma elemeket k!- féleképpen permutálhatjuk egymás közt, más szavakkal, ha indexeléssel megkülönböztetjük az egyforma elemeket, egy adott permutációból k! ismétlés nélküli permutációt képezhetünk. Mivel ez minden egyes permutációnál ugyanaz a szám, ezért ezeket összeadva és az ismétléses permutációk ismeretlen számát ismét x-szel jelölve: k!  x= Pn, vagyis x= Pn/k! . Hasonlóképpen bizonyítható az általános eset, ha n! k , k , ...k Pn 1 2 j  k1! k!...k j!

azonos elem van, akkor

n! k , k , ...k , ahol Pn 1 2 j n elem, melyek közül k1! k!...k j! ismétléses permutációját jelenti. k , k 2 , ...k j

Tétel: Pn 1



Példa: A hallgató szó betűiből P82,2 

azonos,

8! 1 2  3  4  5  6  7  8   1080 különböző ismétléses 2! 2! 22

permutáció készíthető. A következő típusfeladat legyen az ún. kombináció. Definíció: n különböző elem k-adosztályú kombinációja az n elem közül kiválasztott k elem, tekintet nélkül azok kiválasztási sorrendjére. Ezek összes számát Cnk -val jelöljük. Példa: Az a, b, c, d elemek összes harmadosztályú variációja: a b c, a b d, b c d, a c d. Az a, b, c, d elemek összes másodosztályú variációja: a b, a c, a d, b c, b d, c d. Praktikus a k db kiválasztott elemet valamilyen természetes rendezés (ábécé, növekvő) sorrendben szerint leírni. Definíció: n különböző elem k-adosztályú kombinációja az n elem közül kiválasztott k elem, tekintet nélkül azok kiválasztási sorrendjére. Ezek összes számát Cnk -val jelöljük. © Bércesné Novák Ágnes



Tétel: n különböző elem k-adosztályú kombinációinak száma:  n n! Cnk     . Olvasd: „n alatt a k”. k!(n  k )!  k  Bizonyítás: Képzeljük el, hogy az n elemet egy sorban felírjuk valamely természetes sorrendben. Ezután az elemek alá írunk k db „I” betűt (melynek jelentése: IGEN. a felettem levő elem ki van választva!), és (n-k) db „N” betűt (NEM, a felettem lévő elemet nincs kiválasztva). Például: 7 elemből válasszunk ki három elemet ezen a módon: abcdefg I I NN INN Vagyis, a b és e van kiválasztva. Ha leírjuk, hogy NNININI, akkor tudjuk, hogy c e és g van kiválasztva. Tehát csak össze kell számolni, hányféleképpen írhatjuk fel a k db. „I” betűt és a és (n-k) db „N” betűt. Ez pedig nem más, mint n különböző elem, melyek között k és (n-k) egyforma van, n! ismétléses permutációja: Pnk,n - k  . k!(n  k )! Példa: A hagyományos ötös lottóban 90 számból kell ötöt kiválasztani, így a fenti tétel  n   90  alkalmazásával ez      -féleképpen lehetséges. k   5  Feladat: Hányféleképpen lehet kitölteni a hatos lottót, ahol 45 számból kell hatot választani? Az ötös és a hatos lottó közül melyiket lehet többféleképpen kitölteni? A kombináció ismétléses, ha egy elemet többször is választhatunk. Példa: az a,b,c,d elemek másodosztályú ismétléses kombinációi: a b, a c, a d, b c, b d, c d, a a, b b, c c, d d. Tétel: n különböző elem k-adosztályú ismétléses kombinációinak száma:  n  k  1  . Cnk,i    k  Bizonyítás: Az egy sorba felírt elemek sorszámát tudjuk. Az első helyen álló elemet kiválaszthatjuk vagy egyszer, vagy kétszer, vagy k-szor. Ennek megfelelően írjunk annyi „I” betűt, ahányszor kiválasztjuk az első pozíción álló elemet. Ezután írjunk egy elválasztójelet, pl. *-ot, és folytassuk a többi elemre is eszerint. Például az a,b,c,d elemek másodosztályú ismétléses kombinációinak leírása: a b, a c, a d, b c, b d, c d, a a, b b, c c, d d. I*I**, I**I*, I***I, *I*I*, *I**I, **I*I, II*** , *II**, **II*, ***II. Összesen n-1 db egyforma elválasztójelet kell írni, és összesen k db „I”-t. Ezek minden lehetséges sorrendje megadja az összes kiválasztási lehetőséget. Ezért ezek összes lehetséges sorrendje: Pnk, kn -11 

(n  k  1)!  n  k  1    k!(n  1)!  k 




Példa: 15 fajta fagyiból hányfajta 4 gombócos fagyit választhatunk, ha a gombcok egyformák is lehetnek, és nem számít, milyen sorrendben kerülnek a tölcsérbe. Megoldás: 15  4  1  C154,i   4   Végül tekintsük át a variációt. Definíció: n különböző elem k-adosztályú variációján az n elemből kiválasztott k elem egy sorrendjét értjük. Ezek összes számát Vnk -val jelöljük. Példa: Az a,b,c elemek másodosztályú variációi: a b, b a, a c, c a, b c, c a. Tétel: n különböző elem k-adosztályú variációinak száma: n! Vnk  n  (n  1)  (n  2)  ...  (n  (k  1))  k! Bizonyítás: A fenti példában egy sorba írtuk az elemek másodosztályú kombinációjának megfelelő variációkat, ti. ugyanazokat az elemeket választottuk ki, és felírtuk a lehetséges sorrendjeiket, ami ez esetben 2 volt. Ezt azonban bármely k esetén meg lehet tenni: a k-adosztályú kombinációkból úgy kapjuk meg a k-adosztáyú variációkat, hogy a kiválasztott k elem összes sorrendjét veszük, ez k!. Mivel összesen Cnk db kombináció van, és az ezek által meghatározott permutációk mindegyike k!, ezért e halmazok számosságát összeadva: n! n! Cnk  k!  k!  n  (n  1)  (n  2)  ...  (n  (k  1)) k!(n  k )! (n  k )! Példa: A tombolán 100 szelvényt adtak el, és 10 nyeremény van. Hányféleképpen húzhatják ki a nyertes szelvényeket, ha mindenm szelvényt csak egyszer húzhatunk ki? Megoldás: 100  99  98  97  96  95  94  93  92  91. Feladat: Mi a kapcsolat Vnn és Pn között? Lehetséges olyan tombola is, amikor az egyes húzások után visszateszik a kihúzott szelvényt, vagyis egy szelvényt többször is kisorsolhatnak. Ebben az esetben ismétléses variációról beszélünk. Definíció: A variáció ismétléses, ha egy elemet többször is választhatunk. Jelölése: Vnk,i Példa: Az a,b,c elemek másodosztályú ismétléses variációi: a b, b a, a c, c a, b c, c a, aa, bb, cc.




Tétel: n különböző elem k-adosztályú ismétléses variációinak száma: Vnk,i  n  n  n  ...  n  nk Bizonyítás: A k választást képzeljük el k halmazból, melyeknek ugyanazok az elemei, s melyekből egy-egy elemet kell választani. A szorzási tétel alkalmazásával ez valóban nk. Példa: A totó játéknál meg kell tippelni, hogy két focicsapat közül melyik nyer. A két mérkőző csapat adott sorrendben szerepel, így 1.,2. vagy x jelet kell tenni az adott mérkőzéshez, melynek jelentése: - 1: az elsőnek felsorolt csapat nyer - 2: a másodiknak felsorolt csapat nyer - x: döntetlen lezs az eredmény Általában 13+1 mérkőzést sorolnak fel. Hányféleképpen tölthető ki a totószelvény? Megoldás: Mivel a mérkőzések egymástól függetlenek, mindig e 3 elemű halmazból kell választani, tehát a kitöltések száma: 314. Feladatok: - egy halmaznak hány részhalmaza van? - hányféleképpen lehet egy buszjegyet kilyukasztani?


Diszkrét matematika KOMBINATORIKA KOMBINATORIKA

Recommend Documents