2013.02.02.
COEDU // NYOMTATÁS
//
KURZUS: Matematika II. MODUL: Valószínűség-számítás
16. lecke: Kombinatorika (alapfeladatok)
Tananyag: Kiss Béla - Krebsz Anna: Lineáris algebra, többváltozós függvények, valószínűségszámítás, 3.1. fejezet
Elméleti összefoglaló n elem különböző sorrendjeinek (az n elem permutációinak) a száma: P n =n!=n⋅( n−1 )⋅...⋅2⋅1 . Ha az n elem között k 1, k 2, ..., k l ( k 1 + k 2 +...+ k l =n ) darab egyező van, akkor az n elem ismétléses permutációinak száma: P n k 1 , k 2 ,..., k l = n! k 1 !⋅ k 2 !⋅...⋅ k l ! n különböző elemből k különböző kiválasztunk ( k≤n ) úgy, hogy az elemek sorrendje számít, az így keletkező variációk száma: V n,k =n⋅( n−1 )⋅...⋅( n−k+1 )= n! ( n−k )! . Ha egy elem többször is szerepelhet, akkor az ismétléses variációk száma: V n,k ism = n k Ha n különböző elemből k darabot kiválasztunk ( k≤n ) úgy, hogy az elemek sorrendje nem számít, a keletkező kombinációk száma: C n,k = V n,k P k = n⋅( n−1 )⋅...⋅( n−k+1 ) k! = n! k!⋅( n−k )! =( n k ) , 0!=1 . Ha a kiválasztott elem ismétlődhet, akkor a felírható ismétléses kombinációk száma: C n,k ism =( n+k−1 k )
Kidolgozott feladatok 16.1. Hányféleképpen alakulhat a végső sorrend a 16 csapatos labdarúgó bajnokságban? Megoldás: 16 különböző elem (csapat) sorrendjének száma: 16!=16⋅15⋅...⋅2⋅1≈2,09⋅ 10 13 16.2. A fenti bajnokságban az utolsó kettő kiesik. Hányféle lehet a sorrend, ha az egyik kieső a Botláb FC? Megoldás: Ha a Botláb FC utolsó, akkor a csapatok 15!-féleképpen végezhetnek előtte. Ha a Botláb FC utolsó előtti, ekkor a többi csapatot megint csak 15!-féleképpen rakhatjuk sorba. Vagyis a lehetséges sorrendek száma: 15!+15!≈2,61⋅ 10 12 16.3. A 100 méteres gyorsúszás döntőjébe 3 egyesült államokbeli, 2 ausztrál, 1 orosz, 1 holland és 1 magyar versenyző került. Hányféle lehet a végső sorrend a nemzetek szempontjából, ha coedu.sze.hu/print.php4?print_items=
1/7
2013.02.02.
COEDU // NYOMTATÁS
a)
a magyar úszó győzött?
b)
a végén az amerikai himnuszt játszották?
Megoldás: A kérdés a sorrend a nemzetek szempontjából, tehát az egy nemzetbeli versenyzőket nem tekintjük megkülönböztethetőnek. (Pl., ha az élen 2 amerikai végzett, akkor nekünk mindegy, hogy ki az első és ki a második.) a) Ha a magyar győzött, akkor a többiek a maradék hét helyen osztoznak. Így a lehetséges sorrendek száma a nemzetek szempontjából: P 7 3,2,1,1 = 7! 3!⋅2!⋅1!⋅1! =420 . b) Ha valamelyik amerikai győzött, akkor a maradék hét helyre: P 7 2,2,1,1,1 = 7! 2!⋅2!⋅1!⋅1!⋅1! =1260 . (Ha John Smith 1. és Joe Taylor 4. lett, akkor ez a nemzetek szempontjából ugyanaz, mintha fordítva történt volna.) 16.4. Hányféleképpen alakulhatott ki a legendás 6:3 végeredmény (pl. hat magyar gól után 3 angol gól, vagy 2 magyar után egy angol és így tovább, stb.)? Megoldás: A meccsen 9 gól született (6 magyar és 3 angol) ezek lehetséges sorrendjeinek számát kell meghatározni (ismétléses permutáció) P 9 6,3 = 9! 6!⋅3! =84 16.5. Közép-Languszta királya végre zászlót szeretett volna adni népének. Tanácsadóira hallgatva háromsávos, különböző színekből álló lobogót választott. Hányféleképpen tehette ezt meg, ha a rendelkezésre álló színek a következők voltak: piros, kék, sárga, zöld, fehér, fekete? Megoldás: 6 színből kell választani hármat úgy, hogy a színek sorrendje is számít (variáció) V 6,3 =6⋅5⋅4= 6! ( 6−3 )! = 6! 3! =120 . 16.6. Néhány év múlva a forradalom elsöpörte a királyságot, az ország új zászlót szeretett volna. A demokratikus pártok megegyeztek abban, hogy a lobogó középső sávja a citromfa-ültetvényekre való tekintettel sárga lesz. Most hányféle lehetőség van? Megoldás: A maradék öt színből kell kettőt kiválasztani úgy, hogy a sorrend is számít: V 5,2 =5⋅4= 5! ( 5−2 )! = 5! 3! =20 . 16.7. Hányféleképpen fordulhat elő ultiban, hogy a kezdetben kapott 10 lap közül 5 piros és 5 zöld? (A játékot természetesen 32 lapos magyar kártyával játsszák.) Megoldás: A pakliban minden színből (piros, zöld, makk, tök) 8 lap található. A pakliban levő 8 piros közül "választódik ki" az az 5, ami hozzánk kerül. Az osztás után csak az számít, hogy mit osztottak nekünk, de az nem fontos, hogy milyen sorrendben, ezért kombinációról van szó. Ezek lehetséges száma: ( 8 5 ) . Az 5 zöld lapra hasonló érvelés áll. Összegezve: minden egyes piros ötöshöz ( 8 5 ) -féleképpen választhatunk öt zöldet, vagyis a coedu.sze.hu/print.php4?print_items=
2/7
2013.02.02.
COEDU // NYOMTATÁS
lehetséges esetek száma: ( 8 5 )⋅( 8 5 )=3136 16.8. Egy hagyományos lottószelvény ára 175 Ft (2005. november 20-án). Mekkora összeget kell befektetnünk, hogy biztos 5 találatunk legyen? Megoldás: A húzáskor 90 számból választanak ki ötöt. Nem számít, hogy milyen sorrendben húzzák ki ezeket, csak az számít, hogy végül is mik lesznek a nyerő számok (tehát kombinációról van szó). C 90,5 =( 90 5 )=43949268 . Ennyi lottószelvény ára: 175⋅( 90 5 )=7691121900 Ft. 16.9. A tornász vb-n 30 ország csapata indult. Hányféleképpen alakulhat ki a hatos döntő mezőnye, ha a rendező ország csapata biztosan ott lesz? Megoldás: A döntőbe jutás ténye számít, a 6 közötti sorrend még nem. Vagyis a rendezőt leszámítva a maradék 29 csapatból kell kiválasztani másik öt továbbjutót (kombináció). C 29,5 =( 29 5 )=118755 . 16.10. Hányféle négyjegyű szám állítható elő az 1, 2, 3, 4, 5, 6, 7 számjegyekből, ha:
a)
minden számjegy csak egyszer szerepelhet;
b)
a számjegyek többször is szerepelhetnek?
Megoldás: a) Ebben az esetben 7 különböző elemből kell kiválasztani négyet úgy, hogy a sorrend is számít (hiszen egy számban számít a számjegyek sorrendje). Vagyis ismétlés nélküli variációról van szó, tehát a lehetséges sorrendek száma: 7! ( 7−4 )! = 7! 3! =7⋅6⋅5⋅4=840 . Így ebben az esetben 840 különböző számot állíthatunk elő. Úgy is megszámolhattuk volna a lehetőségeket, hogy a következőképp gondolkodunk: az 1. helyre 7-féle szám kerülhet; a 2. helyre 6-féle; a 3. helyre 5-féle; a 4. helyre pedig 4-féle szám kerülhet, így a lehetőségek száma: 7⋅6⋅5⋅4=840 . b) Ha egy számjegy többször is szerepelhet, akkor 7 különböző elemből kell 4-et kiválasztani úgy, hogy egy elem többször is szerepelhet, továbbá számít a kiválasztás sorrendje, tehát itt ismétléses variációról van szó. A lehetséges sorrendek száma tehát: 7 4 =2401 . Gondolkodhattunk volna az a) részhez hasonlóan úgy is, hogy az 1. helyre 7-féle szám kerülhet; a 2. helyre szintén 7-féle; a 3. helyre szintén 7-féle; a 4. helyre pedig ismét 7-féle szám kerülhet, így a lehetőségek száma: 7⋅7⋅7⋅7= 7 4 =2401 .
Ellenőrző feladatok coedu.sze.hu/print.php4?print_items=
3/7
2013.02.02.
COEDU // NYOMTATÁS
1. feladat Hányféle nyolcjegyű szám állítható elő az 1, 2, 3, 4, 5, 6, 7, 8 számjegyekből, ha minden számjegy csak egyszer szerepelhet? 8 88 8! 88
2. feladat Hányféle nyolcjegyű szám állítható elő az 1, 2, 3, 4, 5, 6, 7, 8 számjegyekből, ha minden számjegy többször is szerepelhet? 88 8! 8 88
3. feladat Hányféle jelsorozat állítható elő 4 darab "!" 3 darab "?" jelből? 12 7! 120 35
4. feladat Lékó Péter egy sakkversenyen 8 játszmából négyet nyert, kétszer remizett, kétszer veszített. Hányféleképpen történhetett ez, ha csak az coedu.sze.hu/print.php4?print_items=
4/7
2013.02.02.
COEDU // NYOMTATÁS
egyes partik kimenetele számít? 84 8! 720 420
5. feladat Hányféle négyjegyű szám állítható elő az 1, 2, 3, 4, 5, 6, 7, 8 számjegyekből, ha minden számjegy csak egyszer szerepelhet? 84 1680 2400 720
6. feladat Ha többször is szerepelhet? 84 1680 720 2400
7. feladat Egy vasútállomásról 10 vagonból álló tehervonat-szerelvényeket indítanak. Minden szerelvény 5 zöld, 2 kék és 3 piros vagonból áll. Hány különböző összeállítás lehetséges? 30 coedu.sze.hu/print.php4?print_items=
5/7
2013.02.02.
COEDU // NYOMTATÁS
2520
5!⋅3!⋅2! 1680
8. feladat Egy fagyizóban 12-féle fagylalt közül választhatunk. Hányféle háromgombócos fagyit vehetünk, ha minden gombóc különböző, és tölcsérbe kapjuk (számít a sorrend)? 12! 1320 12 3 36
9. feladat Egy fagyizóban 12-féle fagylalt közül választhatunk. Hányféle háromgombócos fagyit vehetünk, ha minden gombóc különböző, és kehelybe kapjuk (nem számít a sorrend)? 220 12! 12 3 36
10. feladat A 0, 1, 2, 3, 4, 5 számjegyekből hányféle 45-re végződő ötjegyű szám készíthető, ha minden számjegy csak egyszer szerepelhet? 18
coedu.sze.hu/print.php4?print_items=
6/7
2013.02.02.
COEDU // NYOMTATÁS
24 120
720
coedu.sze.hu/print.php4?print_items=
7/7
