0
KOMBINATORIKA – OPAKOVÁNÍ U IVA ZE SŠ
as ke studiu kapitoly: 30 minut
Cíl: Po prostudování této kapitoly budete um t použít • základní pojmy kombinatoriky • vztahy pro výpo et kombinatorických úloh
-6-
Výklad: 0.1 Kombinatorika – co to je? Kombinatorika je vstupní branou do teorie pravd podobnosti. Zabývá se r znými zp soby výb ru prvk z daného souboru. Už jste si vzpomn li? Jde p ece o sou ást st edoškolské matematiky. Ale protože opakování je matkou moudrosti, jdeme na to ... Nejd íve si ujasn me s jakými výb ry se v praxi m žeme setkat. Prvním kritériem je uspo ádanost výb ru. A. Uspo ádaný výb r (= Variace) je takový výb r, p i n mž záleží na po adí vybraných prvk . P .: Kolik trojciferných ísel lze sestavit z ísel 1; 3; 8; 9? íslo 139 a íslo 391 považujeme za dv r zné variace výb ru. B. Neúspo ádaný výb r (= Kombinace) je oproti tomu výb rem, p i kterém na po adí vybraných prvk nezáleží. P .: Kolik je možností jak vsadit Sportku? 7 ísel ze 49 – nap . kombinace {1;2;3;4;5;6;7} je {2;3;1;6;7;4;5} – nezáleží na tom v jakém po adí jsme ísla zaškrtali.
totožná
s kombinací
Druhým kritériem je skute nost, zda se prvky po výb ru do p vodní množiny vracejí i nikoliv. Podle toho se výb ry rozlišují na: A. Výb ry s opakováním tj. vybrané prvky se vracejí do p vodní množiny P .: Z množiny {1;3;8;9} lze mimo jiné vytvo it troj íslí {131; 188; 888; 119; 139 ...} B. Výb ry bez opakování tj. vybrané prvky se do p vodní množiny nevracejí Matematicky je jednodušší popis výb r s opakováním, avšak v praxi se ast ji setkáte s výb ry bez opakování (test není možno opakovat, nap . tažnost trubky m žete testovat pouze jednou, pro další test je zapot ebí použít novou trubku)
-7-
0.2 Základní kombinatorická pravidla 0.2.1 Kombinatorické pravidlo sou inu Toto pravidlo používáme v b žném život zcela automaticky. Než uvedeme jeho matematickou formulaci, ukážeme si jeho využití na p íkladu.
ešený p íklad: U stánku nabízejí ty i druhy zmrzliny a t i polevy. Kolik r zných zmrzlin s polevou lze vytvo it, jestliže nechceme míchat více druh ani více polev? ešení: Následující diagram zobrazuje všechny možnosti výb ru: okoládová poleva vanilková
O íšková poleva Ovocná poleva okoládová poleva
jahodová
O íšková poleva Ovocná poleva okoládová poleva
meru ková
O íšková poleva Ovocná poleva
okoládová poleva citrónová
O íšková poleva Ovocná poleva
-8-
Ke každému ze ty druh zmrzliny m žeme p idat jednu ze t í polev, celkem je proto možné vytvo it 4 · 3 = 12 r zných zmrzlin s polevou.
Výklad: Zobecn ním p edchozí úvahy dojdeme kombinatorické pravidlo sou inu:
k následujícímu
pravidlu
nazývanému
Po et všech uspo ádaných k-tic, jejichž první len lze vybrat n1 zp soby, druhý len po výb ru prvního lenu n2 zp soby atd. až k-tý len po výb ru všech p edcházejících len nk zp soby, je roven n1 · n2 · … · nk. V úvodním p íklad jsme hledali uspo ádané dvojice druh − poleva, jejichž první len (druh) lze vybrat ty mi zp soby a druhý len (polevu) lze vybrat t emi zp soby. Tedy k = 2, n1 = 4, n2 = 3; n1 · n2 = 12. 0.2.2 Kombinatorické pravidlo sou tu Také toto pravidlo v život asto využíváme, aniž si to uv domujeme. Jestliže máme nap . t i žluté, dv modré a ty i zelené pastelky, umí každý snadno spo ítat, že dohromady máme 3 + 2 + 4 = 9 pastelek. Matematicky se toto pravidlo formuluje takto: Jsou-li A1, A2, …, An kone né množiny, které mají po ad p1, p2, …, pn prvk , a jsou-li každé dv disjunktní, pak po et prvk množiny A1 ∪ A2 ∪ … ∪ An je roven p1 + p2 + … + pn.
0.3 Uspo ádané výb ry (variace) Znovu si p ipome me, že u variací záleží na po adí vybíraných prvk . 0.3.1 Variace k-té t ídy bez opakování Nech M je libovolná množina n prvk . Každá uspo ádaná k-tice (skupina k prvk ) z navzájem r zných prvk množiny M se nazývá variace k-té t ídy množiny M bez opakování a zna íme ji Vk(n) – varia ní íslo. Po et variací Vk(n) se ur uje podle vztahu:
Vk (n) = n.(n − 1).(n − 2)
(n − k + 1) =
-9-
n! (n − k )!
ešený p íklad: Z dvaceti lenného zastupitelstva (8 z ODS, 6 z SSD, 4 z KDU- SL, 2 ze SZ) se musí zvolit p ti lenné p edsednictvo (p edseda, místop edseda, 3 lenové). Kolika r znými zp soby lze p edsednictvo sestavit:
a) nejsou-li na výb r funkcí žádná další omezení b) je-li stanoveno, že p edseda a místop edseda musí být ze dvou nejsiln jších stran ešení:
a) Nejsou-li stanovena žádná omezení pro výb r p edsednictva, jde o typický p íklad variací páté t ídy bez opakování:
V5 (20) =
20! 20! = = 20.19.18.17.16 = 1860480 (20 − 5)! 15!
V tomto p ípad tedy existuje 1860480 možností jak sestavit p edsednictvo zastupitelstva. b) Nyní je stanoveno, že p edseda a místop edseda musí být ze dvou nejsiln jších stran (není e eno, že p edseda musí být z nejsiln jší strany). Možností jak zvolit p edsedu a místop edsedu je tedy:
8.6 + 6.8 = 96
Po et možností, jak zvolit p edsedu z ODS a zárove místop edsedup edsedu z SSD Po et možností, jak zvolit p edsedu z ODS a zárove místop edsedup edsedu z SSD
Zbylá t i místa v p edsednictvu mohou obsadit libovolní t i lidé ze zbývajících osmnácti (bez ohledu na stranickou p íslušnost). Takových možností je: V3 (18) =
18! 18! = = 18.17.16 = 4896 (18 − 3)! 15!
Uplatníme-li kombinatorické pravidlo sou inu, zjistíme že celkový po et možností, jak v p ípad takovýchto požadavk sestavit p edsednictvo je 470016 (= 96 . 4896).
Výklad: V p ípad , že velikost výb ru je totožná s rozsahem množiny M (k=n) používáme pro tento typ variací název permutace. U permutací tak nejde v podstat o výb r, nýbrž o r zná uspo ádání téže množiny (p esmy ky).
- 10 -
0.3.2 Permutace bez opakování Permutace množiny M (bez opakování) jsou všechna navzájem r zná uspo ádání množiny M. Po et permutací n prvkové množiny stanovíme na základ vztahu: P ( n ) = V n ( n) =
n! = n! (n − n)!
ešený p íklad: Vra me se op t k volb p edsednictva zastupitelstva. P edpokládejme však, že p edsednictvo je už zvoleno a je pouze t eba rozd lit si funkce. Kolik je možností, jak si funkce rozd lit? ešení: Je z ejmé, že jde o permutace (p esmy ky) 5-ti lenné množiny: P(5) = 5! = 5.4.3.2.1 = 120
P edsednictvo si tedy m že rozd lit funkce 120-ti zp soby.
Výklad: Definujme si op t M jako libovolnou n-prvkovou množinu. 0.3.3 Variace k-té t ídy s opakováním tak nazýváme každou uspo ádanou k-tici prvk mohou opakovat.
z množiny M, v níž se jednotlivé prvky
Po et variací k-té t ídy s opakováním ur uje výraz V’k(n)
Vk, (n) = n k
ešený p íklad: Ur ete kolik je možností jak sestavit 6-ti místné telefonní íslo.
- 11 -
ešení: V tomto p ípad si zvolíme množinu M, M={0;1;2;3;4;5;6;7;8;9}. Pot ebujeme obsadit 6 míst.
Je z ejmé, že existuje celkem V6'(10) = 10 6
možností jak uspo ádat 10 íslic do šestice. V tuto chvíli si musíme uv domit, že telefonní íslo nem že za ínat „0“, proto musíme tyto možnosti od celkového po tu ode íst. 0
V’5(10) V5'(10) = 105
Mezi všemi 6-ti místnými ísly je 105 ísel za ínajících „0“. Existuje tedy 900 000 (106–105) možností jak vytvo it 6-ti místné telefonní íslo.
Výklad: 0.3.4 Permutace s opakováním M jme uspo ádanou n-tici k r zných prvk , v níž se jednotlivé prvky opakují ni (i = 1, 2, ... , k) krát. Permutace s opakováním vznikají r zným uspo ádáním p vodní n-tice. Platí: k i =1
ni = n
Po et permutací s opakováním je dán vztahem: Pn'1 , n2 ,
, nk
=
P(n) n! = P(n1 ).P(n2 ). .P(nk ) n1!.n2!. .nk !
- 12 -
ešený p íklad: Na plakátovací plochu o kapacit 10 míst se mají vylepit reklamní plakáty 4 spole ností. Spole nost ARMA si p edplatila 3 plakáty, spole nost BRUNO 2 plakáty, spole nost CEKO 1 plakát a spole nost DINA 4 plakáty. Ur ete kolika r znými zp soby lze ploch pokrýt. ešení: P edpokládáme-li, že každá spole nost dodala pouze jediný druh plakátu, pak jednotlivé varianty polepení tvo í permutace s opakováním: P43', 2,1,4 =
10! 10.9.8.7.6.5 = = 12600 3!.2!.1!.4! 3.2.2
Plakátovací plochu lze polepit 12600 r znými zp soby.
Výklad: 0.4 Neuspo ádané výb ry (kombinace) Kombinace se používají v p ípadech, kdy se ze skupiny prvk vybírá menší podskupina, jejíž prvky nemají specifickou roli, tj. jsou vzájemn zam nitelné (nezáleží na po adí vybraných prvk ). P íkladem takovéto podskupiny je závodní družstvo mladších žák pro b h na 1500 metr (reprezentujících jistou ZŠ). Definujme si znovu M jako libovolnou n prvkovou množinu. 0.4.1 Kombinace k-té t ídy bez opakování pak nazv me každou k prvkovou podmnožinu sestavenou z navzájem r zných prvk množiny M. Po et r zných kombinací Ck(n) se ur í na základ vzorce: Ck (n) =
n k
=
n! (n − k )!.k!
Hodnota Ck(n) se nazývá kombina ní íslo.
- 13 -
ešený p íklad: Ve tvrtém ro níku ZŠ studuje 30 chlapc a 50 d v at. Pro reprezentaci ro níku v lehké atletice je t eba sestavit smíšené 10-ti lenné družstvo (5 chlapc , 5 dívek). Kolik je možností jak takovéto družstvo sestavit? ešení: Pro výpo et použijeme kombinatorické pravidlo o sou inu: Celkový po et možností jak sestavit družstvo (n) je dán sou inem po tu možností jak vybrat 5 chlapc ze 30-ti (n1) a 5 dívek z 50-ti (n2). Po et možností jak vybrat 5 chlapc ze 30-ti je z ejm : n1 = C5 (30) =
30 5
=
30! 30.29.28.27.26 = = 142506 (30 − 5)!.5! 5.4.3.2.1
Po et možností jak vybrat 5 dívek z 50-ti je z ejm n2 = C5 (50) =
50 50! 50.49.48.47.46 = = = 2118760 5 (50 − 5)!.5! 5.4.3.2.1
A celkový po et možností jak sestavit družstvo je tedy: n = n1.n2 = 142506.2118760= 301.936012560 , tj. tém 302 miliard.
Výklad: 0.4.2 Kombinace k-té t ídy s opakováním nazv me každou k- lennou skupinu sestavenou z prvk množiny M tak, že se prvky ve skupin mohou opakovat a p itom nezáleží na jejich po adí. Po et kombinací k-té t ídy s opakováním je dán vztahem: C k'( n) = C k ( n + k − 1) =
n + k −1 k
=
( n + k − 1)! (n − 1)!.k!
Kvalita výrobku se rozlišuje t emi stupni jakosti: A, B, C. a) Ur ete kolik r zných výsledk m že mít výstupní kontrola výroby, testuje-li se kvalita 10-ti náhodn vybraných vzork . - 14 -
b) Kolik r zných výsledk nebude obsahovat ani jeden výrobek kvality C? ešení: a) Testovaný vzorek je 10-ti prvková skupina složená z výrobk r zných výsledk kontroly je tedy dán vztahem: C10' (3) =
3 + 10 − 1 10
=
t í typu jakosti. Po et
(12)! 12.11 = = 66 (12 − 10)!.10! 2.1
Existuje 66 r zných výsledk kontroly kvality 10-ti výrobk . b) Chceme-li zjistit, kolik výb r 10-ti výrobk neobsahuje výrobek kvality C, musíme omezit po et povolených t íd ve vzorku na 2 (A, B). C10' ( 2) =
2 + 10 − 1 (11)! 11 = = = 11 10 ( 2 − 1)!.10! 1
V 11-ti r zných výsledcích kontroly kvality nenajdeme výrobek kvality C.
Shrnutí: Uspo ádané výb ry
Bez opakování S opakováním
Neuspo ádané výb ry
•
Bez opakování S opakováním
Variace bez opakování Permutace bez opakování Variace s opakováním Permutace s opakováním Kombinace bez opakování Kombinace s opakováním
V k (n) = n.(n − 1).(n − 2). P(n) = V n (n) =
.(n − k + 1) =
n! (n − k )!
n! = n! (n − n)!
Vk, ( n) = n k
Pn'1 , n 2 ,
, nk
Ck ( n ) =
=
P ( n) n! = P(n1 ).P(n2 ). .P(nk ) n1!.n2 !. .nk !
n n! = k (n − k )!.k!
C k'( n) = C k ( n + k − 1) =
n + k −1 k
=
(n + k − 1)! (n − 1)!.k!
Kombinatorické pravidlo o sou inu
Po et všech uspo ádaných k-tic, jejichž první len lze vybrat n1 zp soby, druhý len po výb ru prvního lenu n2 zp soby atd. až k-tý len po výb ru všech p edcházejících len nk zp soby, je roven n1 · n2 · … · nk. •
Kombinatorické pravidlo o sou tu
Jsou-li A1, A2, …, An kone né množiny, které mají po ad p1, p2, …, pn prvk , a jsou-li každé dv disjunktní, pak po et prvk množiny A1 ∪ A2 ∪ … ∪ An je roven p1 + p2 + … + pn. - 15 -
Otázky 1. Co je to kombinatorika? 2. Jaká kritéria rozlišení výb ru v kombinatorice znáte? 3. Definujte: a) variace bez opakování b) variace s opakováním c) permutace bez opakování d) permutace s opakováním e) kombinace bez opakování f) kombinace s opakováním
- 16 -
Úlohy k ešení
Z kolika prvk lze vytvo it 90 variací druhé t ídy (bez opakování) ? 2. Z kolika prvk lze vytvo it 55 kombinací druhé t ídy (bez opakování) ? Zmenší-li se po et prvk o dva, zmenší se po et permutací (bez opakování) ty icetdvakrát. Ur ete po et prvk . Z kolika prvk lze vytvo it padesátkrát více variací t etí t ídy (bez opakování) než variací druhé t ídy (bez opakování) ? V prodejn si m žete vybrat ze sedmi druh pohlednic. Kolika zp soby lze koupit: a) 10 pohlednic, b) 5 pohlednic, c) 5 r zných pohlednic V knihkupectví prodávají 10 titul knižních novinek. Kolika zp soby lze koupit 4 knižní novinky, 5 r zných knižních novinek? 7. Na hokejovém turnaji, kterého se ú astní 8 družstev, sehraje každý tým s ostatními práv 1 utkání. Kolik zápas bude celkem sehráno? 8. Z 5 bílých a 4 ervených kuli ek tvo íme trojice tak, aby v každé trojici byly vždy 2 bílé a 1 ervená kuli ka. Kolik trojic spl ujících tuto podmínky lze vytvo it? 9. Hokejový tým odjel na OH s 23 hrá i, a to s 12 úto níky, 8 obránci a 3 branká i. Kolik r zných sestav m že trenér teoreticky vytvo it? 10. Kolika p ímkami lze spojit 7 bod v rovin , jestliže: a) žádné t i z nich neleží v p ímce, b) t i z nich leží v jedné p ímce? 11. Kolik kružnic je ur eno 10 body v rovin , jestliže žádné t i z nich neleží na p ímce a žádné ty i z nich neleží na kružnici? Kolik r zných hod m žeme provést a) dv mi, t emi r znobarevnými kostkami? 13. Kolik r zných zna ek teoreticky existuje v Morseov abeced , sestavují-li se te ky a árky ve skupiny po jedné až p ti?
- 17 -
14. Kolik prvk obsahuje množina všech p ticiferných p irozených ísel? 15. Deset p átel si vzájemn rozeslali?
poslalo pohlednice z prázdnin. Kolik pohlednic celkem
16. Kolikrát více je variací k-té t ídy z n prvk než kombinací k-té t ídy z t chto prvk (bez opakování) ? 17. V pln obsazené lavici sedí 6 žák a, b, c, d, e, f. a) Kolika zp soby je lze p esadit? b) Kolika zp soby je lze p esadit tak, aby žáci a, b sed li vedle sebe? c) Kolika zp soby je lze p esadit tak, aby žák c sed l na kraji? d) Kolika zp soby je lze p esadit tak, aby žák c sed l na kraji a žáci a, b sed li vedle sebe? 18. Student má v knihovn 4 r zné u ebnice pružnosti, 3 r zné u ebnice matematiky a 2 r zné u ebnice angli tiny. Kolika zp soby je lze se adit, mají-li z stat u ebnice jednotlivých obor vedle sebe? Kolika zp soby lze rozd lit 8 ú astník finále v b hu na 100 m do 8 drah? 20. Kolik r zných permutací lze vytvo it použitím všech písmen slova a) statistika, b) matematika? 21.
eta voják má vyslat na stráž 4 muže. Kolik muž má eta, je-li možno úkol splnit 210 zp soby?
22. Kolik úhlop í ek má konvexní n-úhelník? 23. V zásobníku je 7 ostrých a 3 slepé náboje. Ur ete, kolika zp soby lze namátkou ze zásobníku vyjmout 5 náboj , z nichž alespo 3 jsou ostré. 24. Kolika zp soby je možno na tvercové šachovnici s 64 poli vybrat 3 pole tak, aby všechna t i pole nem la stejnou barvu? 25. Kolika zp soby je možno na šachovnici s 64 poli vybrat 3 pole tak, aby všechna neležela v jednom sloupci?
- 18 -
ešení: 1. n = 10 2. n = 11 3. n = 7 4. n = 52 5. a) 8 008 možností b) 462 možností c) 21 možností 6. a) 715 b) 252
možností možností
7. 28 zápas 8. 40 možností 9. 18 480
možností
10. a) 21 b) 19
p ímkami p ímkami
11. 120 kružnic 12. a) 36 b) 216
r zných hod r zných hod
13. 62 r zných zna ek 14. 90 000 ísel 15. 90 pohled 16. Variací je k! krát více než kombinací 17. a) b) c) d)
720 240 240 96
možností možností možností možností
18. 1728 zp sob 19. 40 320 zp sob
- 19 -
20. a) 75 600 b) 151 200
p esmy ek p esmy ek
21. 10 voják 22.
n(n − 3) úhlop í ek 2
23. 231 možností 24. 31 744 možností 25. 41 216 možností
- 20 -
