1. k o m b I n a t o r I k a

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ěpodobnost-

vý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 za-

bý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 mo-

delový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 pod-

mí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 libovol-

nou 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 po-

stupně 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 n

k

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 = n

k

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 2

32

= 4 294 967 296. Skupina musí tedy obsahovat alespoň 2

32

+ 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

2

1

+ 2

2

+ 2

3

+ 2

4

+ 2

5

+ 2

6

= 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 10

3

= 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 (♥)

n.(n − 1) . . . (n − k + 1)

k!

k−členných

kombinací z n prvků.

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

=

n

n

= 1,

n

1

= n;

b)

n

k

=

n

n − k

=

n!

(n − k)! k!

;

c)

n

k

+

n

k + 1

=

n + 1

k + 1

,

k < n.

Důkaz: a) Kombinační číslo

n

0

= 1 podle definice.

Hodnoty kombinačních čísel dostaneme jestliže do vztahu (♥♥) dosadíme za k postupně

hodnoty k = n a k = 1. Je

n

n

=

n(n − 1) . . . (n − n + 1)

n!

=

n!

n!

= 1;

n

1

=

n − 1 + 1

1

= n.

b) Úpravou vzorce (♥♥) dostaneme

n

k

=

n(n − 1) . . . (n − k + 1)

k!

=

5

=

n(n − 1) . . . (n − k + 1)

k!

·

(n − k)(n − k − 1) . . . 1

(n − k)(n − k − 1) . . . 1

=

n!

k!(n − k)!

.

Jestliže v tomto vztahu dosadíme za k hodnotu n − k, pak ve jmenovateli zlomku dosta-

neme, ž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

+

n

k + 1

=

n!

(n − k)!k!

+

n!

[n − (k + 1)]!(k + 1)!

=

n!

[n − (k + 1)]!k!

1

n − k

+

1

k + 1

=

=

n!

[n − (k + 1)]!(k + 1)!

·

n + 1

(n − k)(k + 1)

=

(n + 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 hod-

noty 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řed-

chozího.

0

0

1

0

1

1

2

0

2

1

2

2

3

0

3

1

3

2

3

3

4

0

4

1

4

2

4

3

4

4

5

0

5

1

5

2

5

3

5

4

5

5

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

2

1

1

3

3

1

1

4

6

4

1

1

5

10

10

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

1.2.3.4.5

= 4 394 268.

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

4

=

89.88.87.86

1.2.3.4

= 2 441 626.

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

·

1.2.3.4.5

90.89.88.87.86

=

5

90

=

1

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

3

=

88.87.86

1.2.3

= 109 736.

Poměr počtu šťastných lístků ku všem (pravděpodobnost výhry) je roven

88.87.86

1.2.3

·

1.2.3.4.5

90.89.88.87.86

=

4.5

90.89

=

2

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

11748

;

4

511038

;

5

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í do-

staneme, 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 n

m

prvků, přičemž

n

1

+ n

2

+ . . . + n

k

= n. Potom je počet různých rozmístění prvků do přihrádek roven číslu

(♥♥♥)

n!

n

1

!n

2

! . . . n

k

!

.

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 n

m

!, 1 ≤ m ≤ k. Podle obec-

ného pravidla kominatoriky je takových výměn celkem n

1

!.n

2

! . . . n

k

!. 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 n

1

= k, n

2

= 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řed-

mě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)!

k!(n − 1)!

=

n + k − 1

k![(n + k − 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!

8!.3!

=

11.10.9

2.3

= 165.

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,

a ve kterých nejsou žádné dvě jedničky za sebou je celkem

n + 1

k

=

(n + 1)!

(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á

první

6

2

=

6.5

1.2

= 15 možností a druhý má

8

2

=

8.7

1.2

= 28 možností. Je tedy

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;

b) právě dvě esa.

Řešení: Je celkem

52

10

=

52!

10!.42!

= 15 820 024 220 možností všech výběrů. Z nich je

48

10

=

48!

10!.38!

= 6 540 715 896 těch, které neobsahují žádné eso,neboť musíme vybrat

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.

Právě dvě esa můžeme vybrat celkem

4

2

·

48

8

=

4.3

1.2

·

48!

8!.40!

= 2 264 093 964 způ-

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í

ze 64, tudíž

64

8

=

64.63.62.61.60.59.58.57

8!

= 4 426 165 368.

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, a

k

), k = 1, 2, . . . , 8 a čísla {a

1

, a

2

, . . . , a

8

} 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

6!

= 13 983 816

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

4 rytíře ze skupiny 9 zbývajících. To lze udělat celkem

6

4

=

6.5.4.3

1.2.3.4

= 15 způsoby.

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ě,

ze kterých jich 5 vybíráme. Obdobně jako v 1. případě dostaneme

7

5

=

7.6.5.4.3

1.2.3.4.5

= 21

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