1. KOMBINATORIKA Kombinatorika je obor matematiky, který zkoumá skupiny prvků vybíraných z jisté základní množiny. Tyto skupiny dělíme jednak podle toho, zda u nich záleží nebo nezáleží na pořadí zastoupených prvků (rozlišujeme tak skupiny nazývané permutace, variace a kombinace), a dále podle toho, zda se prvky v jednotlivých skupinách mohou či nemohou opakovat (skupiny pak nazýváme s opakováním nebo bez opakování). Příklad 1.1: Mějme množinu A a, b, c. Urči počet všech a) uspořádaných trojic, b) uspořádaných dvojic, c) dvojic prvků množiny A, ve kterých se žádný z prvků neopakuje, d) uspořádaných dvojic, e) dvojic prvků množiny A, ve kterých se může opakovat každý z prvků, f) uspořádaných pětic množiny B a, a, b, b, b. Řešení: a) (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)
…6
b) (a, b), (a, c), (b, a), (b, c), (c, a), (c, b)
…6
c) (a, b), (a, c), (b, c)
…3
d) (a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)
…9
e) (a, a), (a, b), (a, c), (b, b), (b, c), (c, c)
…6
f) (a, a, b, b, b), (a, b, a, b, b), (a, b, b, a, b), (a, b, b, b, a), (b, a, a, b, b),
(b, a, b, a, b), (b, a, b, b, a), (b, b, a, a, b), (b, b, a, b, a), (b, b, b, a, a)
…10
Při určování počtu vytvářených k-tic (dvojic, trojic, ...) se řídíme základními větami kombinatoriky, kterým jsou kombinatorické pravidlo součtu a kombinatorické pravidlo součinu: Věta 1.1: (kombinatorické pravidlo součinu) Počet všech uspořádaných k-tic (dvojic, trojic, ...), jejichž první člen lze vybrat n1 způsoby, druhý člen n2 způsoby atd. až k-tý člen nk způsoby, je roven n1 n2 ... nk . Příklad 1.2: Při cestě z Ostravy do Tábora (přes Prahu) lze použít tyto dopravní prostředky: 1
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í: Z Ostravy se do Prahy dostaneme pomocí 4 dopravních prostředků a z Prahy do Tábora pomocí 3. Ke každé cestě do Prahy máme 3 možnosti, jak pokračovat do Tábora, je tedy celkem 4 3 12 možností, jak cestovat z Ostravy do Prahy. Věta 1.2: (kombinatorické 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 A2 ... Ak je roven n1 n2 ... nk . Příklad 1.3: Urči počet všech přirozených dvojciferných čísel, v jejichž dekadickém zápisu se každá číslice vyskytuje nejvýš 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. Obr.1.1:
1) PERMUTACE (z n prvků) - jsou uspořádané n-tice vytvářené z n prvků (uspořádané, tzn. záleží na pořadí) a) bez opakování: P(n) n! - viz Příklad 1.1 a) - základní množina, jejíž uspořádání měníme, má n různých prvků - umisťuji n prvků na n pozic: na 1. místo mám n možností, na 2. místo (n-1) možností … , na (n-1). místo 2 možnosti a na n-té místo 1 možnost n (n 1) (n 2) ... 2 1 n! Poznámka: Označení n! používáme pro faktoriál přirozeného čísla n. Zápis n! čteme „n faktoriál“ a pro každé přirozené číslo n jej definujeme jako n! 1 2 3 ... (n 1) n . Dále je definováno 0! 1.
2
Příklad 1.4: Kolika způsoby lze seřadit 8 sprinterů na startovní čáru? Řešení: Tvoříme uspořádané osmice z 8 prvků. Měníme-li pořadí prvků celé skupiny, vytváříme permutace. Jejich počet je dán vzorcem P(n) n! , existuje tedy P(8) 8! 40320 možností, jak seřadit 8 sprinterů na startovní čáru. b) s opakováním: P (n)
n! n1!n2 !... nk !
- viz Příklad 1.1 f) - základní množina, jejíž uspořádání měníme, má n prvků, existuje v ní však k skupin nerozlišitelných prvků, jejichž počty jsou n1 , n2 ,..., nk Příklad 1.5: Kolik různých čísel lze vytvořit užitím všech cifer čísla 112 218 251? Řešení: Tvoříme uspořádané devítice z 9 prvků, vytváříme tedy permutace. Jelikož ale množina obsahuje skupiny nerozlišitelných prvků (jednotlivé jedničky od sebe nerozlišujeme, protože jejich záměnou nedostáváme nové číslo, stejně tak nerozlišujeme jednotlivé dvojky), 9! jedná se o permutace s opakováním, jejichž počet je P (9) 2520 . Užitím všech 4!3!1!1! zadaných cifer lze tedy vytvořit 2520 různých čísel.
2) VARIACE (k-té třídy z n prvků) - jsou uspořádané k-tice vytvářené z n prvků (uspořádané, tzn. záleží na pořadí) a) bez opakování: Vk (n)
n! (n k )!
- viz Příklad 1.1 b) - základní množina má n různých prvků, ze kterých tvoříme uspořádané k-tice, ve kterých se žádný z prvků nesmí opakovat - umisťuji k prvků na k pozic: na 1. místo mám n možností, na 2. místo (n-1) možností … , n! na k-té místo (n (k 1)) n k 1 možností n (n 1) (n 2) ... (n k 1) (n k )! Příklad 1.6: Na startu běžeckého závodu je 8 atletů. Kolika způsoby mohou být obsazeny stupně vítězů? Řešení: Na obsazení první pozice máme celkem 8 možností. Ke každé této možnosti máme 7 možností na obsazení pozice druhé a ke každé dvojici na prvních dvou místech připadá v 8! úvahu 6 závodníků, kteří mohou obsadit pozici třetí. Je tedy celkem 8 7 6 (8 3)! V3 (8) 336 možností, jak mohou být na konci závodu obsazeny stupně vítězů. b) s opakováním Vk (n) n k
3
- viz Příklad 1.1 d) - základní množina má n různých prvků, ze kterých tvoříme uspořádané k-tice, ve kterých se každý z prvků může libovolně opakovat - umisťuji k prvků z n možných na k pozic: na 1. místo mám n možností, na 2. místo také n možností (prvky se mohou opakovat) …, na k-té místo rovněž n možností n n ... n n k Příklad 1.7: Urči počet všech možných pěticiferných kódů. Řešení: Když náhodně volím pěticiferný kód, vybírám na každou pozici jednu cifru z deseti možných. Počet všech možných pěticiferných kódů je tedy 10 10 10 10 10 105 V5 (10) 100 000 .
3) KOMBINACE (k-té třídy z n prvků) - jsou k-tice vytvářené z n prvků, u kterých nezáleží na pořadí
n a) bez opakování: Ck (n) k - viz Příklad 1.1 c) - základní množina má n různých prvků, ze kterých vybíráme k-tice, ve kterých nezáleží na tom, v jakém pořadí jsou prvky uspořádány. Žádný z prvků se v k-tici nesmí opakovat. n! - vycházím z variací bez opakování, těch je . U variací záleží na pořadí, je jich proto (n k )! k! -krát víc než kombinací (každou k-tici lze uspořádat k! způsoby) zlomek dělím k! n n Poznámka: Označení používáme pro kombinační číslo. Zápis čteme „n nad k“ a k k n n! pro každou dvojici přirozených čísel n a k jej definujeme jako . Je snadné k (n k )!k! n n n n n . dokázat, že 1 , n a 1 k n k 0 n Příklad 1.8: Na výtah, do něhož můžou nastoupit nejvýše 2 osoby, čeká 6 osob. a) Kolik je možností, jak vybrat 2 osoby, které výtahem pojedou? b) Kolik je možností, jak vybrat 4 osoby, které výtahem nepojedou? Řešení: a) Tvoříme dvojice ze šesti prvků, přičemž nezáleží na pořadí (pojede-li Mirek s Janou, je to totéž, jako když pojede Jana s Mirkem) a jednotlivé prvky se nemohou se opakovat (nemohu do výtahu umístit jednu osobu dvakrát). Jedná se tedy o kombinace bez opakování, kde n = 6 6 6! 6 5 4! 15 . Existuje tedy 15 možností, jak a k = 2. Jejich počet je C 2 (6) 4!2 2 (6 2)!2! vybrat 2 osoby, které výtahem pojedou.
4
b) Vybíráme čtveřice z 6 osob, opět jde o výběr bez opakování, kde nezáleží na pořadí. Jedná 6 6! 6 5 4! se tedy o kombinace 4. třídy z 6 prvků a těch je C 4 (6) 15 . 2!4! 4 (6 4)!4! Možností, jak vybrat 4 osoby, které nenastoupí, je celkem 15. Vidíme, že počet možností, jak vybrat 2 osoby, které výtahem pojedou, je stejný, jako počet n n ). možností výběru 4 osob, které zůstanou čekat (ilustruje platnost vlastnosti k n k
n k 1 b) s opakováním: Ck (n) k - viz Příklad 1.1 e) - základní množina má n různých prvků, ze kterých vybíráme k-tice, ve kterých nezáleží na tom, v jakém pořadí jsou prvky uspořádány. Každý z prvků se přitom v k-tici může libovolně opakovat. Příklad 1.9: V cukrárně prodávají 10 druhů zákusků. Kolika způsoby lze objednat 8 zákusků? Řešení: Vybírám 8 prvků z 10 možných, přičemž v provedeném výběru nezáleží na pořadí (když zákusky přeskládám, nepovažuji to za odlišný nákup) a prvky se mohou opakovat (milovníci šlehačky si koupí 8 kremrolí). Jedná se tedy o kombinace 8. třídy z 10 prvků 10 8 1 17! 17 16 ... 10 9! s opakováním, a těch je C8 (10) 24310 . 8 9!8! 9!8!
5
Příklady k procvičení: 1. 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 žák c seděl na kraji? 2. Kolik různých přesmyček lze vytvořit použitím všech písmen slova a) STATISTIKA, b) MATEMATIKA? 3. Na hokejovém turnaji o 8 družstvech se hraje systémem „každý s každým“. Kolik zápasů bude celkem odehráno? 4. Deset přátel si vzájemně poslalo pohlednice z prázdnin. Kolik pohlednic celkem rozeslali? 5. Kolik prvků obsahuje množina všech pěticiferných přirozených čísel? 6. V prodejně nabízí 7 druhů pohlednic. Kolika způsoby lze koupit a) 10 pohlednic, b) 5 pohlednic, c) 5 různých pohlednic? 7. Kolik různých hodů můžeme provést a) dvěma kostkami, b) třemi kostkami? 8. Ve třídě je 12 chlapců a 15 dívek. Kolika způsoby lze vybrat pětici dětí, která se zúčastní přivítání zahraniční delegace, mají-li v ní být zastoupeny 3 dívky a 2 chlapci? 9. Urči počet všech možných trojciferných kódů, ve kterých se cifry a) nemohou opakovat, a) mohou opakovat. 10. Kolika způsoby lze rozesadit 8 studentů k 8 různým počítačům? 11. V knihkupectví prodávají 10 titulů knižních novinek. Kolika způsoby lze koupit a) 4 novinky, b) 5 různých novinek? 12. Student má v knihovně 4 různé učebnice pružnosti, 3 různé učebnice matematiky a 2 různé učebnice fyziky. Kolika způsoby je lze seřadit, mají-li zůstat učebnice jednotlivých předmětů vedle sebe? 13. Kolik různých čísel lze vytvořit užitím všech cifer čísla a) 1 115 251, b) 283 388?
6
