Kapitola 8 Kombinatorika 8.1 Opakování z přednášky kombinatorické pravidlo součtu počty vzájemně vylučujících se možností se sčítají kombinatorické pravidlo součinu počty nezávislých a současně se vyskytujících možností se mezi sebou násobí permutace počet bijekcí 𝑛-prvkové množiny do sebe je 𝑛! kombinace počet výběrů 𝑘 prvků z 𝑛 prvků (𝑘-prvkových podmnožin 𝑛-prvkové množiny) je (︃ 𝑛 𝑘 )︃ := 𝑛! 𝑘!(𝑛 − 𝑘)! = 𝑛 · (𝑛 − 1) · · · · · (𝑛 − 𝑘 + 1) 𝑘! variace počet pořadí 𝑘 prvků z 𝑛 prvků (uspořádaných 𝑘-tic z 𝑛-prvkové množiny) můžeme získat jako počet výběrů 𝑘 prvků z 𝑛 prvků krát počet (dobrých) uspořádání 𝑘 prvků, tedy jako (︃ 𝑛 𝑘 )︃ · 𝑘! = 𝑛 · (𝑛 − 1) · · · · · (𝑛 − 𝑘 + 1) permutace s opakováním prvků různých druhů máme-li 𝑝1 prvků prvního druhu, 𝑝2 prvků druhého druhu, . . . , 𝑝 𝑘 prvků 𝑘-tého druhu, pak počet permutací 𝑝1 + 𝑝2 + + · · · + 𝑝 𝑘 prvků s opakováním prvků daných druhů je (𝑝1 + 𝑝2 + · · · + 𝑝 𝑘)! 𝑝1! · 𝑝2! · · · · · 𝑝 𝑘! variace s opakováním počet pořadí 𝑘 prvků z 𝑛 prvků s opakováním je 𝑛 𝑘 kombinace s opakováním počet kombinací 𝑘 prvků z 𝑛 prvků s opakováním odpovídá ekvivalentně 52 • počtu rozdělení 𝑘 stejných prvků do 𝑛 krabiček, • počtu rozmístění 𝑛 − 1 oddělovačů mezi lineárně seřazených 𝑘 stejných prvků • počtu permutací 𝑘 + 𝑛 − 1 prvků a oddělovačů s opakováním 𝑘 prvků a 𝑛 − 1 oddělovačů přičemž počet posledních je (𝑘 + 𝑛 − 1)! 𝑘!(𝑛 − 1)! = (︃ 𝑘 + 𝑛 − 1 𝑘 )︃ = (︃ 𝑘 + 𝑛 − 1 𝑛 − 1 )︃ 8.2 Příklady řešené na cvičení Příklad 8.1. Určete počet řešení rovnice 𝑥 + 𝑦 + 𝑧 = 2 024 v N0, respektive v N. Řešení. Nejprve úlohu řešíme nad N0. Máme 2 025 možností pro 𝑥 (𝑥 = 0, 1, . . . , 2 024). Pro každou z těchto možností máme 2024 − 𝑥 + 1 možností pro 𝑦 (𝑦 = 0, 1, . . . , 2024 − 𝑥). Každá z těchto dvojic 𝑥 a 𝑦 jednoznačně určuje 𝑧 = 2024 − 𝑥 − 𝑦. Stačí tedy sečíst přes všechny možnosti pro 𝑥 možnosti pro 𝑦 v závislosti na 𝑥. 2 024∑︁ 𝑥=0 (2 025 − 𝑥) = 2 025 · 2 025 − 2 024∑︁ 𝑥=0 𝑥 = 2 025 · 2 025 − 2 025 · 2 024 2 = = 2 025 · (2 025 − 1 012) = 2 025 · 1 013 = 2 051 325. Můžeme si rovněž zapsat číslo 2 024 jako součet dvou tisíc dvaceti čtyř jedniček. 2 024 = 1 + 1 + · · · + 1⏟ ⏞ 2 024 Následně se ptáme, kolik z nich přináleží 𝑥, kolik 𝑦 a kolik 𝑧. Hledáme tedy, kolika způsoby je možné rozdělit 2 024 stejných prvků na tři hromádky. Jedná se tedy o kombinace s opakováním, počet možností je tedy (︃ 2 024 + 2 2 )︃ = (︃ 2 026 2 )︃ = 2 026 · 2 025 2 = 2 051 325. Řešíme-li rovnici v N, musí být 𝑥, 𝑦 i 𝑧 minimálně 1. Můžeme si tedy zavést nové proměnné 𝑥0 := 𝑥 − 1, 𝑦0 := 𝑦 − 1 a 𝑧0 := 𝑧 − 1, které již budou z N0. Po vyjádření si proměnné 𝑥0, 𝑦0 a 𝑧0 dosadíme do původní rovnice a dostaneme 𝑥0 + 1 + 𝑦0 + 1 + 𝑧0 + 1 = 2 024 53 neboli 𝑥0 + 𝑦0 + 𝑧0 = 2 021, přičemž počet řešení nové rovnice je stejný jako počet řešení původní rovnice – ke každé proměnné bychom přičetli 1. Například druhým způsobem řešení pak dospějeme k počtu řešení (︁ 2 021+2 2 )︁ = (︁ 2 023 2 )︁ = 2 045 253. △ Příklad 8.2. Kolika způsoby můžeme zapsat číslo 22 500 000 jako a) součin dvou přirozených čísel; b) součin tří přirozených čísel? Řešení. Hledáme vlastně počet řešení rovnice 𝑥 · 𝑦 = 22 500 000, resp. 𝑥 · 𝑦 · 𝑧 = 22 500 000 v N. Nejprve si určíme prvočíselný rozklad 22 500 000. Celkem snadno máme 22 500 000 = 225 · 100 000 = 152 · 105 = 32 · 52 · 25 · 55 = 25 · 32 · 57 . Řešíme nejprve a). Vzhledem k tomu, že 𝑦 = 22 500 000 𝑥 je jednoznačně určené 𝑥, zajímá nás počet 𝑥 takových, že 𝑥 dělí 22 500 000, tedy počet dělitelů tohoto čísla. Napíšeme si 𝑥 = 2 𝑎 · 3 𝑏 · 5 𝑐 . Pak mohou být 𝑎 ∈ {0, 1, . . . , 5}, 𝑏 ∈ {0, 1, 2} a 𝑐 ∈ {0, 1, . . . , 7}. Máme tedy 6 možností pro 𝑎, 3 možnosti pro 𝑏 a 8 možností pro 𝑐. Volby jsou na sobě nezávislé, celkem máme tedy 6 · 3 · 8 = 144 možností pro 𝑥 a celkem 48 řešení. Jinak se na úlohu můžeme dívat tak, že zvlášť dělíme 5 dvojek, 2 trojky a 7 pětek na dvě hromádky (jedna pro 𝑥 a jedna pro 𝑦). Rozdělení dvojek, trojek a pětek jsou na sobě nezávislá. Máme tedy tři nezávislé kombinace s opakováním, tedy počet řešení je (︃ 5 + 1 1 )︃ · (︃ 2 + 1 1 )︃ · (︃ 7 + 1 1 )︃ = 6 · 3 · 8 = 144. Nyní řešíme b), již pouze druhou možností (je jednodušší). Dělíme 5 dvojek, 2 trojky a 7 pětek zvlášť na tři hromádky (pro 𝑥, 𝑦 a 𝑧), jedná se tedy opět o tři nezávislé kombinace s opakováním, počet řešení b) je (︃ 5 + 2 2 )︃ · (︃ 2 + 2 2 )︃ · (︃ 7 + 2 2 )︃ = (︃ 7 2 )︃ · (︃ 4 2 )︃ · (︃ 9 2 )︃ = 21 · 6 · 36 = 4 536. △ Poznámka. Pokud bychom řešili úlohu až na pořadí činitelů, zkomplikovala by se. V a) by stačilo vydělit počet řešení dvěma (počet permutací dvouprvkové množiny). 22 500 000 není druhá mocnina, takže počet dělitelů je sudý, a dělitele jde spárovat tak, že součin dá vždy kýžené číslo. Až na pořadí tedy lze číslo 22 500 000 zapsat jako součin dvou 72 různými způsoby. Pro druhou mocninu by byl počet dělitelů lichý – pak bychom odečetli 1 (pro příslušnou odmocninu), vydělili dvěma (párování dělitelů) a zase bychom 1 přičetli. Část b) by již byla složitější. Museli bychom uvažovat šestiprvkovou grupu permutací tříprvkové množiny. Ač 4 536 je dělitelné šesti, nestačí pouze výsledek vydělit. Museli bychom použít Burnsideovo lemma. Pro každou permutaci bychom určili počet fixních bodů, tedy počet trojic 𝑥, 𝑦, 𝑧, které se zobrazí samy na sebe. Následně bychom počty sečetli a na závěr vydělili 6. 54 Příklad 8.3. Kamarádi Artem, Barbora, Cyril, Danuše a Ervín jdou spolu do kina. V kině si sednou do řady vedle sebe. Kolika způsoby si mohou posedat, pokud chtějí, aby a) Barbora seděla vedle Cyrila; b) Danuše neseděla vedle Artema; c) nastaly možnosti a) i b) současně? Řešení. Označíme si osoby A, B, C, D a E. V a) můžeme uvažovat B a C za jednu osobu a pak výsledek vynásobit dvěma – B a C se mohou vždy prohodit. Zbývají 4 „osoby“ (tři osoby a jedna dvojice), které můžeme libovolně permutovat. Máme tedy 2 · 4! = 2 · 24 = 48 možností. V b) můžeme zjistit počet všech rozesazení a odečíst počet možností, kdy A a D sedí vedle sebe. Máme 5! − 2 · 4! = 120 − 48 = 72 možností. Úlohu c) řešíme podobně jako b) s tím, že zároveň B a C považujeme za jednu osobu. Permutujeme 4 „osoby“ s tím, že odečítáme 2 · 3! možností, kdy A a D sedí vedle sebe. Celkem máme 2 · (4! − 2 · 3!) = 2 · (24 − 12) = 2 · 12 = 24 možností. △ Příklad 8.4. a) Kolika způsoby se může rozesadit 5 osob v pětimístném autě, když jen dva lidé mají řidičský průkaz? b) V autobuse je vedle místa pro řidiče ještě 25 míst k sezení. Kolika způsoby se může rozesadit 20 cestujících a 2 řidiči? Řešení. a) Nejprve posadíme jednoho řidiče. Následně máme 4! = 24 možností, jak se rozesadí zbytek osazenstva. Pro každou možnost můžeme prohodit řidiče, máme tedy celkem 48 možností. Jinak lze úlohu řešit tak, že máme 2 možnosti, kdo si sedne na místo řidiče, pak 4 možnosti, kdo na místo spolujezdce a na zadním sedadle máme postupně 3, 2 a 1 možnost. Výsledek vynásobíme, máme tedy 2 · 4 · 3 · 2 · 1 = 48 možností. b) Máme 2 možnosti, kdo si sedne na místo řidiče. Druhý řidič má 25 možností k sezení, první cestující 24, druhý 23, atd., přičemž poslední, dvacátý, cestující má 5 volných sedadel. Máme tedy celkem 2 · 25 · 24 · · · · · 6 · 5 možností. Druhý způsob řešení je nejprve vybrat 21 sedadel pro cestující (pro 20 cestujících a druhého řidiče), to je možné (︁ 25 21 )︁ způsoby, následně pro každý výběr sedadel máme 21! rozesazení, a pro každé rozesazení navíc dvě možnosti (prohazujeme řidiče). Celkový počet možností je tedy 2 · (︃ 25 21 )︃ · 21! = 2 · 25! 21! · 4! · 21! = 25! 4 · 3 . △ Příklad 8.5. Výsledné pořadí týmů první ligy se ztratilo, našlo se pouze relativní pořadí všech sedmi týmů z Čech a relativní pořadí všech šesti týmů z Moravy. Kolika způsoby lze 55 z těchto částečných údajů sestavit pořadí první ligy? Kolika způsoby by to bylo možné, pokud by se první ligy účastnily ještě tři týmy ze Slezska, jejichž relativní pořadí také známe? Řešení. Pořadí týmů z Čech je známé, stejně jako pořadí týmů z Moravy. Při určování celkových pořadí nás tedy pouze zajímá, jestli je tým na daném místě z Čech, nebo z Moravy. Určujeme proto počet možností, jak mezi sebe týmy seřadit. Pokud si například představíme týmy z Čech jako prvky a týmy z Moravy jako oddělovače, začíná úloha připomínat kombinace s opakováním. Máme tedy (︁ 7+6 6 )︁ = (︁ 13 6 )︁ = 1 716 možností. Jinak lze úlohu chápat tak, že určujeme počet permutací třináctiprvkové množiny, přičemž za stejné považujeme ty permutace, kde prohazujeme mezi sebou týmy z Čech a mezi sebou týmy z Moravy. Pak vyjde 13! 7!·6! možností, což je totéž, co (︁ 13 6 )︁ = (︁ 13 7 )︁ . Přidáme-li týmy ze Slezska, již první způsob (který je vlastně ekvivalentní s druhým) nevede na kombinační číslo. Počet řešení je podebně (7 + 6 + 3)! 7! · 6! · 3! = 16! 7! · 6! · 3! = 960 960. △ 56