1. Kombinatorikai bevezetés példákkal, (színes golyók): (a)
(sorba rendezés): n különböz® szín¶ golyót hányféleképp állíthatunk sorba? 10-et? ismétlés nélküli permutáció
n! (b)
ismétléses permutáció:
n1 piros, n2 kék,. . . nk fehér golyót hányféleképp állíthatunk sorba? 10-et, amik közül 3, 2, 4 egyforma szín¶ van? n! n1 !n2 !...nk !
(c)
10!
9! 3!2!4!
(kiválasztás és sorba rendezés): n különböz® szín¶ golyó közül hányféleképp választhatunk k-at, ha számít a sorrendjük? 10 golyó, 3-t húzunk? ismétlés nélküli variáció
n! (n − k)! (d)
ismétléses variáció:
(e)
ismétlés nélküli kombináció
(f)
ismétléses kombináció:
10! (10 − 3)!
n-féle szín¶ golyó van, mindb®l kell®en sok (legalább k ). Húzunk k-at, számít a sorrend. Hányféle kimenetel lehet? 10-féle golyó, mindb®l legalább 3, és 3-t húzunk? nk 103 (kiválasztás): n különböz® szín¶ golyóból hányféleképp választhatunk ki k -at, ha a sorrend nem számít? 10-b®l 3-t? 10 10! n n! = = k!(n − k)! 3 3!(10 − 3)! k
n-féle sütemény van a cukrászdában, mindb®l jó sok. Mi k sütit szeretnénk hazavinni. Ez hányféleképp (t)ehet® meg? 10-féle süti van, 3 darabot veszünk? n+k−1 10 + 3 − 1 k 3
2. Binomiális együtthatók:
n X n k n−k (a + b) = a b k k=0 n
(a + b)n = (a + b)(a + b). . . (a + b), azaz ak bn−k együtthatója annyi lesz, ahányféleképpen az n db zárójelb®l k db a-t és n − k db b-t választhatunk (k megy 0-tól n-ig). Ez épp nk -féleképp tehet® meg (ismétlés nélküli kombináció). Indoklás:
3. A következ® feladatok a 6 alaptípusba tartoznak. Sorolja be és oldja meg ®ket! (a) Hány különböz® (értelmes vagy értelmetlen) 13-bet¶s szó készíthet® a KOMBINATORIKA szó bet¶ib®l? ismétléses kombináció, a magoldás 13!/(2!2!2!2!), ahol a 4 db 2!-t a 4 db kétszer ismétl®d® bet¶ indokolja.
Megoldás:
(b) Mennyiféleképpen olvasható ki a MENNYIFÉLE az alábbi rajzból, ha a bal fels® sarokból indulunk, és csak lefelé vagy jobbra léphetünk? M E N N Y
E N N Y I
N N Y I F
N Y I F É
Y I F É L
I F É L E
ismétlés nélküli kombináció, ugyanis 9-et kell mindenképp lépni, és ebb®l szabadon választhatjuk ki azt az 5 lépést, amit jobbra teszünk meg. A válasz tehát 95 . Megoldás:
(c) Legalább hány lottószelvényt kell kitöltenünk, találatosunk? Megoldás:
ismétléses kombináció:
hogy biztosan legyen 5-
.
90 5
(d) Hány különböz® autó-rendszám készíthet® három bet¶b®l és három számjegyb®l? És 2 bet¶, 4 számjegyb®l? Hányszor több kocsi különböztethet® meg az els® módszerrel? ismétléses variáció: az els® esetben a válasz 263 · 103 , a másodikban 26 · 10 . A hányados 2 · 6.
Megoldás: 2 4
(e) Három kockát dobunk fel egyszerre. Az azonos szín¶ kockák megkülönböztethetetlenek. Hány különböz® kimenetele lehet a kísérletnek, ha i. mindhárom kocka különböz® szín¶; ii. két kocka piros, a harmadik kék; iii. a kockák azonos szín¶ek? Megoldás:
i. különböz® szín¶ kockák: 63 ii. 2 piros, 1 kék:
63 2!1!
63 3! (f) Egy versenyen 23 versenyz® indul. sorrend lehet a dobogón? iii. azonos szín¶ kockák:
Megoldás:
riáció).
23! illetve
Hányféle sorrend alakulhat ki?
Hányféle
23! (ismétlés nélküli permutáció, illetve ismétlés nélküli va20!
4. (Gyakran használt módszer: komplementer számolása): Hatszor dobunk egy kockával. Hány olyan dobássorozat lehet, amelyben dobtunk hatost? Összesen 66 -féle dobássorozat lehet, ezek közül 56 olyan van, amiben nincsen 6-os. Tehát azok száma, amikben van legalább egy hatos: 66 − 56 .
Megoldás:
5. A binomiális együtthatókra vonatkozó következ® összefüggések kombinatorikus indoklása: (a)
n+1 k
=
n n + k−1 k
(b)
X k n+m n m = k i k−i i=0
a másodikat így indokolhatjuk: egy zsákban van n piros és m kék golyó, az egyenl®ség bal oldalán azt látjuk, hogy hányféleképp választhatunk ki a zsákból (a színekre nem gyelve) k golyót. A jobb oldalon is ez áll, hiszen a k golyó között, amit kiválsztunk, lehet pontosan i db piros (i = 0..k ), ezeket az n db piros golyó közül ni féleképp választhatjuk, de akkor n − i db kéket kell választanunk az m db kék közül, ez m pedig n−i -féleképp tehet® meg. Az els® feladat ennek pont az m = 1 esete. Megoldás:
Gyakorló feladatok, végeredménnyel
1. Hányféleképpen tehetünk fel egy sakktáblára a) egy fekete és egy fehér bástyát, b) két fehér bástyát, c) egy fekete egy fehér és egy zöld bástyát, d) három fehér bástyát? 2. Hányféleképpen tölthet® ki egy TOTÓ-szelvény? 3. 32 lapos magyar kártyából hányféleképpen húzhatunk 6 lapot egymás után (!), ha a kihúzott lapot nem tesszük vissza? És ha visszatesszük? 4. Egy 30 f®s osztály diákbizottságot választ: elnök, titkár, sportfelel®s, kultúrfelel®s, gazdaság felel®s. Hányféle eredmény lehet, ha Pistinek mindenképpen szeretnénk tisztséget adni? 5. Egy emeletes ház szintjeit szeretnénk kifesteni. Hányféleképpen tehetjük ezt meg, ha piros kék és sárga festék áll rendelkezésre, és a) két emelet van, b) három emelet van, c) 20 emelet van, d) 20 emelet van, de szomszédos szintek között nem lehetnek egyszín¶ek. 6. Hányféleképp tehetünk fel a sakktáblára 8 különböz® szín¶ bástyát úgy, hogy semelyik kett® ne üsse egymást? És ha azonos szín¶ek? 7. Hányféle - akár értelmetlen - szó készíthet® az ANAGRAMMA szó bet¶inek összekavarásával? És ha nem engedjük meg, hogy két M egymás mellett legyen? 8. Hányféleképpen sorakozhat fel egy állatidomár mögött egy oroszlán, egy tigris és egy jegesmedve? S ha még egy pingvin is van? 9. Nyolc titkosügynök - A, B, C, D, E, F, G, X - leül egy (I) padra, (II) kerek asztalhoz. Hányféleképpen helyezkedhetnek el úgy, hogy a) nincs megkötés, b) A, B és C egymás mellett szeretnének ülni, ilyen sorrendben, c) A, B és C egymás mellett szeretnének ülni bármilyen sorrendben, d) A B mellé, C pedig D mellé ül, e) (I) X csak a szélén hajlandó ülni, (II) X csak F jobbja fel®l hajlandó ülni, f) A és B nem ülnek egymás mellé, g) (I) X nem hajlandó a szélén ülni, (II) X nem hajlandó F mellé ülni. 10. Hány buszjegyre van ahhoz szükség, hogy tetsz®leges lyukkombináció esetén legyen érvényes jegyünk, ha a jegyen 9 számozott mez® van, melyekb®l a) 3-at lyukaszt ki a gép, b) 3-at vagy 4-et lyukaszt ki a gép. 11. Egy pakli francia kártyából van a kezemben 10 lap, melyek között összesen három dáma van, négy pikk, de az egyik a pikk dáma. Hányféleképpen lehetséges ez? Végeredmények:
64 · 63 , ismétlés nélküli variáció, vagy 64 , 2 2 64 · 63 · 62 ismétlés nélküli kombináció. c) 64 · 63 · 62, ismétlés nélküli variáció. d) , 3! 64 ismétlés nélküli variáció , vagy 3 ismétlés nélküli kombináció.
1. a) 64 · 63, ismétlés nélküli variáció. b)
2. 313 ismétléses variáció. 3.
32! Ha nem tesszük vissza a lapokat, akkor ez ismétlés nélküli variáció. 26! Ha visszatesszük 326 , ismétléses variáció.
4. 5 · 29 · 28 · 27 · 26 , ismétlés nélküli variáció 5. a) 3 · 3 ismétléses variáció. b) 3 · 3 · 3 c) 320 d) 3 · 29 6. Ha különböz® szín¶ek a básták: 64 · 49 · 36 · 25 · 16 · 9 · 4 · 1 Ha azonos szín¶ek a bástyák, akkor 8! 7.
9! 8! 9! Ismétléses permutáció. Ha nincs a két M egymás mellett: − 4!2! 4!2! 4!
8. 3!, de ha pingvin is van, akkor 4!, mindkett® ismétlés nélküli permutáció. 9. (I) pad, (II) körasztal a) (I) 8! (II) 7! b) (I) 6! (II) 5! c) (I) 6! · 3!, (II) 5! · 3! d) (I) 6! · 2! · 2! (II) 5! · 2! · 2! e) (I) 2 · 7! (II) 6! f) (I) 8! − 2! · 7! (II) 7! − 2! · 6! g) (I) 8! − 2 · 7! (II) 7! − 2! · 6!
10. a) 93 lehet®ség, ez egy ismétlés nélküli kombináció. b) 93 + 94 ismétlés nélküli kombináció. 36 11. 32 · 12 · 4 , ismétlés nélküli kombináció. 3
Gyakorló feladatok, megoldás nélkül
1. Egy csomag magyar kártyát jól összekeverünk. Mennyi annak a valószín¶sége, hogy a 4 ász egymás után helyezkedik el? 2. 100 alma közül 10 férges. Mennyi a valószín¶sége, hogy válogatás nélkül 5 almát kivéve, közöttük lesz férges alma? 3. Két testvér ugyanabba a 27-es létszámú osztályba jár. Egy gyors sorakozónál mindenki beáll valahova. a./ Mennyi a valószín¶sége, hogy a két testvér között pontosan 10-en állnak? b./ Hogyan változik az eredmény, ha kör alakban helyezkednek el? 4. A 32 lapos magyar kártyából 4 lapot véletlenszer¶en kiválasztunk. Mennyi annak a valószín¶sége, hogy a kihúzott lapok között pontosan egy piros és egy ász lesz? 5. Egy urnában 6 piros, több fehér és fekete golyó van. Annak a valószín¶sége, hogy egy golyót kihúzva, az fehér vagy fekete lesz: ; hogy piros vagy fekete szín¶ lesz: . Hány fehér és fekete golyó van az urnában? 6. Annak a valószín¶sége, hogy egy most felvett f®iskolai hallgató diplomát szerez, 0,4. Határozza meg annak a valószín¶ségét, hogy 5 hallgató közül a./ senki sem szerez diplomát, b./ pontosan 1 hallgató szerez diplomát, c./ legalább 1 hallgató diplomás lesz, d./ mindenki diplomát szerez! 7. Egy pénzérmét 10-szer egymás után feldobunk. Ha fejet kapunk, azt F-fel, ha írást, azt I-vel jelöljük. Mennyi annak a valószín¶sége, hogy az F és I bet¶knek ez a 10 elem¶ sorozata tartalmaz két azonos bet¶t egymás után? 8. Egy vendégl® egyik asztalánál 12 vendég ül. Összesen rendelnek 3 üveg sört, 4tésztát, 3 kávét és 2 fagylaltot. ( Minden vendég csak egy tételt rendel és a sörök, tészták, stb. teljesen egyformák. ) A pincér emlékszik arra, hogy mib®l mennyit kell hoznia, de teljesen elfelejtette, hogy mit, kinek kell adnia. Találomra szétosztja amit hozott. Mennyi annak a valószín¶sége, hogy mindenki azt kapja amit kért? 9. Mennyi a valószín¶sége, hogy ha valakinek az 52 lapos francia kártyából 13 lapot kiosztanak, akkor legfeljebb 3 ásza lesz? 10. A 32 lapos magyar kártyacsomagból kihúzunk 6 lapot. Mennyi annak a valószín¶sége, hogy e hat lap között mindegyik szín el®fordul? 11. Egy rossz, de néha m¶köd® villanykapcsoló átlagosan a 12-ik próbálkozásra gyújtja fel a villanyt. Mennyi a valószín¶sége, hogy a harmadik kísérletre gyullad fel a villany? 12. Hány különböz®
sorrend be
állíthatóak az 1, 2,. . . n számok?
13. Hányféleképpen választhatunk ki az 1, 2,. . . n számok közül k -t, ha a kiválasztás sorrend je számít, és minden elemet csak egyszer választhatunk? Mi a helyzet akkor, ha egy elemet akárhányszor kiválaszthatunk?
14. Hányféleképpen választhatunk ki az 1, 2,. . . n számok közül k -t, ha a kiválasztás sorrendje nem számít és minden elemet csak egyszer választhatunk? Mi a helyzet akkor, ha egy elemet akárhányszor is kiválaszthatunk? 15. Hányféleképpen állíthatunk sorba k db egyest és n − k db 0-t? Hány n hosszú 0 1-sorozat van összesen? 16. Egy n elem¶ halmaznak hány részhalmaza van? 17. Tíz urnába hányféleképpen helyezhet® el 5 megkülönböztethetelen golyó? És 5 különböz®? 18. Hány különböz® autó-rendszám készíthet® (három bet¶b®l és három számból)? 19. (1 + x)n kifejtésében mennyi xk együtthatója? (k = 0, 1, . . . , n) 20. Hány pontosan 6 jegy¶ (tizes számrendszerben), tízzel nem osztható szám van? 21. Hatszor dobunk egy kockával. Hány olyan dobássorozat lehet, amelyben dobtunk hatost? 22. Hányféle számot állíthatunk össze három 1-es, négy 2-es és kilenc 3-as mindegyikének felhasználásával (a számok tehát mind 16 jegy¶ek lesznek). 23. Legkevesebb hány lottószelvényt kell az ötöslottón kitölteni, hogy biztosan öttalálatosunk legyen? 24. Három kockát dobunk fel egyszerre. Az azonos szín¶ kockák megkülönböztethetetlenek. Hány különböz® kimenetele lehet a kísérletnek, ha (a) mindhárom kocka különböz® szín¶; (b) két kocka piros, a harmadik kék; (c) a kockák azonos szín¶ek? 25. Hányféleképpen festhetjük egy n-emeletes ház szintjeit fehérre, drappra és barnára, ha a szomszédos szintek nem élehetnek azonos szín¶ek? 26. Hányféleképpen állíthatunk sorba 42 út és 42 lányt, ha úk és lányok felváltva kell, hogy kövessék egymást? És ha csak 41 lány van? 27. Számoljuk ki, hogy egy kitöltött lottószelvényünkhöz hány olyan számötöst húzhatnak ki, amivel 0, 1, 2, 3, 4 illetve 5 találatunk lesz. 28. Egy Forma I-es futamon 18 versenyz® indul. (a) Hány féle lehet a beérkezési sorrend? (b) Hány féle sorrend alakulhat ki a dobogón?
(c) Tegyük fel, hogy a 18 versenyz® 3 különböz® csapathoz tartozik, mindhárom csapat 6-6 f®t nevez. Hány féle kimenetele lehet a versenynek a csapatok szempontjából? (Például egy lehetséges kimenetel: az els® csapaté az 1., 4., 5., 7., 8. és 18. hely, a másodiké a 9. helyt®l a 14-ig, és a harmadiké a maradék hat hely.) 29. Tíz urnába helyezünk el 5 egyforma piros, 4 egyforma kék és egy zöld golyót úgy, hogy minden urnába egy golyó kerüljön. Hányféleképpen tehetjük ezt meg? 30. Hányféleképpen tölthet® ki egy totószelvény, úgy hogy legalább két döntetlenre akarunk tippelni? 31. Tíz rabló el akar rejteni egy láda kincset. Úgy akarják lakatokkal lezárni a ládát, hogy semelyik három ne tudja kinyitni, de bármelyik négy már igen. Hány lakat kell, és hogyan osszuk szét a kulcsokat? (Ez kicsit nehezebb feladat.)
