VI.Kombinatorika. Permutációk, variációk, kombinációk VI.1.Permutációk ismétlés nélkül és ismétléssel (sorrendi kérdések) Pl.1.) Az 1, 2, 3 számjegyekből, ismétlés nélkül, hány háromjegyű szám írható? 123 231 312 132 213 321 F. 6 db. van. A fenti példában előállítottuk 3 elem ismétlés nélküli permutációit: 3 elemet 3 helyre rendeztünk úgy, hogy egy elem csak egyszer szerepelhetett. A permutációk számának megállapítása: -a helyek sorszáma: I. II.
III.
↑ ↑ ↑ 3-ból 2-ből 1-ből választok választok „választok” Tehát a permutációk száma: 3·2·1 = P3 („permutáció 3 elemből”). Ugyanazt jelöli a 3! („3 faktoriális”) is. Pl.2.) Az ALOM szó betűiből hány négybetűs, nem föltétlenül értelmes szót lehet fölírni? (tegyük föl, hogy a betűk kártyákon állnak, tehát nem ismétlődhetnek.) ALOM ALMO AOLM AOML AMLO AMOL
L… L… L… L… L… L…
M… M… . . . M…
O… O… . . . O…
Látható, hogy négy oszlop van, mivel a 4 betűből bármelyik állhat az első helyen. Hogy a maradék 3 helyre a fennmaradó 3 betűt 6 féle módon lehet elhelyezni, azt már az előző feladatban láthattuk. Másképpen gondolkodva: I. II. III. IV. .. .. .. .. 4- 3- 2- 1ből ból ből ből választunk
P4 = 4 ⋅ 3 ⋅ 2 ⋅ 1 = 4!= 24 (db)
Tehát a felsorolt formák: 4 elem ismétlés nélküli permutációi (valójában a 24-ből csak 6ot soroltunk föl, a többi csak el van kezdve). Pl.3.) 1
Egy gyerek öt kedvenc könyvét (Benedek Elek, Móra Ferenc, Gárdonyi Géza, Kányádi Sándor, Lázár Ervin) cserélgeti egy könyvespolcon. Minden nap egyféle sorrendet alakít ki. Hány napig kell cserélgetnie, ha azt akarja, hogy minden sorrendet kialakítson? 5 hely – 5 könyv P5 = 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 5!= 120 F.120 napig tart, amíg az összes sorrendet ki tudja alakítani. Egy-egy sorrend 5 elemnek egy permutációja, ismétlés nélkül. Pl.4.) Az ALMA szó betűiből négybetűs szavakat alkotunk. Hányat lehet? Fel lehet írni mind a 24-et, de közülük 12-t ki kell húzni: ennyi esetben kapunk olyant, amit már előzőleg megkaptunk. Így gondolkodhatunk: Vesszük úgy, mintha mind a 4 betű különböző lenne, de az így kapható számot osztani kell 2!-sal, jelen esetben 2-vel. Ha rögzítjük két nem ismétlődő betű pozícióját: ALMA, minden esetben pontosan feleannyi felírás van, mert A-t A-val felcserélve nem kapunk új felírásokat. Egészen pontosan: annyiszor kevesebb permutáció van, ahányszor az ismétlődő betűk a fennmaradt helyekre elhelyezhetők lennének, ha azok különbözők volnának. Amit így felírtunk 4 elem permutációi (4 elemet 4 helyre rendeztünk), amelyek közül kettő ismétlődött. 4! 24 Jele: P42,1,1 = P42 = = = 12 2! 2 Pl.5.) Adottak a következő számkártyák: 1 2 3 3 3 . Hány ötjegyű szám alkotható ezekből? Itt az 1 2 kártyák minden rögzített pozíciója esetén hatszor kevesebb eset van ( P3 = 6 ). 5! 120 Tehát P53,1,1 = = = 20 . 3! 6 Pl.6.) Az 1, 2 számjegyekből hány olyan ötjegyű szám írható föl, amelyben az 1-es háromszor, a 2-es pedig kétszer szerepel? 5! 120 P53, 2 = = = 10 3!⋅2! (3 ⋅ 2 ⋅ 1) ⋅ (2 ⋅ 1) A fenti példák alapján foglaljuk össze: -n elem nem ismétléses permutációja azt jelenti, hogy n db különböző elemből választunk n helyre. Ezek száma: Pn = n!= n ⋅ (n − 1) ⋅ (n − 2) ⋅ ... ⋅ 2 ⋅ 1
2
Pn : n elem permutációinak száma, vagy n! „n faktoriális” – mindkettő ugyanazt a dolgot jelöli. -Az ismétléses permutációnál is n elem van, és n hely van, de az elemek közül rendre k1 db egyforma, k 2 db egyforma, ... , k n db egyforma, tehát k1 + k 2 + ... + k n = n . n! k , k ,..., k A permutációk száma: Pn 2 n1 = k1!⋅k 2 !⋅... ⋅ k n ! Pl.7.) a.)A TERELTE szó betűit hányféle módon lehet egymás mellé helyezni? b.)Hát az ÉDESAPU szó esetében? a.) TERELTE T = 2 db ⎫ E = 3 db ⎪⎪ 7! 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅1 3, 2 ,1,1 = = = 420 (db) ⎬n = 7 ⇒ P7 R = 1 db ⎪ 3!⋅2!⋅1!⋅1! (3 ⋅ 2 ⋅ 1) ⋅ (2 ⋅ 1) ⋅ 1 ⋅ 1 L = 1 db ⎪⎭ b.)Nincs ismétlődés ⇒ P7 = 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 5040 (db) VI.2.Variációk ismétlődés nélkül és ismétlődéssel (kiválasztási és sorrendi kérdések) Pl.1.) Van négy számkártya: 2 3 4 5 . Hány háromjegyű szám rakható ki ezekből? ☺ ☺ ☺ ↑ ↑ ↑ 4-ből 3-ból 2-ből Választunk 234 243 324 342 423 432 6 db
235 . . . . . 6 db
4·3·2 = 24 (db) 245 . . . . . 6 db
345 . . . . . 6 db
Amit felírtunk 4 elem 3-ad osztályú variációi, ismétlés nélkül. (4 elemből 3 helyre választottunk, ismétlődés nélkül) Jele: V43 = 4 ⋅ 3 ⋅ 2 = 24(db) Tehát n különböző elem k-ad osztályú variációi: n elemből választunk k helyre és minden elem csak egyszer szerepelhet.
3
k (n − 1) ⋅ (n − 2) ⋅ ... ⋅ (n − k + 1) A variációk száma: Vn = n1⋅ 4 44442444443 k db szorzótényezö
Az előbbi képletből levezethető: Vnk =
n! ( n − k )!
Pl.2.) A 2, 3, 4, 5 számjegyek felhasználásával hány háromjegyű szám írható fel? (a számjegyek ismétlődhetnek). ☺ ☺ ☺ 4-ből 4-ből 4-ből Tehát ismétléssel 4 elemből választunk 3 helyre. választok V43,i = 4 ⋅ 4 ⋅ 4 = 4 3 = 64(db) Itt 4 elem ismétléses variációiról van szó. Az ismétléses variációnál n elemből választunk k helyre, de a kiválasztott elemek megint szerepelhetnek. Vnk ,i = n k Pl.3.) Egy nyuszika egy öt fokozatú lépcső tetején áll. Ugrándozik lefelé úgy, hogy bármelyik lépcsőfokra ráugorhat, vagy át is ugorhatja. Hányféle ugráskombinációt próbálhat ki, amíg a földre ér? Minden lépcsőfoknál 2 lehetőség közül Választhat: vagy ráugrik, vagy nem. Tehát 2 lehetőségből választ 4 helyre: V24,i = 2 4 = 16 , vagy: I. II. III. IV. (lépcsőfok) 2· 2· 2· 2 Pl.4.) Dobókockával dobunk egymás után négyszer és az eredményeket (a dobások számjegyét) egymás mellé írjuk. Így minden négy dobás után egy-egy négyjegyű számot kapunk. Hány esetben lesz a kapott négyjegyű szám 4-gyel osztható? A 4-gyel való oszthatóság szabálya alapján a jó végződések: 12, 16, 24, 32, 36, 44, 52, 56, 64. Tehát 9 db jó végződés van. I . II . III . IV . Az első két hely esetén 6-ból választunk: V62 ,i = 6 2 = 36 . 1424 3 14243 ide választunk a 6 −ból
fix: 9 jó végzödés
Tehát Ö = 9·36 = 324 jó szám van. Pl.5. Adott a következő elrendezés. Hányféle képpen olvasható ki belőle a MATEK szó, ha csak jobbra vagy lefele léphetünk?
4
MATEK ATEK TEK EK K
4 lépés van M-től K-ig. Minden esetben kétféle lehetőség van. Tehát V24,i = 2 4 = 16 .
-Másképpen megoldva: Indexeljük a betűket azzal a számmal, amely azt mutatja, hogy az illető betűhöz hányféle módon juthatunk. M 1 A1 T1 E1 K1 Bármelyik K-hoz jutunk, az mind jó, tehát a K betűk indexeit összeadjuk A1 T2 E3 K 4 Ö = 1 + 4 + 6 + 4 + 1 = 16 T1 E3 K 6 E1 K 4 K1 Pl.6.) Adott a mellékelt elrendezés. Hányféleképpen olvasható ki A VIZSGA szó, ha csak jobbra vagy lefelé lehet haladni?
VIZS IZSG ZSGA
A V-től az A-ig haladva 5 lépéslehetőség. Ebből az elrendezést figyelve 3 történhet 5! jobbra és 2 lefelé. Tehát a lépések száma: P53, 2 = = 10 3!⋅2! -A feladat ugyanaz, mintha a j, j, j, l, l betűket rendezném 5 helyre (jobbra 3×, lefelé 2×), tehát valóban P53, 2 -ről van szó. -Másképpen megoldva: indexeljük a betűket azzal a számmal, amely azt mutatja, hogy az illető betűhöz hányféle módon juthatunk. Az utolsó betű (A) indexe megadja az összlehetőségek számát: V1 I 1 Z1 S1 I 1 Z 2 S 3 G4 Z 1 S 3 G6 A10 Látható, hogy az eredmény így is 10. VI.3.Kombinációk ismétlés nélkül és ismétléssel (kiválasztási kérdések) A feladat: n elemből k elemet tartalmazó részhalmazokat alkotni. Másképpen: n elemből válasszunk ki k darabot úgy, hogy a kiválasztott elemek sorrendje nem számít. Bármelyik megfogalmazást tekintjük, n elem k-ad osztályú ismétlés nélküli kombinációiról van szó. 5
⎛n⎞ Jelölés: C nk , vagy ⎜⎜ ⎟⎟ . ⎝k ⎠ Megjegyzés Az első megfogalmazásban azért nem kell hangsúlyozni, hogy nem fontos a sorrend, mert maga a halmaz fogalma tartalmazza azt, hogy az elemek sorrendjétől el lehet tekinteni. Pl.1.) A {2, 3, 4, 5} halmaznak hány 3 elemes részhalmaza van? F. 4 db, éspedig: {2, 3, 4}; {2,. 3, 5}; {2, 4, 5}; {3, 4, 5}. Megjegyzés A variációk 1.)-es feladatánál ugyanezekből a számjegyekből alkottunk ismétlődés nélkül háromjegyű számokat. Ahhoz viszonyítva most 6× kevesebb eset van. Miért? -Az egyszer kiválasztott 3 számot itt nem kell átrendezni más sorrendbe, mint a variációknál, tehát annyiszor kevesebb eset van. Ez annyi, mint ahányszor a 3 elemet a megadott 3 sorrendbe tudtuk volna helyezni, vagyis P3 -szor kevesebb eset van. Amit fölírtunk 4 elemnek 3-ad osztályú ismétlés nélküli kombinációi. V43 4 ⋅ 3 ⋅ 2 3 C4 = = = 4 eset van. P3 3 ⋅ 2 ⋅1 Vnk n! = Általában a nem ismétléses kombináció képlete: C = Pk k!⋅(n − k )! Pl.2.) Osszunk szét 5 tanuló között 3 egyforma ajándékot úgy, hogy minden gyerek csak 1-1 ajándékot kaphat. Hányféle módon lehet? k n
Most a tanulókból választunk az ajándékokhoz. Mivel az ajándékok egyformák, a kiválasztott 3 tanuló között nem kell cserélgetni az ajándékokat, tehát nem variációról, hanem kombinációról van szó. V 3 5⋅4⋅3 C 53 = 5 = = 10 P3 3 ⋅ 2 ⋅ 1 Pl.3.) Ugyanaz a feladat, de egy tanuló több ajándékot is kaphat. Megoldás: V53 5 ⋅ 4 ⋅ 3 -Kaphatnak a tanulók 1-1 ajándékot (mint az előbb), ezek száma: C = = = 10 P3 3 ⋅ 2 ⋅ 1 -Kaphat egy tanuló 2 ajándékot és egy tanuló 1-et. Így az 5 tanulóból 2-t választunk. Az így kapott számot megduplázzuk, mert az első kaphat kettőt és a második egyet, vagy fordítva. 5⋅4 2 ⋅ C 52 = 2 ⋅ = 20 2 ⋅1 -Kaphat egy tanuló 3 ajándékot -5 féle képpen. Tehát összesen 10 + 20 + 5 = 35 eset van. 3 5
6
Amit felírtunk ebben a 3. példában az 5 elem 3-ad osztályú ismétléses kombinációi voltak. 7 ⋅6⋅5 Megfigyelhető, hogy 35 = C 53+ 3−1 = C 73 = = 35 3 ⋅ 2 ⋅1 Így az ismétléses kombináció képletét alkalmaztuk, vagyis: C nk ,i = C nk+ k −1 . Tehát az ismétléses kombinációk számának kiszámítása visszavezetődik a nem ismétléses kombináció képletére. Tehát n elem k-ad osztályú ismétléses kombinációja azt jelenti, hogy az n db elemből k darabot úgy választunk, hogy bármelyik elem többször is előfordul. Pl.4.) Egy urnában 20 cédula van 1-20-ig megszámozva. Kihúzunk 5 cédulát úgy, hogy minden húzás után a kihúzott cédulát visszatesszük. Hány esetben lesz a kihúzott legkisebb szám nagyobb hatnál? 14 db olyan cédula van, amelyen hatnál nagyobb számok vannak. Tehát 14 elemből kell 5-ös sorozatokat alkotni, ahol a sorrend nem számít, vagyis kombinációról van szó. Mivel minden húzás után visszatevődik a már kihúzott cédula, ezért ismétléses a kombináció. A válasz tehát: C145,i = C145 + 5−1 = C185 = 8568 . Pl.5.) Hány átlója van egy szabályos 12 oldalú sokszögnek? A 12 db hármanként nem kollineáris pontból 2-2-t választva „meghúzzuk” az összes lehetséges egyenest. Ezek között a sokszög oldalai is ott lesznek, tehát ezeket levonjuk. Azért van szó kombinációról, mert a két kiválasztott pont sorrendje nem számít (nem számít, hogy „oda, vagy vissza húzzuk” az egyenest). V 2 12 ⋅ 11 C122 = 12 = = 66 66 – 12 = 54 (db átló) P2 2 Pl.6.) Egy polcon 15 üveg bor van: 10 fehér és 5 vörös. Hányféle módon lehet kiválasztani ezek közül 6 üveggel, hogy közötte 2 üveg vörös bor legyen? 5⋅4 10 ⋅ 9 ⋅ 8 ⋅ 7 = 10 (vörös bor ) C104 = = 210 ( fehér bor ) 2 ⋅1 4 ⋅ 3 ⋅ 2 ⋅1 Tehát C 52 ⋅ C104 = 210 ⋅ 10 = 2100 féleképpen. Pl.7.) Egy 32-es létszámú osztályban létre kell hozni egy 5 tagú bizottságot, amelyben legyen 1 titkár, a másik 4 csak tag. Hány olyan eset van, amikor Kovács Éva: a.) titkára a bizottságnak? b.) nem titkár, de tag a bizottságban? c.) szerepel a bizottságban? C 52 =
7
a.)Ha Kovács Éva a titkár, akkor a maradék 31 tanulóból választunk 4 helyre: 31 ⋅ 30 ⋅ 29 ⋅ 28 C 314 = = 31 465 . 4 ⋅ 3 ⋅ 2 ⋅1 b.)Valaki titkár lesz, Kovács Éva tag. A titkár helyére 31 féle választás van. A 3 tag helyére C 303 (3 helyre választunk, mert a titkárt már kiválasztottuk és Kovács Éva is elfoglalt egy helyet.) 30 ⋅ 29 ⋅ 28 Tehát Ö = 31· C 303 = 31 ⋅ = 31 ⋅ 5 ⋅ 29 ⋅ 28 = 125 860 . 3 ⋅ 2 ⋅1 c.)Az előző kettőből következik, hogy C 314 + 31· C 303 = 157 325.
8
