1. přednáška KOMBINATORIKA
Při řešení mnoha praktických problémů se setkáváme s úlohami, ve kterých utváříme skupiny z prvků nějaké konečné množiny. Například máme sestavit rozvrh hodin z daných předmětů, potřebujeme rozhodnout, které týmy budou v turnaji hrát proti sobě, nebo chceme rozdat několik druhů cen mezi účastníky závodu. Řešením těchto úloh se zabývá kombinatorika. Kombinatorika je tedy obor matematiky, který se zabývá uspořádáním daných prvků podle určitých pravidel do určitých skupin. Základním pojmem v kombinatorice je pojem (k-prvková) skupina, nebo také k-tice prvků, kde k je přirozené číslo. S náznaky kombinatoriky se setkáváme již u starořeckých matematiků. Počátky hlubšího studia otázek spojených s kombinatorikou však spadají do období 16. století. Zájem o kombinatoriku podnítily v té době různé hazardní hry, například vrchcáby neboli hra v kostky. Matematici se začali zabývat otázkami, jaká možná seskupení mohou nastat při házení určitého počtu hracích kostek, jaké jsou pravděpodobnosti výher, později i jinými otázkami, a tak se postupně vyvíjel obor, který v současné době nalézá uplatnění v teorii pravděpodobnosti, v teorii informací, ve statistice a v dalších oborech.
Základními větami kombinatoriky jsou tzv. kombinatorické pravidlo součtu a kombinatorické pravidlo součinu: Věta (pravidlo součinu): Počet všech uspořádaných k-tic (dvojic, trojic,...), 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 × n 2 × ... × n k .
Příklad: Při cestě z Ostravy do Tábora (přes Prahu) lze použít tyto dopravní prostředky: Ostrava - Praha: autobus, vlak, letadlo, auto Praha - Tábor: autobus, vlak, auto. Kolika možnými způsoby se dostaneme z Ostravy do Tábora? Řešení: Je zřejmé, že z Ostravy se do Prahy dostaneme pomocí 4 dopravních prostředků a z Prahy do Tábora lze využít 3 možností. Ke každé cestě do Prahy máme 3 možnosti v pokračování. Je tedy celkem 4 × 3 = 12 možností, jak cestovat z Ostravy do Prahy.
1
Poznámka: Kombinatorické pravidlo součinu můžeme použít také v případě, kdy několikrát (k-krát) opakujeme výběr z určitých prvků a zajímá nás, kolik různých pořadí může vzniknout. Např. když házíme mincí, jde o opakovaný výběr ze dvou prvků (orel, panna). Po třech hodech může vniknout 2 × 2 × 2 = 8 různých výsledků.
Věta (pravidlo součtu): Mějme konečné množiny A1, A2, ... , Ak, které mají po řadě n1, n2, ..., nk prvků. Jsou-li každé dvě množiny navzájem disjunktní, tzn. neobsahují žádný společný prvek, pak počet prvků množiny A1 È A 2 È K A k je roven n1 + n2 + K nk . Příklad: Určete počet všech přirozených dvojciferných čísel, v jejichž dekadickém zápisu se každá číslice vyskytuje nejvýše jednou. Řešení: Všechna přirozená dvojciferná čísla můžeme rozdělit do dvou disjunktních skupin tak, že v první jsou dvojciferná čísla s různými číslicemi a ve druhé dvojciferná čísla se stejnými číslicemi. Počet všech dvojciferných čísel je 90, počet dvojciferných čísel se stejnými číslicemi je 9 (jsou to čísla 11, 22, …, 99). Označíme-li hledaný počet dvojciferných čísel s různými číslicemi x, pak platí:x + 9 = 90. Odtud dostáváme, že x = 81.
Kombinatorika tedy zkoumá skupiny (podmnožiny) prvků vybraných z jisté základní množiny. 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: Uspořádaný výběr (variace) - záleží na pořadí prvků Například: Kolik trojciferných čísel můžeme sestavit z cifer 2; 4; 8? Číslo 248 a 482 považujeme za 2 různé výběry => záleží na pořadí cifer. Neuspořádaný výběr (kombinace) - nezáleží na pořadí prvků Například: Kolik je možností při vsázení Sportky? Vždy zaškrtnu 7 čísel ze 49, ale volba {1; 5; 25; 34; 12; 19; 21} je shodná z volbou {1; 25; 5; 12; 34; 19; 21} => nezáleží na pořadí v jakém čísla škrtám Druhým kritériem je, zda se prvky po výběru do původní množiny vracejí či nikoliv. Podle toho výběry rozlišujeme na:
Výběry s opakováním - vybraný prvek se vrací do původní množiny 2
Například: Z cifer {1;2} můžeme sestavit tato dvojciferná čísla {11; 12; 21; 22}. V 11 se opakuje prvek 1 - po prvním výběru se vrátila do množiny možných cifer. Výběry bez opakování - vybraný prvek se nevrací do původní množiny Například: Kolika způsoby lze seřadit 8 sprinterů na startovní čáru. Po výběru prvního sprintera už budeme dalšího vybírat pouze ze 7 (vybraného již nemůžeme použít), atd.. Matematicky je jednodušší popis výběru s opakováním, avšak v praxi se častěji setkáváme s výběry bez opakování (test není možno opakovat se stejným vzorkem, např. tažnost trubky lze testovat pouze jednou, pro další test se musí použít další trubka). 1) VARIACE bez opakování Definice: k-členná variace z n prvků ( 0 < k £ n ) je uspořádaná k-tice sestavená tak, že každý prvek se v ní vyskytuje nejvýše jednou. Značíme ji Vk (n) - variační číslo.
Věta : Počet variací Vk (n) je roven: Vk (n) = n × (n - 1) × (n - 2) × ... × (n - k + 1) =
n! . (n - k )!
Poznámka: Symbol n! čteme "n faktoriál" a pro každé přirozené číslo n definujeme: n!= 1 × 2 × 3 × ... × (n - 1) × n a 0!= 1 . Příklad: Členové správní rady hokejového klubu volí prezidenta, viceprezidenta a revizora účtů klubu. Určete, kolik existuje způsobů, jak mohou být tyto funkce obsazeny, víme-li, že členů rady je 8, do funkcí lze volit pouze členy správní rady a žádný člen nemůže zastávat více než jednu funkci. Řešení: Máme dvě možnosti řešení: a) Pomocí kombinatorického pravidla součinu: Předpokládejme, že nejdříve se volí prezident klubu. Je zřejmé, že budeme vybírat z 8. Následuje volba viceprezidenta. Počet možností, jak ji provést, je již 7 (prezident už tuto funkci vykonávat nemůže). Při poslední volbě revizora připadá do úvahy 6 možných kandidátů => možností je celkem: 8 × 7 × 6 = 336 b) Uvědomíme si, že vlastně vybíráme trojici (k=3) z 8 lidí (n=8). Lidé se nemohou opakovat (jedna osoba nemůže zastávat více funkcí) a záleží na tom, v jakém pořadí vybíráme (není jedno, zda jsem prezident nebo viceprezident) => záleží na pořadí a prvky se neopakují => jde o tříčlenné variace z osmi prvků bez opakování. 8! 8 × 7 × ... × 1 Máme tedy V3 (8) = = = 8 × 7 × 6 = 336 možností, jak obsadit funkce. (8 - 3)! 5 × 4 × ... × 1 2) PERMUTACE bez opakování
3
Permutace je zvláštní případ variace, kde k = n. To znamená, že ze zadaných prvků postupně vybereme všechny. Každá permutace tedy odpovídá nějakému pořadí zadaných prvků: každý prvek se v pořadí musí objevit, ale žádný tam nemůže být dvakrát. U permutací tedy v podstatě nejde o výběr, ale o různá uspořádání dané množiny. Definice: Permutace z n prvků je uspořádaná n-tice sestavená tak, že každý prvek se v ní vyskytuje právě jednou. Značíme ji P (n) .
Věta : Počet permutací P (n) je roven: P ( n ) = Vn ( n) =
n! n! = = n!. (n - n)! 0!
Příklad: Kolika způsoby lze seřadit 8 sprinterů na startovní čáru? Řešení: Tvoříme osmice z 8 (k=8, n=8), záleží na pořadí a jeden sprinter nemůže být na dvou pozicích (prvky se neopakují) => variace bez opakování, kde k = n, tj. hledáme počet permutací z 8 prvků. Existuje tedy P (8) = 8!= 40320 možností, jak seřadit 8 sprinterů na startovní čáru. 3) VARIACE s opakováním Definice: k-členná variace s opakováním z n prvků je uspořádaná k-tice sestavená tak, že každý prvek se v ní vyskytuje nejvýše k-krát. Značíme ji Vk¢ (n) . Věta : Počet variací s opakováním Vk¢ (n) je roven: Vk¢ (n) = n k .
Poznámka: Pokaždé vybírám ze všech prvků a podle kombinatorického pravidla součinu tedy existuje n × n × ... × n (celkem se n opakuje k-krát). Příklad: Určete, kolik čtyřciferných přirozených čísel lze sestavit z cifer 1,2,3 a kolik jich je menších než 3 000. Řešení: V prvním případě hledám čtveřice ze tří prvků (musí se opakovat) a číslo 1231 není stejné s číslem 1123 (záleží na pořadí) => variace s opakováním (k=4, n=3). Počet všech čtyřciferných přirozených čísel je: V4¢ (3) = 3 4 = 81 Pro určení, kolik z těchto 81 čísel je menších jak 3 000 si stačí uvědomit, že na pozici tisíců může být pouze 1 nebo 2 (máme 2 možnosti) a pak už hledáme trojice ze všech prvků (pokaždé 3 možnosti) => použitím pravidla o součinu dostáváme: 2 ×V3¢(3) = 2 × 33 = 54 čísel.
4
4) PERMUTACE s opakováním
Definice: Permutace s opakováním je uspořádaná n-tice z k různých prvků, v níž se každý prvek ni -krát opakuje ( i = 1,..., k ). Značíme ji Pn¢1 ,...,nk .
Věta : Počet permutací s opakováním je roven: Pn¢1 ,...,nk =
n! . n1!×n 2 !×... × n k !
Poznámka: Počet opakování jednotlivých prvků označujeme n1 ,..., n k a musí platit, že n1 + ... + n k = n .
Příklad: Určete, kolika způsoby je možné srovnat do řady 2 šedé, 3 modré a 4 černé kostky. Řešení: Máme 3 prvky (šedá, modrá a černá kostka), kde první prvek se vyskytuje 2-krát ( n1 = 2 ), druhý 3-krát ( n2 = 3 ) a třetí 4-krát ( n3 = 4 ), tj. máme celkem 9 prvků (n=9). Musíme použít všechny, tzn. budeme sestavovat 9-tice z 9 - záleží na pořadí a musí se opakovat. Existuje P2¢,3, 4 =
9! = 1260 způsobů, jak dané kostky srovnat do řady. 2!×3!×4!
5) KOMBINACE bez opakování Definice: k-členná kombinace z n prvků ( 1 £ k £ n ) je neuspořádaná k-tice sestavená tak, že každý prvek se v ní vyskytuje nejvýše jednou. Značíme ji C k (n) - kombinační číslo.
Věta : Počet kombinací C k (n) je roven: ænö n! C k (n) = çç ÷÷ = . è k ø (n - k )!k! ænö Poznámka: çç ÷÷ tedy nazýváme kombinační číslo a čteme n nad k. èk ø ænö ænö ænö ænö æ n ö ÷÷ Platí: çç ÷÷ = çç ÷÷ = 1 , çç ÷÷ = n a çç ÷÷ = çç è0ø ènø è1ø èk ø èn - k ø
Příklad: Na výtah, do něhož můžou nastoupit nejvýše 2 osoby, čeká 6 osob.
5
a) Kolik je možností, jak vybrat 2 osoby, kteří pojedou? b) Kolik je možností, jak vybrat 4 osoby, které nepojedou? Řešení: a) Tvoříme dvojice ze šesti prvků, přičemž nezáleží na pořadí (Mirek s Janou je to samé co Jana s Mirkem) a nemohou se opakovat => kombinace bez opakování (n=6 a k=2) æ 6ö 6! 6 × 5 × 4! Máme celkem C 2 (6) = çç ÷÷ = = = 15 možností, jak mohou lidé nastoupit. 4!×2 è 2 ø (6 - 2)!2!
b) Vybíráme čtveřice ze 6 osob (k=4 a n=6) - opět nezáleží na pořadí a osoby se nemohou opakovat: æ 6ö 6! 6 × 5 × 4! Máme celkem C 4 (6) = çç ÷÷ = = = 15 možností, jak vybrat osoby, které 2!×4! è 4 ø (6 - 4)!4! nenastoupí.
Je vidět, že počet možností, jak vybrat 2, kteří pojedou je stejný jako počet možností, jak ænö æ n ö ÷÷ ). vybrat 4, kteří zůstanou čekat (ilustruje platnost vlastnosti çç ÷÷ = çç èk ø èn - k ø 6) KOMBINACE s opakováním Definice: k-členná kombinace s opakováním z n prvků je neuspořádaná k-tice sestavená tak, že každý prvek se v ní vyskytuje nejvýše k-krát. Značíme ji C k¢ (n) . Věta : Počet kombinací C k¢ (n) je roven: æ n + k - 1ö (n + k - 1)! ÷÷ = C k¢ (n) = çç . è k ø (n - 1)!k!
Příklad: V cukrárně prodávají čtyři druhy zákusků. Kolika způsoby lze nakoupit 8 zákusků? Řešení: Nezáleží na pořadí a prvky se musí opakovat => 8-členné kombinace ze 4 prvků s opakováním æ 4 + 8 - 1ö 11! 11 × 10 × 9 × 8! ÷÷ = Existuje C8¢ (4) = çç = = 165 možností, jak zákusky vybereme. 6 × 8! è 8 ø 3!×8!
6
Shrnutí:
7
