1. K o m b i n a t o r i k a V teorii pravděpodobnosti a statistice budeme studovat míru výskytu -pravděpodobnostvýsledků procesů, které mají náhodný charakter, t.j. při opakování za stejných podmínek se objevují různé výsledky. Studiem zákonitostí rozdělení těchto možných výsledků se zabývá matematická statistika. Teorie pravděpodobnosti uvádí algoritmy pomocí nichž se toto studium v jednotlivých případech provádí. V elementárních úvahách a v řadě základních modelových situací si možné výsledky můžeme představit jako výběry z určité skupiny prvků. Přitom nás zajímají počty různých možných výběrů, které splňují nějakou dodatečnou podmínku. Uvedeme si nyní některé základní případy výběrů. 1.1 Věta: Obecné pravidlo kombinatoriky - pravidlo součinu. Nechť ve dvojici (A, B) můžeme místo A vybrat n různými způsoby a místo B celkem m různými způsoby, potom dvojici (A, B) můžeme vybrat celkem n.m různými způsoby. 1.2. Příklad: Při cestě z Kladna do Brna přes Prahu můžeme použít: z Kladna do Prahy - autobus, vlak, vlastní automobil: z Prahy do Brna - autobus, vlak, vlastní automobil, letadlo. Kolik je různých možností dopravy z Kladna do Brna. Řešení: Vidíme, že z Kladna do Prahy máme tři možnosti dopravy a z Prahy do Brna čtyři. Ke každé jednotlivé cestě z Kladna do Prahy existují čtyři další možnosti pokračování cesty. Je tedy celkem 3.4=12 možností jak cestovat z Kladna do Brna. (Obrázek grafu možností.) Poznámka: Je zřejmé, že pravidlo lze uplatnit i na trojice, čtveřice atd. Počet možností pak získáváme postupným násobením. 1.3. Definice: Permutace. Uvažujme skupinu n různých prvků, např. čísel {1, 2, . . . , n}. Různá uspořádání této skupiny prvků nazýváme permutacemi z n prvků. 1.4. Věta: Počet permutací. Permutací z n prvků je celkem (♠)
n! = 1.2 . . . n,
kde symbol n! čteme n faktoriál. Poznamenejme ještě, že v některých vzorcích se může objevit hodnota 0! a tu definujeme jako 0! = 1. Důkaz: provedeme matematickou indukcí. Je samozřejmé, že jeden prvek můžeme uspořádat právě jedním způsobem a zároveň vidíme, že 1! = 1, tedy tvrzení platí. Předpokládejme, že je pravdivé pro hodnoty 1, 2, . . . , n. Dokažme, že platí i pro n + 1 prvků. Utvoříme libovolnou permutaci n prvků. Potom různé permutace n+1 prvků vytvoříme umístěním n+1−tého prvku do dané permutace n prvků. Tento prvek můžeme umístit před první prvek, nebo před druhý prvek a nebo až před n−tý prvek. To je celkem n různých možností. Další možnost získáme tak, že tento prvek umístíme za n−tý prvek. Je tedy celkem n+1 možností jak k dané permutaci n prvků vytvořit různé permutace n + 1 prvků. Počet všech různých permutací n + 1 prvků je tedy (n + 1).n! = (n + 1).1.2 . . . n = (n + 1)!. 1.5. Příklad: Při psaní slov ananas a matematika přeházejme písmenka. Kolika způsoby je možné přehodit písmena, aby se slovo nezměnilo. Řešení: Vidíme, že ve slově ananas můžeme vyměnit mezi sebou písmenka a nebo n. První jsou tři a tudíž je 3!=1.2.3=6 možných výměn - permutací. Druhé jsou dvě a jsou tedy 2!=1.2=2 možnosti výměn. Podle pravidla součinu je tedy celkem 6.2=12 možností výměn, kdy se uvedené slovo nezmění. 3
Snadno nahlédneme, že pro slovo matematika dostaneme celkem 2!.3!.2!=2.6.2=24 možností. ( Dvě m, tři a, dvě t.) 1.6. Příklad: Řešte předchozí úlohu pro slovo Mississippi.
[1152]
1.7. Definice: Variace s opakováním. Uvažujme skupinu n prvků a vybírejme postupně k−tici prvků tak, že se mohou prvky ve výběru opakovat. Tyto výběry nazýváme k-členné variace s opakováním. 1.8. Věta: Počet variací s opakováním. Je celkem nk různých k−členných variací s opakováním. Důkaz: Ve výběru na první místo můžeme použít celkem n různých prvků. Protože se mohou prvky opakovat, pak pro každé další místo máme k dispozici vždy n prvků. Podle pravidla součinu je tedy celkem n.n . . . n = nk možností. 1.9. Příklad: Dospělý člověk má celkem 32 zubů. Jak velká musí být skupina lidí, aby se v ní vyskytli alespoň dva lidé se shodnou sestavou zubů. Řešení: Na každém místě čelisti člověk buď zub má nebo nemá. Můžeme tudíž vybírat ze dvou možností. Výběr opakujeme 32-krát. Počet různých sestav je počet 32-členných variací ze 2 prvků, což je 232 = 4 294 967 296. Skupina musí tedy obsahovat alespoň 232 + 1 = 4 294 967 297 lidí, aby se v ní vyskytli alespoň dva lidé se stejnou sestavou zubů. Poznámka: Zakódujme si zub symboly 0 a 1 pro případy zub chybí a nechybí. Počet sestav zubů je pak roven počtu různých výběru z prvků 0 a 1 předepsané délky. Symbol má tvar typu např. 1000110. Takový způsob kódování používají počítače, kdy všechny symboly převádí na čísla zapsaná ve dvojkové soustavě, tedy čísla složená z 0 a 1. 1.10. Příklad: Morseova abeceda se sestavá ze symbolů, které obsahují · a −. Jestliže uvažujeme „slovaÿ o nejvýše 6 symbolech, kolik různých slov máme k dispozici. Řešení: Každé slovo tvoříme výběrem ze dvou prvků (symbolů), tj. n = 2 a tvoříme výběry délky k, k = 1, 2, . . . , 6. Dostaneme tedy celkem 21 + 22 + 23 + 24 + 25 + 26 = 2 + 4 + 8 + 16 + 32 + 64 = 126 různých slov. 1.11. Příklad: Píšeme trojciferná čísla složená z číslic 0, 1, 2, . . . , 9. Kolik různých čísel můžeme napsat: a) číslo může začínat nulou; b) číslo nesmí začínat nulou. Řešení: V případě a) vybírame tři prvky z deseti, je tedy počet různých čísel roven 3členným variacím s opakovaním z 10 prvků. To je celkem 103 = 1000 čísel. V případě b) můžeme na první místo vybrat pouze 9 cifer (nesmí být nula) a na zbývající dvě opět 10. Je tedy celkem 9.10.10 = 900 různých možností. 1.12. Definice: Variace bez opakování. Vybírejme z n různých prvků k, 0 < k ≤ n, prvků tak, že se prvky nesmí ve výběru opakovat. Tyto výběry nazýváme k-členné variace bez opakování. 1.13. Věta: Počet variací bez opakování. Je celkem (♣)
n.(n − 1).(n − 2) . . . (n − k + 1), 1 ≤ k ≤ n,
k−členných variací bez opakování. Důkaz: Vztah odvodíme podle kombinatorického pravidla součinu. První prvek lze vybrat n způsoby, druhý už pouze n − 1 způsoby, třetí n − 2 způsoby a pro každý další máme vždy o 4
jednu možnost méně. Počet variací je roven součinu k čísel, kde řada začíná číslem n a každé následující je o 1 menší. Dostaneme tak pro počet variací vzorec n.(n − 1) . . . (n − k + 1). Poznámka: Všimneme si, že v případě kdy volíme k = n, t.j. při výběru vyčerpáme všechny prvky dané množiny, volíme vlastně pouze jejich pořadí. Jsou tedy n−členné variace bez opakování z n prvků shodné s jejich permutaceni. I pro jejich počty dostaneme ze vzorců (♠) a (♣) shodnou hodnotu n!. 1.14. Definice: Kombinace. Neuspořádaný výběr k prvků z množiny n prvků, 1 ≤ k ≤ n, takový, že se v něm každý prvek vyskytuje nejvýše jednou se nazývá k-člennou kombinací z n prvků. 1.15. Věta: Počet kombinací. Je celkem (♥) kombinací z n prvků.
n.(n − 1) . . . (n − k + 1) k−členných k!
Důkaz: Při výběru k prvků z n, kdy uvažujeme i jejich pořadí jsme dostali k− členné variace z n prvků. Ty z nich, které dostaneme jenom přerovnaním jejich prvků odpovídají jediné k−členné kombinaci. Je jich vždy k!, neboť je získáme jako všechny jejich permutace. Počet kombinací je tudíž podílem počtu k−členných variací bez opakování a počtu permutací k prvků. To je ovšem podle vzorců (♣) a (♠) vzorec (♥). 1.16. Definice: Kombinační číslo. Číslo ze vzorce (♥), které uvádí počet k−členných kombinací z n prvků označujeme symbolem n k
(♥♥)
!
=
n.(n − 1) . . . (n − k + 1) . k!
Nazýváme jej kombinační číslo a čteme n nad k. V souladu s definicí hodnoty 0!=1 definujeme n 0
!
=1
pro n = 0, 1, 2, . . . . 1.17. Věta: Vlastnosti kombinačních čísel. Pro všechna celá nezáporná čísla n, k, k ≤ n platí: !
a)
n 0
!
b)
n k
!
c)
n k
!
=
n n
=
n n−k
+
n k+1
= 1, !
=
!
=
n 1
!
= n;
n! ; (n − k)! k! n+1 k+1
Důkaz: a) Kombinační číslo
!
, n 0
k < n. !
= 1 podle definice.
Hodnoty kombinačních čísel ! dostaneme jestliže do vztahu (♥♥) dosadíme!za k postupně n(n − 1) . . . (n − n + 1) n! n−1+1 n n hodnoty k = n a k = 1. Je = = = 1; = = n. n 1 n! n! 1 b) Úpravou vzorce (♥♥) dostaneme
n k
!
=
5
n(n − 1) . . . (n − k + 1) = k!
n(n − 1) . . . (n − k + 1) (n − k)(n − k − 1) . . . 1 n! · = . k! (n − k)(n − k − 1) . . . 1 k!(n − k)! Jestliže v tomto vztahu dosadíme za k hodnotu n − k, pak ve jmenovateli zlomku dostaneme, že k!(n − k)! = (n − k)!(n − n + k)! = (n − k)!k!, což jsou shodné hodnoty. =
c) Vztah dokážeme pomocí vyjádření kombinačních čísel, které je uvedeno ve vztahu b). Je pak n k
!
!
+
1 n! n! n! 1 n = = + = + k+1 (n − k)!k! [n − (k + 1)]!(k + 1)! [n − (k + 1)]!k! n − k k + 1
n! n+1 (n + 1)! = · = = [n − (k + 1)]!(k + 1)! (n − k)(k + 1) [n − (k + 1)]!(k + 1)!
n+1 k+1
!
1.18. Poznámka: Pascalův trojúhelník. Vlastnost c) z věty nám umožní počítat hodnoty kombinačních čísel. Čísla se dají uspořádat do tzv. Pascalova trojúhelníku. Je z něj patrná jejich symetrie a následující jeho řádek dostaneme sčítáním dvou čísel z řádku předchozího. ! 0 0 ! ! 1 1 1 0 ! ! ! 2 2 2 1 2 0 ! ! ! ! 3 3 3 3 1 2 3 0 ! ! ! ! ! 4 4 4 4 4 1 2 3 4 0 ! ! ! ! ! ! 5 5 5 5 5 5 1 2 3 4 5 0 Po vyčíslení dostaneme pro kombinační čísla uvedené schema. V něm vidíme, že dolní řádek dostávame jako součty dvou prvků z horního řádku. To nám dovolí efektivně počítat hodnoty kombinačních čísel pro nízké hodnoty n a k. 1 1 1 1 1 1
2 3
4 5
1 1 3 6
10
1 4
10
1 5
1
1.19. Příklad: Janovská loterie. Z 90 čísel se losuje 5. Můžeme si koupit lístek, který obsahuje 1, 2, 3, 4 nebo 5 čísel. Lístek vyhrává, pokud obsahuje pouze čísla, která jsou mezi pěti vylosovanými. Na lístek s 1 číslem se vyplácí 15 krát cena lístku. V případě výhry s dvěma čísly (ambo) se vyplácí 270 krát cena lístku. Pro lístek s 3 čísly (terno) je výhra 5 500 krát cena lístku, pro lístek se 4 čísly (kvaterno) je výhra 75 000 krát cena lístku a pro lístek s 5 čísly (kvinterno) je výhra 1 000 000 krát cena lístku. Vypočtěte kolik je možných výsledků tahu a kolik z nich připadá na jednotlivé možnosti výher. Řešení: Při tahu vybíráme 5 čísel z 90 a na jejich pořadí nezáleží. Počet všech možností je počet všech 5-ti členných kombinací z 90 a podle vzorce (♥) je roven 6
90 5
!
=
90.89.88.87.86 = 4 394 268. 1.2.3.4.5
Pokud si koupíme lístek s jedním číslem, pak potřebujeme, aby se toto číslo shodovalo s některým z tažených. Ostatní 4 čísla mohou být libovolná. Ta se ale losují ze zbývajících 89 čísel ! a tedy je jejich počet roven 89.88.87.86 89 = = 2 441 626. 4 1.2.3.4 Poměr počtu šťastných lístků ku všem (pravděpodobnost výhry) je roven 89.88.87.86 1.2.3.4.5 5 1 · = = . 1.2.3.4 90.89.88.87.86 90 18 Lze tedy říci, že v průměru vyhrává každý 18-tý lístek, ale vyplácí se na něj výhra pouze v ceně 15 lístků. Pořadatel loterie si nechává cenu 3 lístků. Pro ostatní možnosti výher je tento poměr ve prospěch pořadatele ještě příznivější. V případě lístků se dvěma čísly musí být 2 čísla z 5 tažených. Zbývající 3 čísla jsou tažena z 88 ! čísel a jejich počet je tedy roven 88.87.86 88 = 109 736. = 3 1.2.3 Poměr počtu šťastných lístků ku všem (pravděpodobnost výhry) je roven 88.87.86 1.2.3.4.5 4.5 2 · = = . 1.2.3 90.89.88.87.86 90.89 801 Lze tedy říci, že v průměru vyhrává přibližně každý 400-tý lístek, ale vyplací se na něj výhra pouze v ceně 270 lístků. Pořadatel loterie si nechává cenu 130 lístků. Vypočtěte si poměry šťastných lístků a všech možností pro zbývající případy lístků se 3, 4 a 5 čísly. 3 4 5 [ 11748 ; 511038 ; 43949268 .] Poznámka: S kombinačními čísly se setkáme v pravděpodobnosti především v situacích, které odpovídají tzv. binomickému rozdělení. Obecnější případ multinomického rozdělení dostaneme, jestliže budeme uvažovat výběry při kterých budeme prvky rozmisťovat do přihrádek a nebude nás zajímat pořadí prvků. Kombinační číslo odpovídá situaci dvou přihrádek. Jedna, do které ukládáme vybírané prvky (k prvků) a druhá (původní), ve které zůstanou nevybrané prvky (n − k prvků). 1.20. Věta: Permutace s opakováním. Máme n různých prvků, které máme rozmístit do k, 1 ≤ k ≤ n přihrádek tak, že do m−té přihrádky umístíme nm prvků, přičemž n1 + n2 + . . . + nk = n. Potom je počet různých rozmístění prvků do přihrádek roven číslu n! (♥♥♥) . n1 !n2 ! . . . nk ! Důkaz: Při popsaném výběru musíme vyčerpat všechny prvky. Výběrem vlastně provádíme jejich permutaci. Jejich počet je podle vzorce (♠) roven n!. Pokud další permutaci získáme pouze výměnou prvků v některé s přihrádek, pak je to z pohledu rozdělování tentýž výběr. Takových permutací můžeme provést v m−té přihrádce nm !, 1 ≤ m ≤ k. Podle obecného pravidla kominatoriky je takových výměn celkem n1 !.n2 ! . . . nk !. Počet různých možných rozdělení prvků je roven poměru všech možností ku počtu shodných. To je ale uvedený vzorec. Všimneme si, že v případě dvou přihrádek je n1 = k, n2 = n − k a počet výběrů je dán kombinačním číslem.
7
Poznámka: Kombinace s opakováním. Uvažujeme výběr ze skupiny n druhů předmětů. Ptáme se kolik k−tic předmětů můžeme vybrat, když nepřihlížíme k pořadí ve skupině a za různé výběry se považují ty, které se liší alespoň v jednom předmětu. Počet takových výběrů je dán kombinačním číslem a mluvíme pak o kombinacích s opakováním. 1.21. Věta: Počet kombinací s opakováním. Počet k− kombinací s opakováním z n druhů předmětů je roven n+k−1 k
!
=
(n + k − 1)! . k!(n − 1)!
Důkaz: Vzorec odvodíme dvěma způsoby, které využíváme při řešení úloh, které odpovídají popsanému výběru. a) Nejprve si výběr popišme tak, že srovnáme prvky podle jednotlivých druhů. Výběr popíšeme pomocí symbolů z 0 a 1 tak, že píšeme tolik jedniček, kolik obsahuje výběr prvků určítého druhu a potom napíšeme nulu. Pokud výběr prvky některého druhu neobsahuje následují v zápise nuly za sebou. Např. Symbol 11010011101 znamená, že výběr obsahuje 2 prvky z 1. skupiny, jeden z 2., žádný ze 3., tři ze 4. a jeden z 5. skupiny. Je vidět, že zápis obsahuje k jedniček a n−1 nul. Jedničky odpovídají prvkům výběru a nuly oddělují jednotlivé druhy. Každému symbolu odpovídá jeden výběr a každý výběr je jednoznačně určen takovým symbolem. Počet výběrů je tedy roven počtu symbolů, které obsahují k jedniček a n − 1 nul. Ten je ale roven počtu permutací s opakováním kdy n + k − 1 prvků rozdělujeme do dvou skupin, které obsahují buď nuly a nebo jedničky. Podle vzorce (♥♥♥) je tento počet roven !
(n + k − 1)! n+k−1 n+k−1 . = = k k!(n − 1)! k![(n + k − 1) − k]! b) Jiný způsob odvození může odpovídat jiné modelové situaci. Uspořádejme výběr tak, že prvky stejného druhu jsou za sebou. Dostaneme tak posloupnost čísel 1, 2,. . .,k. Nyní k pořadovým číslům prvků z druhé skupiny přičteme 1, k pořadovým číslům prvků z třetí skupiny přičteme 2 a postupujeme tak dále až k pořadovým číslům poslední skupiny přičteme číslo n−1. Dostaneme tak vybranou rostoucí posloupnost k čísel z posloupnosti {1, 2, . . . , n+k−1}. Každá taková posloupnost odpovídá jednoznačně jednomu výběru požadované vlastnosti. Počet takových posloupností, tedy i výběrů, je roven počtu k−členných kombinací z n + k − 1 prvků, což je číslo ze vzorce ve větě. 1.22. Příklad: V cukrárně prodávají čtyři druhy zákusků, špičky, větrníky, věnečky a kremrole. Kolika způsoby lze nakoupit 8 zákusků. Řešení: Podle předchozích úvah se jedná o 8− členné kombinace s opakováním ze 4 prvků. Je tedy k = 8, n = 4 a n + k − 1 = 8 + 4 − 1 = 11. Jejich počet je roven kombinačnímu číslu n+k−1 k
!
=
11 8
!
=
11! 11.10.9 = = 165. 8!.3! 2.3
Poznámka: Výběry s podmínkami. V některých úlohách řešíme výběry za omezujících podmínek. Výběry jsme často popisovali pomocí posloupností z 0 a 1, kdy 0 znamená, že prvek není vybrán a 1 označuje výběr prvku. Řešme situaci takovou, že pokud z prvků v řadě jeden vybereme nesmíme již vybrat jeho souseda. Znamená to, že výběr je určen posloupností 0 a 1 takovou, že se v ní nevyskytnou dvě 1 za sebou. Hledejme kolik je takových výběrů. 1.23. Věta: Různých posloupností z 0 a 1, které obsahují n nul! a k jedniček, k ≤ n + 1, (n + 1)! n+1 a ve kterých nejsou žádné dvě jedničky za sebou je celkem = . k (n − k + 1)!k!
8
Důkaz: Podmínka k ≤ n + 1 je zřejmá. Pokud by bylo 1 více než 0 musí být alespoň dvě 1 za sebou. Zapišme si nyní 0 za sebou. Potom můžeme jednotlivé 1 umísťovat po jedné vždy před 0. Dostaneme n možností. Další možnost je, že můžeme 1 umístit za poslední 0. Je tedy k dispozici celkem n + 1 pozic, ze kterých vybíráme k míst. Jejich počet je roven počtu k−členných kombinací z n + 1 prvků, což je vzorec z věty. 1.24. Příklady k procvičování. 1. Příklad: Z města A do města B vede 5 různých cest, z města B do města C vedou 3 cesty a z města C do města D 2 cesty. Kolik různých cest vede z města A do města D. Řešení: Počet různých cest určíme z pravidla součinu. Je celkem 5.3.2=30 cest. 2. Příklad: Kolika způsoby lze vybrat jednu souhlásku a jednu samohlásku ze slova lavice a ze slova statistika. Řešení: Ve slově lavice jsou 3 různé souhlásky a 3 různé samohlásky. Podle pravidla součinu je tedy 3.3=9 možných výběrů. Ve slově statistika jsou 2 různé samohlásky a 3 různé souhlásky. Je tedy celkem 2.3=6 výběrů. 3. Příklad: Kolika způsoby je možné vybrat na šachovnici dvě pole tak, aby platilo: a) pole jsou různá; b) pole mají různou barvu; c) pole neleží v jedné vertikále a ani v jedné horizontále; d) splní podmínku z c) a mají různou barvu. Řešení: a) Šachovnice má celkem 64 polí, tudíž podle pravidla součinu je 64.63=4 032 možností výběru. (2-členné variace bez opakování z 64 prvků.) b) Šachovnice má 32 polí bíle barvy a 32 polí černé barvy. Podle pravidla součinu je celkem 32.32=1 024 možností. c) První pole vybereme ze všech 64 polí. Pro výběr druhého vynecháme ze šachovnice 1 sloupec a 1 řádek. Zbyde nám čtverec, který má 7 krát 7, tedy 49 polí. Podle pravidla součinu je celkem 64.49=3 136 možností. d) První pole vybereme ze všech 64 polí. Pro výběr druhého vynecháme ze šachovnice 1 sloupec a 1 řádek. Zbyde nám čtverec, který má 7 krát 7, tedy 49 polí. Z těchto polí je ale pouze 24 polí druhé barvy než jsme zvolili poprvé. Podle pravidla součinu je celkem 64.24=1 536 možností. 4. Příklad: Kolik různých čtyřciferných čísel je možné napsat pomocí číslic 0, 1, 2,. . ., 9 tak, aby: a) číslo nezačínalo 0; b) číslo nezačínalo 0 a všechny cifry byly rozdílné. Řešení: Použijeme pravidlo o součinu. a) První cifru můžeme vybrat 9 způsoby (není dovolena 0) a každou další 10 způsoby. Je tedy celkem 9.10.10.10= 9 000 různých čísel. b) První cifru můžeme vybrat 9 způsoby (není dovolena 0), druhou také 9 způsoby (přidáme 0 a vynecháme použitou cifru), třetí 8 a čtvrtou 7 způsoby (vždy v dalším kroku vynecháme použité cifry). Je celkem 9.9.8.7=4 536 různých čísel. 9
5. Příklad: Jeden člověk má 6 detektivek a druhý má 8 historických románů. Kolika způsoby si mohou vyměnit a) po jedné knize;
b) po dvou knihách.
Řešení: Použijeme pravidlo součinu. Při výměně jedné knihy má první 6 možností a druhý 8. Celkem je tedy 6.8=48 možných výměn. V ! ! případě výměny dvou knih má 6.5 8.7 6 8 první = = 15 možností a druhý má = = 28 možností. Je tedy 2 2 1.2 1.2 celkem 15.28=420 možností různých výměn. 6. Příklad: Ze souboru 52 karet vybereme 10. Kolik je možností, že ve vybrané skupině je: a) alespoň jedno eso; Řešení: Je celkem
52 10
b) právě dvě esa. !
=
52! = 15 820 024 220 možností všech výběrů. Z nich je 10!.42!
!
48! 48 = = 6 540 715 896 těch, které neobsahují žádné eso,neboť musíme vybrat 10 10!.38! 10 karet ze 48. Je tedy 15 820 024 220 − 6 540 715 896 = 9 279 308 324 možností, kdy je ve výběru alespoň jedno eso. !
!
4.3 48! 48 4 · = Právě dvě esa můžeme vybrat celkem · = 2 264 093 964 způ8 2 1.2 8!.40! soby. Vybíráme totiž 2 esa ze 4 a 8 karet ze zbývajících 48. 7. Příklad: Máme k dispozici 7 různých korálků, které navlékneme na šnůru a dostaneme náhrdelník. Kolik různých náhrdelníků můžeme sestavit. Řešení: Náhrdelník je určen pořadím korálků. Různých pořadí 7 korálků je tolik, kolik je jejich permutací, tedy 7!=5 040. Ale ty permutace, které dostaneme pootočením určí stejný náhrdelník. Ke každé permutaci takto získáme ještě 6 dalších, tedy celkem 7 permutací vždy určí týž náhrdelník. Je tedy počet náhrdelníků roven 7!7 = 6! = 720. Když si ale takový náhrdelník nakreslíme, vidíme, že jej můžeme převrátit kolem svislé osy a dostaneme nhrdelník, který odpovídá jiné permutaci korálků. Bude tedy celkový počet náhrdelníků poloviční, tudíž je roven 360. 8. Příklad: Kolika způsoby můžeme rozestavit 8 věží na šachovnici. Řešení: Jediné omezení v této úloze je, že na poli smí být postavena nejvýše jedna věž. Znamená to, že ze ! 64 polí jich vybíráme 8. Počet je roven počtu 8-členných kombinací 64.63.62.61.60.59.58.57 64 ze 64, tudíž = = 4 426 165 368. 8 8! 9. Příklad: Na šachovnici máme rozestavit 8 věží tak, aby se navzájem neohrožovaly. Kolik je takových možností. Řešení: Ze zadání úlohy vyplývá, že v každém sloupci a každém řádku smí být postavena jediná věž. Jestliže očíslujeme řádky a sloupce od 1 do 8, třeba z levého dolního rohu doprava a nahoru, pak je postavení věže v každém sloupci určeno číslem řádku, tedy dvojicí (k, ak ), k = 1, 2, . . . , 8 a čísla {a1 , a2 , . . . , a8 } jsou permutací čísel 1,2,. . .,8. 10
Každá z permutací určí jedno dovolené postavení věží a jejich počet je tedy roven počtu všech permutací 8 prvků, tudíž je 8!=40 320 možností. 10. Příklad: Ve sportce se losuje 6 čísel ze 49 a potom ještě jedno číslo premiové. Výhra 1. pořadí znamená uhodnout všechna tažená čísla a výhra 2. pořadí vyžaduje uhádnout prvních 6 čísel. Vypočtěte kolik je všech možností losovaných čísel. Kolik je mezi nimi těch, které odpovídají výhře 2. pořadí. Řešení: V první části tahu vybíráme 6 čísel ze 49 a nezáleží na pořadí. Jejich počet je tedy rovem počtu 6-členných kombinací ze 49, tudíž 49 6
!
=
49.48.47.46.45.44 = 13 983 816 6!
Ty odpovídají výhře 2. pořadí. Pro 1. pořadí ještě volíme další číslo a pro tuto volbu máme k dispozi 43 zbývajících čísel. Všech možností je tedy 43.13 983 816 = 601 304 088.
11. Příklad: Krotitel šelem přivádí do manéže 5 lvů a 4 tygry. Kolika způsoby je může seřadit, jestliže nesmí jít dva tygři za sebou. Řešení: Úloha je podobná úloze o výběrech s podmínkami, ale zde záleží na pořadí zvířat, která jsou rozlišitelná. Způsob řešení je ale shodný jako u počtu posloupností z 0 a 1. Nejprve seřadíme lvy a to můžeme udělat celem 5!=120 způsoby. Nyní můžeme umístit tygra vždy po jednou před lvy, tedy je 5 možností a další místo je za posledním lvem. Máme celkem 6 míst pro 4 tygry. Protože jsou od sebe rozlišitelní, záleží tedy na pořadí a počet možných výběrů je počet 4− členných variací ze 6. Ten je roven 6.5.4.3=360. Podle pravidla o součinu je celkový počet možností jak seřadit šelmy roven 120.3604=43 200. 12. Příklad: Na dvoře krále Artuše sedí u kulatého stolu 12 rytířů. Každý z nich má 2 nepřátele a ti jsou u stolu jeho sousedy. Na výpravu k záchraně lady Ginervy je třeba vybrat 5 rytířů tak, aby mezi nimi nebyli nepřátelé. Kolik je možností výběru. Řešení: Úloha je podobná předchozí, liší se v tom, že rytíři nejsou v řadě, ale sedí v kruhu a v tom, že nezáleží na pořadí v jakém rytíře do skupiny vybereme. Řešení provedeme tak, že kruh na jednom místě přetrhneme. Mezi rytíři je nejvíce ctěn sir Lancelot. Pro výběr máme dvě možnosti. Ve skupině je sir Lancelot, nebo není. 1. ve skupině je sir Lancelot. Potom tam nesmí být jeho oba sousedé. Zbývá nám vybrat ! 6.5.4.3 6 4 rytíře ze skupiny 9 zbývajících. To lze udělat celkem = = 15 způsoby. 4 1.2.3.4 Je celkem 9 rytířů, 4 vybereme a 5 ne. Označíme-li vybrané 1 a nevybrané 0, je počet výběrů roven počtu posloupností ze čtyř 1 a pěti 0 takových, že v ní nejsou dvě 1 za sebou. Podle odstavce o výběrech z podmínkami je těchto možností uvedený počet. 2. ve skupině není sir Lancelot. Pak ho z řady vynecháme a zůstane nám ! 11 rytířů v řadě, 7.6.5.4.3 7 ze kterých jich 5 vybíráme. Obdobně jako v 1. případě dostaneme = = 21 5 1.2.3.4.5 možností výběrů. Je zde pět 1 a šest 0. Celkový počet výběrů je tedy 15+21=36.
11
