Kombinatorika V tomto tématu se budeme zabývat určováním počtu skupin, které jsou sestaveny z prvků dané konečné množiny; budeme přitom rozlišovat, zda tyto skupiny jsou uspořádané nebo neuspořádané, tj. zda v nich na pořadí jejich prvků záleží nebo nezáleží. O tuto problematiku se kombinatorika zajímala zejména v době svého vzniku v 17. století, který je spojován se jmény B.Pascala, P. de Fermata, J. Bernoulliho, G. W. Leibnize aL. Eulera. Současná kombinatorika však řeší problémy mnohem obecnější a její metody a výsledky se uplatňují v řadě důležitých odvětví vědy, techniky, ekonomie a dalších. 2.1 Základní kombinatorická pravidla Počet výběr «2, Slova „p pro určit Toto pra místech Nejprve si ukážeme některé důležité způsoby řešení kombinatorických úloh. A» Z místa A do místa B vedou tři turistické cesty, z místa B do místa C dvě. Turista chce dojít z místa A přes B do C. Kolik má pro celkovou trasu svého výletu možností? Obr. 2.1 Řešení: Označme podle obr. 2.1 cesty z místa A do B písmeny a, b, c, cesty z B do C písmeny x, y a každou možnou celkovou trasu turistova výletu zapišme jako uspořádanou dvojici, jejímž prvním členem je cesta z A do B, druhým členem cesta z B do C. Dostaneme tak těchto šest možných tras splňujících danou podmínku: (a,x), (a,y), (b,x), (b,y), (c,x), (c,y). K tomu, abychom určili hledaný počet tras, tj. počet uspořádaných dvojic splňujících dané podmínky, není však vůbec nutné vypisovat všechny možnosti - stačí totiž následující úvaha: Ke každé ze tří cest z A do B si turista může vybrat jednu ze dvou cest z B do C, takže z A do C přes B může jít 3 ■ 2 způsoby. Celkový počet tras, po nichž může turista svůj výlet uskutečnit, je roven součinu 3 ■ 2, tj. číslu 6. 64 2. Kombinatorika 2.1 základ Hledali jsme počet uspořádaných dvojic, u nichž pro výběr prvního členu byly tři možnosti (cesty a, b, c) a pro výběr druhého členu po výběru prvního dvě možnosti (cesty x, y). Jak jsme dostali počet těchto uspořádaných dvojic? Tak, že jsme počty těchto možností vynásobili, tj. určili součin 3-2 = 6. Takto lze postupovat nejen v případě uspořádaných dvojic. Tento způsob určování počtu uspořádaných A:-tic se nazývá kombinatorické pravidlo součinu: Počet všech uspořádaných k-ůc, jejichž první člen lze vybrat n\ způsoby a pro výběr každého dalšího členu je po výběru všech předcházejících členů postupně n.2, n$.....n/c možností, je roven součinu n \ ■«? • m -... ■«/(. Slova „po výběru všech předcházejících členů" jsou důležitá v případě, že výběr pro určité místo uspořádané k-úct ovlivňuje počet výběrů pro místa následující. Toto pravidlo se však dá použít i v případech, kdy výběry členů na jednotlivých místech uspořádané k-úce, jsou na sobě nezávislé. Kolik je trojciferných přirozených čísel, v jejichž dekadickém zápisu se každá z deseti číslic vyskytuje nejvýše jednou? řešení: Každé trojciferné přirozené číslo je uspořádaná trojice, jejíž první člen lze vybrat devíti způsoby (na prvním místě nemůže být nula); po jeho výběru lze druhý člen vybrat rovněž devíti způsoby (na druhém místě už nula být může, ale nemůže tam být číslice, která byla vybrána pro místo první); třetí člen lze po výběru předchozích dvou členů vybrat už jen osmi způsoby. Počet trojciferných přirozených čísel splňujících danou podmínku je tedy roven součinu 9-9-8, tj. číslu 648. Při řešení následující úlohy kombinatorické pravidlo součinu nepoužijeme; na způsobu jejího řešení si vysvětlíme kombinatorické pravidlo součtu. Kolik je trojciferných přirozených čísel, v jejichž dekadickém zápisu se vyskytují právě dvě stejné číslice? řešení: Pro každé trojciferné číslo nastává jediná z následujících možností: a) v jeho zápisu je každá číslice nejvýše jednou - těchto čísel podle výsledku úlohy v B je 648; b) v jeho zápisu jsou právě dvě stejné číslice - počet těchto čísel, který máme určit, označíme p; c) v jeho zápisu jsou všechny tři číslice stejné - těchto čísel je devět - jsou to čísla 111,222, ...,999. Vzhledem k tomu, že všech trojciferných čísel je 900 (čísla 100 až 999), plyne odtud: 900 = 648 + /? + 9, p = 900-648-9, p = 243. 2.1 základní kombinatorická pravidla 65 Množinu všech trojciferných čísel jsme rozložili na tři disjunktní podmnožiny a usoudili jsme, že celkový počet těchto čísel je roven součtu počtů čísel v těchto jednotlivých podmnožinách. Zobecněním uvedené úvahy je věta, která se nazývá kombinatorické pravidlo součtu: Lze-li konečnou množinu A rozložit na n disjunktních podmnožin, které mají p\. p2, pn prvků, je počet prvků množiny A roven p\ + P2 H-----Vpn. Určete počet všech čtverců, jejichž strany leží na přímkách čtvercové sítě, která podle obr. 2.2 pokrývá obdélník ABCD s rozměry \AB\ = 4 cm, \AD\ - 3 cm. D Di_Ci C S, S2 s3 $4 S5 Se A A, Bi B Obr. 2.2 Řešení: Čtverce v této síti mají strany o délkách 1 cm nebo 2 cm nebo 3 cm. Množinu všech těchto čtverců rozložíme do tří disjunktních podmnožin. Čtverců o délce strany 1 cm je zřejmě 4 • 3 = 12, čtverců o délce strany 2 cm je šest (neboť jejich středy jsou body S\, ..., počet čtverců o délce strany 3 cm je roven dvěma (jsou to čtverce AB\C\D a A\BCD\). Celkový počet čtverců v dané síti je tedy roven součtu 12 + 6 + 2 = 20. Před řešením úlohy v části E si připomeneme, že tenisové turnaje se obvykle hrají systémem na jednu porážku: Z hráčů jsou s ohledem na výkonnost sestaveny dvojice, které se utkají v prvním kole, vítěz postoupí do dalšího kola, kde se utká s vítězným hráčem z jiné dvojice, poražený z turnaje vypadává. Počet hráčů se tak po sehrání všech utkání prvního kola zmenší na polovinu, po sehrání druhého kola se zmenší na čtvrtinu, a tak se postupuje dále, až se v posledním kole, ve finále, utkají zbývající dva hráči, kteří v předchozích kolech neprohráli. Je zřejmé, že počet hráčů, kteří nastoupí do prvního kola, musí být roven mocnině dvou; je-li přihlášen jiný počet hráčů, musí ti, kteří jsou na tenisovém žebříčku nejníže, projít kvalifikací. Určete celkový počet utkání, která budou sehrána v tenisovém turnaji, do něhož se přihlásilo n hráčů. 66 2. Kombinatorika Řešení: Všimněme si, že mezi všemi utkáními turnaje a mezi všemi hráči, kteří během turnaje prohráli, je tento vztah: Každému utkání turnaje odpovídá jediný hráč - ten, který v tomto utkání prohrál. Každému hráči, který v turnaji prohrál, odpovídá jediné utkání - to, v němž prohrál. Tento vztah je znázorněn na obr. 2.3, kde A značí množinu všech utkání turnaje a B množinu všech hráčů, kteří v turnaji prohráli. A protože, jak je z tohoto obrázku vidět, každému prvku množiny A odpovídá právě jeden prvek množiny B a obráceně, mají obě množiny stejný počet prvků. Počet hráčů, kteří v turnaji prohráli, však známe - je jich celkem n— 1, neboť prohráli všichni až na vítězného finalistu. Znamená to, že také počet všech utkání sehraných v turnaji je n— 1. Obr. 2.3 Obecně platí: Jestliže prvky konečných množin A, B lze na sebe zobrazit tak, že každému prvku množiny A odpovídá právě jeden prvek množiny B a obráceně, mají obě množiny stejný počet prvků. Pro řešení některých kombinatorických úloh je užitečné znát tzv. přihrádkový princip: Je-li počet předmětů rozmístěných do n přihrádek větší než n, jsou aspoň v jedné přihrádce aspoň dva předměty. 2.1 základní kombinatorická pravidla 67 Pro ilustraci použijeme tento princip při řešení jednoduché úlohy, kde ukážeme, že mezi každými čtyřmi sty osobami jsou vždy aspoň dvě, které mají narozeniny ve stejný den. Mysleme si, že máme 366 přihrádek a že do první umístíme všechny osoby narozené 1. ledna, do druhé všechny narozené 2. ledna,..., do šedesáté všechny narozené 29. února a tak dále až do poslední, která má pořadové číslo 366, umístíme všechny osoby narozené 31. prosince. Protože rozmísťovaných osob je více než přihrádek, jsou podle přihrádkového principu aspoň v jedné přihrádce aspoň dvě osoby. A protože tyto osoby jsou ve stejné přihrádce, mají narozeniny ve stejný den. Cvičení WtM Z místa A vede do místa B pět cest, z B do C tři cesty, z C do D čtyři cesty. Určete, kolika způsoby může turista dojít z místa A do místa D, chce-li se cestou zastavit v B i v C. Kolika způsoby se může vrátit z D do A, nechce-li jít zpět po žádné z cest, po kterých šel z A do D? M Překladatelská firma potřebuje slovníky pro překlad z češtiny, angličtiny, ruštiny, němčiny a francouzštiny do každého z těchto jazyků. Určete, jaký nejmenší počet slovníků musí mít k dispozici. gcg Určete počet všech čtyřciferných přirozených čísel, v jejichž dekadickém zápisu není nula a každá ze zbývajících cifer je v něm nejvýše jednou. Kolika způsoby lze z políček šachovnice 8x8 vybrat dvě políčka různé barvy, která a) neleží ve stejném řádku, b) neleží ve stejném řádku ani ve stejném sloupci? ÍUiM Hlavní město Švambránie má 500 000 obyvatel, žádný z nich nemá na hlavě více než 500000 vlasů. Je jisté, že mezi těmito obyvateli jsou určitě dva, kteří mají stejný počet vlasů? 2.2 Permutace V tomto článku se budeme zabývat úlohami souvisejícími s počtem způsobů, kterými se dá vedle sebe nebo za sebou seřadit n daných prvků. Ptejme se například: Kolika způsoby se na čtyřmístnou lavici letního kina mohou posadit čtyři diváci? Úlohu vyřešíme nejprve tak, že vypíšeme všechny možnosti; tento způsob se dá sice použít pro konečný počet diváků vždy, ale při jejich velkém počtu bude časově velmi B8 2. Kombinatorika náročný. Označíme-li jednotlivé diváky A, B, C, D, je pro jejich rozsazení na čtyřmístné lavici těchto 24 možností: (A, B, C, D), (A, B, D, C), (A, C, B, D), (A, C, D, B), (A, D, B, C), (A, D, C, B), (B, A, C, D), (B, A, D, C), (B, C, A, D), (B, C, D, A), (B, D, A, C), (B, D, C, A), (C, A, B, D), (C, A, D, B), (C, B, A, D), (C, B, D, A), (C, D, A, B), (C, D, B, A), (D, A, B, C), (D, A, C, B), (D, B, A, C), (D, B, C, A), (D, C, A, B), (D, C, B, A). Zajímáme-li se však pouze o počet těchto způsobů a uvědomíme-li si, že se jedná o počet uspořádaných čtveřic sestavených ze čtyř prvků, můžeme použít kombinatorické pravidlo součinu: První člen lze vybrat čtyřmi způsoby, po jeho výběru lze druhý člen vybrat třemi způsoby, pro výběr třetího členu po výběru druhého jsou dvě možnosti a čtvrtý člen po výběru třetího už má pouze jedinou možnost. Všech rozsazení čtyř diváků na čtyřmístnou lavici je tedy 4 ■ 3 • 2 ■ 1 =24. Uspořádané čtveřice ze čtyř prvků z předcházející ilustrační úlohy se nazývají permutace, přesněji řečeno permutace ze čtyř prvků. Obecně definujeme: Permutace z n prvků je uspořádaná n-tice sestavená z těchto n prvků tak, že každý je v ní právě jednou. Kolik je permutací z n prvků? Odpověď získáme podobným způsobem jako v úloze z A, a to užitím kombinatorického pravidla součinu: První člen uspořádané n-tice lze vybrat n způsoby a pro výběr každého dalšího členu je po výběru všech předcházejících členů postupně n-1, n-2, n-3,..., 2, 1 možností. Počet permutací z n prvků je proto roven součinu n • (« — 1) • (»—2) •,.. • 3 ■ 2 • 1. Pro součin všech přirozených čísel od jedné do n se zavádí symbol ni, který čteme n-faktoriál: ra! = 1 -2-3 •... ■(n-X)-n. Pro úplnost uveďme, že pro číslo nula se definuje 0! = 1; zdůvodníme si to později. Například: 0! = 1,11 = 1,2! = 1- 2 = 2, 31 = 1- 2- 3 = 6, 4! = 1- 2- 3- 4 = 24 atd. Výsledek, k němuž jsme v předcházejícím textu dospěli, vyslovíme užitím faktoriálu takto: Pro počet P(n) všech permutací z n prvku platí: l'(n) = n\. Určete, kolika způsoby může při nástupu, kterým se zahajuje volejbalový turnaj, nastoupit n hráčů a) do řady, v níž hráč A stojí na prvním místě, b) do řady, ve které hráči A, B nestojí vedle sebe. 2 2 Pfrmi itapf 69 řešení: a) Počet řad sestavených z n hráčů, v nichž hráč A stojí na prvním místě, je roven počtu způsobů, kterými se vedle něho může seřadit zbývajících n- 1 hráčů. Počet řad s hráčem A na prvním místě je tedy roven («- 1)!. b) Určíme nejprve počet řad, ve kterých hráči A, B stojí vedle sebe, a to tak, že hráč A má hráče B po své pravici. Považujeme-li oba tyto hráče zajediného, máme seřadit jen n — 1 hráčů, což lze provést (n— 1)! způsoby. Ke stejnému výsledku dojdeme, má-li hráč A hráče B po své levici. Odtud plyne, že počet řad, v nichž hráči A a B stojí vedle sebe, je roven 2 • (n— 1)!. O hledaném počtu řad, v nichž hráči A, B vedle sebe nestojí, už snadno usoudíme, že je roven rozdílu n\ -2 • (n — 1)!. Petr chce na poličku postavit vedle sebe pět různých učebnic a čtyři různé romány. Určete, kolika způsoby to může udělat, chce-li, aby a) všechny romány byly vedle sebe, b) všechny učebnice byly vedle sebe, c) všechny učebnice i všechny romány byly vedle sebe. řešení: a) Považujeme-li všechny čtyři romány za knihu jedinou, můžeme ji společně s pěti učebnicemi postavit na poličku 6! způsoby. Protože však v uvedené „knize" se čtyři romány, které ji tvoří, dají uspořádat 4! způsoby, je celkový počet způsobů, jak splnit dané podmínky, dán součinem 6!4!. b) Podobnou úvahou jako v a) si jistě sami zdůvodníte, že celkový počet způsobů je v tomto případě roven součinu 5 !5!. c) Pro umístění všech učebnic na levém kraji poličky a všech románů na jejím kraji pravém, je celkem 5!4! možností. Protože však všechny učebnice mohou být i na kraji pravém a všechny romány na kraji levém, je počet všech rozmístění, v nichž jsou všechny učebnice i všechny romány vedle sebe, roven 2 • 5!4!. Určete počet všech pěticiferných přirozených čísel dělitelných šesti, v jejichž zápisu se vyskytuje každá z číslic 0, 1,2, 5, 7. řešení: Všechna pěticiferná přirozená čísla, v jejichž zápisu je každá z uvedených číslic, jsou dělitelná třemi, neboť jejich ciferný součet je 15. Aby byla dělitelná šesti, musí být dělitelná i dvěma. Dělitelná dvěma jsou však právě ta čísla, která končí nulou, anebo která končí dvojkou a nezačínají nulou. Počet čísel, která končí nulou, je 4!; počet těch, která končí dvojkou a nezačínají nulou, je 4! - 3! (od počtu těch, která končí dvojkou, jsou odečtena ta, která končí dvojkou a nulou začínají). Hledaný počet čísel dané vlastnosti je tedy 4!+(4! - 3!) = 2 • 4! - 3!. Úpravy výrazů obsahujících laktoriály Tyto úpravy jsou založeny na tom, že výraz n\ = n • (n - ľ) ■ (n—2) ■... ■ 3 ■ 2 • 1 se dá vyjádřit také takto: n\ =h.(n- I )!=/;•(«- !)•(»-2)! =/;•(« - 1)0; -2)-... -(n-k+Din-k)'.. 70 2. Kombinatorika Upravte výrazy: a) 10!-3-8! + 2-9!, b) i^i-^—, c) —i- + i, »! (n - ľ)! (n + 2): h! Řešení: a) Protože je 10! = 10-9-8!a2-9!=2-9-8!, vytkneme z daného výrazu 8! a dostaneme: 10!-3-81 + 2-9! = 8! (10 -9-3+2 -9) = 105-8!. b) Protože je (n+ľ)\ = (n+\)n\ a n\ = n(n- 1)!, zkrátíme v prvním zlomku n!, ve druhém (n— 1)! a dostaneme, že daný výraz je roven (n+ t)-h = 1. c) Po převedení daného součtu obou zlomků na společného jmenovatele, kterým je výraz (n+2)! = (h+2)(b+ 1)m!, dostaneme: l ^ 1 l + (n + 2)(n+l) _ ra2 + 3n + 3 («+2)! n\ (n + 2)! (« + 2)! Cvičení | Určete, kolika způsoby se na šestimístnou lavici může posadit šest spolužáků, jestliže jeden z nich nechce sedět na kraji. Určete, kolika způsoby může nastoupit do zástupu sedm hochů a pět dívek tak, aby nejdříve stály všechny dívky a za nimi všichni chlapci. Kolik musí být prvků, aby při zvětšení jejich počtu o dva se počet permutací zvětšil třicetkrát? Určete počet pěticiferných přirozených čísel, v jejichž zápisu je každá z číslic 1, 3, 5, 7, 9 a která jsou větší než 59 731. Upravte výrazy n\ (n+1)! (n+1)!-; (n+1)! (n2-4)' "' (n-1) a) 3 -10!-6 -11! +9 -12!, b) —- ' n! (n + 3)\ JN (n+iy.-n-nl 2.3 Variace V předcházejícím článku jsme se vždy zajímali o počet uspořádaných w-tic, které každý z daných n prvků obsahovaly právě jednou. Nyní se budeme zabývat situacemi, ve kterých z daných n prvků budou sestavovány nikoli n-tice, ale uspořádané &-tice, kde k < n. AKolika způsoby může být trojmístná lavice letního kina obsazena třemi ze čtyř zájemců? Podobně jako v úvodní úloze předcházejícího článku všechny možnosti nejprve vypíšeme. Označíme-li A, B, C, D zájemce o místa na trojmístné lavici, jsou pro jejich rozsazení tyto možnosti: 2.3 Variace 71 (A, B, C), (A, C, B), (B, A, C), (B, C, A), (C, A, B), (C, B, A), (A, B, D), (A, D, B), (B, A, D), (B, D, A), (D, A, B), (D, B, A), (A, C, D), (A, D, C), (C, D, A), (C, A, D), (D, A, C), (D, C, A), (B, C, D), (B, D, C), (C, B, D), (C, D, B), (D, B, C), (D, C, B). Jak už bylo uvedeno, není určování počtu všech možností jejich výčtem příliš efektivní. Uvědomíme-li si však, že v úloze se jedná o počet uspořádaných trojic sestavených ze čtyř prvků, můžeme tento počet určit rychleji pomocí kombinatorického pravidla součinu: Pro první člen této trojice jsou čtyři možnosti, pro druhý jsou po výběru prvního tři možnosti a pro třetí člen po výběru předchozího máme celkem dvě možnosti. Počet možných obsazení trojmístné lavice čtyřmi zájemci je tedy roven součinu 4-3-2 = 24. Uspořádané trojice sestavené ze čtyř prvků tak, že každý se v nich vyskytuje nejvýše jednou (tj. jen jednou nebo vůbec ne), se nazývají variace, přesněji řečeno trojčlenné variace ze čtyř prvků. Obecně definujeme: Uspořádaná fc-tice sestavená /. daných prvků tak. že každý je v ní nejvýše jednou, se nazývá Á-členná variace z n prvků. Aby bylo možné sestavit ä-člennou skupinu. \ níž je každý /. daných prvků nejvýše jednou, musí být k < n; pro k > n takové skupiny neexistují! Všimněte si dále. že permutace jsou zvláštním případem variací, a to pro k = n: //-členná variace z daných n prvků a permutace z těchto « prvků představují tutéž uspořádanou //-tici. Místo o variacích se také hovoří o variacích bez opakování. Zdůrazňuje se tím, že v těchto variacích žádný prvek není obsažen vícekrát, tj. že se neopakuje. Podobným způsobem jako při zjišťování počtu trojčlenných variací ze čtyř prvků v předešlé úloze určíme nyní počet /c-členných variací z n prvků obecně. Sestavujeme-li z daných n prvků uspořádanou k-ůci, máme pro výběr jejího prvního členu n možností - může to být libovolný z n daných prvků; po jeho výběru máme pro druhý člen této k-ůce jen (n — 1) možností, protože na tomto místě nemůže být prvek vybraný pro místo první. Pro třetí člen máme po výběru předchozího členu (n-2) možností, pro čtvrtý člen po výběru třetího je (n—3) možností a tak dále, až pro výběr posledního A-tého členu je po výběru všech předchozích členů celkem \n-(k - I j j = = (n — k+ 1) možností. Z kombinatorického pravidla součinu dostáváme, že celkový počet /c-členných variací z n prvků je roven součinu n ■ (n —1) • (n-2) • (n — 3)-.,. ... • (n-k+l). Odvodili jsme tak větu: Pro počet V(k,ri) všech ^-členných variací z n prvků platí: V(k,n) = n(n-l)(n-2).. . (n-k+l). 72 2. Kombinatorika Uvědomte si, že v součinu V(k.n) - n(n — l)(n-2)... (n—k+1) je celkem k činitelů: první je n a každý další je o jednu menší. Např. V(4,8) = 8 • 7 ■ 6 • 5, V(3,5) = 5-4-3, Vil. 1)-1 -6 atd. Jak uvidíte v dalším textu, dá se vzorec pro V(fc,n) zapsat pomocí faktoriálu. Z deseti závodníků má trenér vybrat čtyři pro štafetový závod, který probíhá tak, že každý z vybraných „borců" absolvuje jeden ze čtyř úseků o délkách 100 m, 200 m, 400 m a 800 m. Kolika způsoby to může provést? :' Mu" J ' "^SMätiKF" * ^ Řešení: V uvažovaných čtveřicích záleží na pořadí (v rámci jedné čtveřice záleží na tom, kdo poběží který úsek) a v každé z nich má být každý závodník nejvýše jednou. Jedná se proto o počet čtyřčlenných variací z deseti prvků, který známe: V(4,10)= 10-9-8-7 = 5040. Vzorec pro počet V(k,n) k-č\enných variací z n prvků vyjádříme nyní jinak. Vynásobíme rovnost V(k,n) = n-(n-l)-(n-l)-... -(n-k+l) výrazem (n—k)\, tj. V(k,n)-(n-k)\ = n-(n-l)-(n-2)-... ■ (n-k+l) ■ (n-k)\ neboli V(k,n)-(n-k)\=n\; odtud n\ V(k,n)=--rr (n—k)\ Nyní je vidět, proč jsme v článku o permutacích definovali 0! = 1; chceme-li totiž, aby vzorec V(k,n) ■ (n-k) platil i pro permutace, tj. pro k = n, musí být: V(n,n) = ■ n\=P(n). (n-n)\ 0! 1 Vzorec pro počet variací je tedy možné vyjádřit pomocí faktoriálu: Pro počet V(k,n) všech /^-členných variací z n prvků platí: V(k,n) = n-(n-\)-(n-l)- (n-k+l) = (n-k)V Určete počet všech šesticiferných přirozených čísel dělitelných pěti, v jejichž zápisu jsou každé dvě číslice různé. řešení: Každé šesticiferné přirozené číslo daných vlastností je uspořádaná šestice, ve které se vyskytuje každá z deseti číslic nejvýše jednou a pro kterou nastane jedna z těchto možností: 1. na posledním místě má pětku a nezačíná nulou, 2. na posledním místě má nulu. 2.3 Variace 73 Počet šestic s pětkou na konci a nezačínajících nulou dostaneme, když od počtu šestic s pětkou na konci odečteme počet těch šestic, které mají pětku na konci a nulou přitom začínají: šestic s pětkou na konci je V(5,9), šestic s pětkou na konci a nulou na začátku je V (4,8). Šestic s pětkou na konci a nezačínajících nulou je tedy Vr(5,9)-F(4,8). Šestic, které mají na posledním místě nulu, je V(5,9). Počet všech šesticiferných přirozených čísel dělitelných pěti, v jejichž zápisu jsou každé dvě číslice různé, je tedy dán výrazem [V (5.9) - V(4,8)] + V(5,9) = 2 • V(5,9) - V(4,8), který můžeme určit numericky: 2-9- 8-7-6-5-8-7 -6-5 = 8-7-6-5(2-9-l) = 8-7-6-5 • 17 = 28560. Kolika způsoby se ze čtyř dívek a osmi chlapců dají sestavit čtyři taneční páry, tj. dvojice tvořené chlapcem a dívkou? ŘEŠENÍ: Utvoříme-li z daných osmi chlapců všechny uspořádané čtveřice, dostaneme čtyři taneční páry tak, že první chlapec ze čtveřice bude tančit s dívkou D |, druhý s dívkou D2, třetí s dívkou D3 a čtvrtý s dívkou D4. Odtud je vidět, že počet všech tanečních párů je roven počtu uspořádaných čtveřic sestavených z daných osmi chlapců, tj. číslu V(4,8) = 8-7-6-5 = 1680. Do výboru sportovního klubu bylo zvoleno pět mužů a tři ženy a těchto osm osob má ze svého středu vybrat předsedu, jednatele a hospodáře. Kolik těchto trojic může vzniknout, má-li být v každé aspoň jedna žena? ŘEŠENÍ: Protože ve vybraných trojicích záleží na tom, která z osob bude předsedou, která jednatelem a která hospodářem, jde o trojice uspořádané; vynecháme-li zatím podmínku, že v každé musí být aspoň jedna žena, bude v každé této trojici každý z pěti mužů a každá ze tří žen nejvýše jednou. Počet všech těchto uspořádaných trojic je proto roven počtu tříčlenných variací z osmi prvků, tj. číslu V(3,8). Chceme-li však, aby v každé z těchto trojic byla aspoň jedna žena, musíme od počtu V(3,8) všech uspořádaných trojic odečíst počet všech uspořádaných trojic sestavených jenom z mužů, tj. číslo V(3,5). Dostaneme tak, že hledaný počet trojic s aspoň jednou ženou je roven V(3,8)-V(3,5) = 8-7-6-5-4-3 = 276. Určete počet prvků, pro který je počet všech čtyřčlenných variací z nich sestavených dvacetkrát větší než počet všech variací dvoučlenných. Řešení: Označíme-li n hledaný počet prvků, platí V(4,n) = 20 - V(2,n), kde neH,n> 4, 74 2. Kombinatorika . šestic přitom jsou . dvo- neboli n(n-l)(K-2)(R-3) = 20n(n-l). Vzhledem k tomu, že n i (n - 1) jsou různé od nuly, dostaneme po zkrácení a úpravě kvadratickou rovnici «2-5rt-14 = 0, s kořeny n\ = 7, «2 = -2. Vzhledem k tomu, že číslo n, které udává počet prvků, nemůže být záporné, kořen «2 nevyhovuje úloze; a protože n\ > 4, dostáváme odtud, že daná úloha má jediné řešení, a to n = 7. Cvičení Určete, kolika způsoby se osm finalistů olympijského závodu na 100 m může umístit na 1., 2. a 3. místě a podle svého umístění získat zlatou, stříbrnou a bronzovou medaili. Kolik je všech přirozených čísel menších než 5 000, v jejichž zápisu jsou pouze číslice 1, 3, 5, 7, 9, a to každá nejvýše jednou? Určete, kolik různých vlajek skládajících se ze tří vodorovných pruhů různé barvy se dá sestavit, jsou-li k dispozici tyto barevné látky: červená, modrá, bílá, žlutá a zelená. Určete, kolika způsoby je možné sestavit pro danou třídu šestihodinový rozvrh hodin na jeden den, má-li v něm být z deseti vyučovaných předmětů každý nejvýše jednou. Kolika způsoby si může pět hochů rozdělit mezi sebe tři různé předměty, má-li každý dostat nejvýše jeden? sob může edou, zatím : ?én »jic je počtu mých idnou nvch 2.4 Kombinace Až dosud jsme určovali počty skupin vybraných z daných prvků, v nichž záleželo na pořadí. V tomto článku přejdeme ke skupinám, ve kterých pořadí rozhodovat nebude. Kolika způsoby se pro trojmístnou lavici letního kina dají ze čtyř diváků vybrat tři? Řešení: Označme A, B, C, D čtyři diváky, kteří se o posezení na trojmístné lavici ucházejí a jimž je přitom lhostejné, na kterém místě této lavice budou sedět. Vypíšeme--li všechny možnosti tohoto výběru, dostaneme čtyři neuspořádané trojice (pro jejich odlišení od trojic uspořádaných budeme používat množinové závorky): {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}. Můžeme však postupovat i jinak. Z prvků každé z těchto neuspořádaných trojic utvoříme všech 3! permutací a dostaneme tak všechny trojčlenné variace ze čtyř prvků, jejichž počet známe: {A,B,C}-^ {A, B,D} -> {A,C,D}-^ {B,C,D} -»■ (A,B,C), (A,C,B), (A, B,D), (A,D.Mi (A.CD), (A,D,C). (B.C.D). (B,D,C). (B,A,C), (B,C,A), (C,A,B), (C,B,A), (B, A, D), (B,D, A), (D, A, B), (D,B, A), (C,D,A), (C.A.D), (D.A.C). (D,C,A), (C,B,D), ÍC.D.B), (D,B,C), (D,C,B). rika 2.4 Kombinace 75 Počet všech uspořádaných trojic v rámečku, tj. počet V(3,4) tříčlenných variací ze čtyř prvků, je roven součinu počtu sloupců v rámečku, kterých je 3!, a počtu řádků v rámečku; těchto řádkuje však právě tolik, kolik je neuspořádaných trojic z daných čtyř prvků. Označíme-li tento počet neuspořádaných trojic ze čtyř prvků K(3,4), dostáváme V(3,4) = 3\K(3,4), odkud vypočteme Neuspořádané trojice sestavené ze čtyř prvků tak, že každý se v nich vyskytuje nejvýše jednou (tj. jen jednou nebo vůbec), se nazývají kombinace, přesněji trojčlenné kombinace ze čtyř prvků; jejich počet značíme K(3 A). Obecně definujeme: Neuspořádaná £-tice sestavená z daných n prvků tak, že každý je v ní nejvýše jednou, se nazývá /r-členná kombinace z n prvků. Ze stejného důvodu, kvůli němuž pro k > n neexistují A-členné variace z n prvků, neexistují ani Ä-členné kombinace z n prvků. Připomeňme si také, že místo o kombinacích (podobně jako o variacích) se často hovoří o kombinacích bez opakování, aby se zdůraznilo, že žádný prvek se v žádné A'-tiei neopakuje. Všimněte si rovněž, že ^-členné kombinace z n prvků nejsou nic jiného než ^-prvkové podmnožiny «-prvkové množiny; proto jsme pro výčet jejich prvků používali množinové závorky. Vzorec pro počet ^-členných kombinací z n prvků se dá získat zobecněním postupu, který jsme použili pro určení počtu těchto kombinací v případě k = 3 a n = 4. Představíme si tabulku, do níž jsou všechny £-členné variace z n prvků sestaveny tak, že v každém řádku jsou právě ty variace, které obsahují tytéž prvky. Počet těchto řádků je roven počtu /c-členných kombinací z n prvků a počet sloupců je k\, proto platí V(k,ri) = k\K(k,ri), odkud dostáváme vn \ V^n) t iw ^ n-k+\ n\ K(k.n) = —-— = n(n-\)(n-2)- k\ v /v ' "' kl (n-k)lkl' Tento výsledek zapíšeme obvyklejším způsobem pomocí symbolu ( " ), který čteme „n nad /c" a který se nazývá kombinační číslo. ~6 2. Kombinatorika Pro všechna celá nezáporná čísla n, k, kde k < n, je kombinační číslo definováno takto: 0t\ n\ n(n-\)(n-2)-...-(n — k + l) KkJ (n-k)\k\ k\ Vzorec, který jsme pro počet ^-členných kombinací z n prvků získali, si zapamatujeme: Pro počet K(k,n) všech fc-členných kombinací z n prvků platí: n K(k,n) = Protože každá A-členná kombinace z n prvků je A-prvková podmnožina této množiny, udává kombinační číslo ^ ] i počet všech Á-prvkovvch podmnožin n-prvkové množiny. Kolika způsoby je možné z krabice, která obsahuje padesát součástek, z nichž pět je vadných, vybrat osm součástek, mezi nimiž je vadná nejvýše jedna? řešení: Počet možných výběrů osmi součástek, mezi nimiž je jediná vadná, označme pi, počet výběrů osmi součástek, mezi nimiž není vadná žádná, označme pq. Počet výběrů osmi součástek s nejvýše jednou vadnou je roven součtu p\ +pq. Výběr s jedinou vadnou součástkou dostaneme, když vybereme jednu vadnou součástku, což lze provést ( j způsoby, a k ní vybereme sedm součástek, které vadné nejsou, coz lze provést ( 1 způsoby; je tedy = i i • i Pro počet po výběrů bez vadné součástky platí: pq = Hledaný počet výběrů je dán součtem pi+po= [^j • + y% ): počet už proveďte sami. Z pěti mužů a čtyř žen se má postavit šestičlenné volejbalové družstvo, v němž mají být nejvýše tři muži a aspoň tři ženy. Kolik je možností pro sestavení tohoto družstva? Řešení: Mají-li být splněny dané podmínky, jsou pro počty mužů a žen v družstvu pouze dvě možnosti: 1. družstvo tvoří dva muži a čtyři ženy, 2. družstvo tvoří tři muži a tři ženy. 2.4 Kombinace 77 Q] V prvním prípade vybereme dva muže z pěti, což lze provést \J způsoby, a čtyři ženy ze čtyř, což lze provést jediným způsobem. Počet možností, jak toto družstvo sestavit, je tedy U ) "1 = U Ve druhém případě vybereme tři muže z pěti, což lze provést ( ) způsoby, a tři ženy ze čtyř, což lze provést I J způsoby. Protože každou trojici mužů můžeme doplnit libovolnou trojicí žen, je počet možností, jak toto družstvo sestavit, roven součinu Pro sestavení volejbalového družstva je tedy celkem + Numerickým výpočtem zjistíte, že těchto možností je 10 +10 • 4 = 50. možností. Určete počet přímek určených deseti různými body, jestliže a) žádné tři z těchto bodů neleží v přímce, b) pět z daných bodů leží v přímce. Řešení: a) Neleží-li žádné tři body v přímce, je každými dvěma z deseti daných bodů určena jiná přímka, takže celkový počet těchto přímek je ( ^ I = 45. b) Leží-li pět bodů v přímce, pak všech IJ přímek, které jsou každými dvěma z těchto pěti bodů určeny, splyne v přímku jedinou. V tomto případě je proto nutno od počtu přímek získaného v a) těchto přímek odečíst, nesmíme však zapomenout, že tím odečítáme i přímku, která těmito pěti body prochází. Dostaneme tak, že celkový počet přímek určených deseti body, z nichž pět leží v jedné přímce, je roven ŕ^J -ft I V tombole je sto losů, z nichž deset vyhrává. Petr si zakoupil pět losů. Kolik je možností, že mezi těmito pěti losy je aspoň jeden, který vyhraje? Řešení: Pět losů ze sta si Petr může vybrat ^ 4. Za tohoto předpokladu platí x-í\ (x-l)\ (x-l)(x-2) x-3j (jc-3)!2! 2 jt-2\ (x-2)! (*-2)(x-3) x-41 (x-4)!2! 80 Kombinatorika a protože je 3 [ ^ ) =3-3 = 9, přejde daná rovnice po vynásobení dvěma na tvar (x-1)(jc-2)+(jc-2)0c-3) = 18. Po snadných úpravách dojdeme k rovnici x2-4x-5 = 0, jejímiž kořeny jsou čísla x i = -l,X2 = 5. Dané rovnici z těchto dvou kořenů vyhovuje pouze jediný, a to x = 5. Přesvědčme se zkouškou, že jde o řešení: L(5)=^) + (i)=6+3 = 9, P(5) = 3-(T)=9, L(5) = P(5). . Í50\ Í5\\ Í52\ Jediným kombinačním číslem vyjádřete součet I ^ j + I ^ I + I ^ I, aníz tato cisla vyjadřujete podle definice. řešení: Na první pohled nemůžeme žádnou ze dvou vět, které o kombinačních číslech známe, použít, ale na druhý ano, když si uvědomíme, že platí \^\ ~ f 51y ^10 sou^et prvních dvou sčítanců daného součtu tak budeme mít 5o) + (50) = (51) + (50) = (51 /52\ a přičteme-li nyní k tomuto součtu ještě í J, dostaneme výsledek: 5o) + (si) + (S) = (si) + (S) = (si Podobným způsobem, jaký jsme použili v předchozím příkladu, se dá dokázat tvrzení: Pro všechna celá nezáporná k, n platí: (k\ fk+\\ (k + 2\ ík + n\ fk+n+\\ Například: Uspořádáme-li kombinační čísla do trojúhelníkového schématu, v jehož řádcích jsou postupně pro n = 0. 1,2,... seřazena kombinační čísla od k = 0 do k = n, dostaneme tzv. Pascalův trojúhelník; jestliže tato kombinační čísla vyčíslíme, dostaneme Pascalův trojúhelník zapsaný čísly přirozenými. 2.5 Vlastnosti kombinačních čísel, Pascalův trojúhe 81 Pascalův trojúhelník zapsaný kombinačními čísly Pascalův trojúhelník zapsaný přirozenými čísly Všimněte si rozmístění čísel v temže řádku Pascalova trojúhelníku; čísla ( ^ j a ( " ^ J jsou umístěna symetricky vzhledem ke středu řádku, v němž se nacházejí, a protože se sobě rovnají, je celý trojúhelník souměrný podle svislé osy. Z rovnosti + = vyplývá i další vlastnost Pascalova trojúhelníku: Součet libovolných dvou sousedních čísel v n-tém řádku Pascalova trojúhelníku je roven číslu, které se nachází v řádku («+ l)-ním „pod jejich středem". Tato vlastnost Pascalova trojúhelníku umožňuje určit jeho libovolný řádek, známe-li řádek předcházející. Tak např. řádek pro w = 6 dostaneme zřádku 1,5,10, 10,5,1 pro n = 5 uvedeného schématu takto: Začíná a končí jedničkou a jeho „vnitřní" členy jsou po řadě čísla = 1 + 5, 15 = 5 + 10, 20=10+10, 15 = 10+5, 6 = 5 + 1. Blaise Pascal byl významný francouzský matematik, fyzik a filozof, který žil v 17. století. Zkonstruoval první mechanický sčítací stroj, z hydrostatiky je znám Pascalův zákon. Spolu s Pierrem de Fermatem vytvořil základy počtu pravděpodobnosti. B.Pascal P. de Fermat 82 2. Kombinatorika Cvičení Vyjádřete jediným kombinačním číslem součty: Určete všechna přirozená čísla x, pro něž platí: x-l) + C-2) = (2, Určete přirozené číslo n tak, aby kombinační číslo ( j bylo třikrát větší než kombinační číslo Napište pomocí kombinačních i pomocí přirozených čísel řádek Pascalova trojúhelníku, který odpovídá číslu n = 8. rT x , , , /700\ /699\ v, Určete, které z kombinačních cisel I 1,1 I je vetsi, amz je vyčíslíte. 2.6 Binomická věta Vzorce pro druhou a třetí mocninu dvojčlenu (neboli binomu), které určitě znáte, v tomto článku zobecníme a naučíme se umocňovat dvojčlen na jakékoli přirozené číslo n. Vyjdeme z toho, že porovnáme koeficienty mnohočlenů, které vzniknou umocněním dvojčlenu (a + b)n pro n = 0, 1, 2, 3, 4, 5, s příslušnými řádky Pascalova trojúhelníku: (a + bf 1 1 (a + b){ a + b 1 1 (a + bf a2 + 2ab + b2 1 2 1 (a + bf a3 + 3a2b + 3ab2 + b3 13 3 1 (a + b)4 a4+4a3b + 6a2b2 + 4ab3+b4 1 4 6 4 1 (a + b)5 a5 + 5a4b+\0a3b2 + \0a2b3+5ab4 + b5 1 5 10 10 5 1 Toto porovnání nás přivádí na myšlenku, že např. řádek Pascalova trojúhelníku pro n = 6, tj. řádek 1, 6, 15, 20, 15, 6, 1, určuje koeficienty mnohočlenu, který vznikne umocněním dvojčlenu (a + b)6. Přesvědčte se, že vskutku platí: (a + bf = a6 + 6a5b+l5a4b2 + 20a3 b3 + I5a2b4 + bab5 + b6. Na základě tohoto porovnání můžeme vyslovit domněnku, že koeficientům mnohočlenu, který vznikne umocněním dvojčlenu (a + b)k, odpovídá řádek Pascalova trojúhelníku pro n =k, tj. že platí: (a + bf k _ /k)ak-]b + ík\lk-2b2+- .+(ky w \2 2.6 Binomická věta 83 Tato domněnka se dá dokázat matematickou indukcí, my si však naznačíme její odvození kombinatorické. Představme si, že mocninu (l+.r)" vyjádříme jako součin n dvojčlenů, který budeme roznásobovat: (1 +x)n = (1 +x) (1 +x) (1 +jc) ... (1 +x). • Ze žádného dvojčlenů nevybereme x, tj. ze všech vybereme jedničku a všechny jedničky mezi sebou vynásobíme - v celkovém výsledku dostaneme člen rovný jedné. • Z jednoho dvojčlenů vybereme x, ze zbývajících vybereme jedničky a utvoříme jejich součin, který je roven x; takto utvořených součinů je , neboť tolika způsoby je možné z n dvojčlenů jedno x vybrat. V celkovém výsledku tak dostaneme člen ( . \x. Ze dvou dvojčlenů vybereme x, ze zbývajících vybereme jedničky a utvoříme jejrch součin, který ,e roven *>; rakto „.vorech souernu ,e (»). nebo,' ,o-lika způsoby je možné z n dvojčlenů dvě x vybrat. V celkovém výsledku tak dostaneme člen ('Dx2. 2/ Ze tří dvojčlenů vybereme x, ze zbývajících vybereme jedničky a utvoříme jejich součin, který je roven x3; takto utvořených součinů je y^j, neboť tolika způsoby je možné z n dvojčlenů tři x vybrat. V celkovém výsledku tak dostaneme člen x\ • Takto pokračujeme. V předposledním kroku vybereme x z (n— 1) dvojčlenů, ze zbývajícího vybereme jedničku a utvoříme jejich součin, který je roven x"_1; o ( n\ takto utvořených součinu je I I, neboť x je možné z n dvojčlenů tolika způsoby vybrat. V celkovém výsledku dostaneme člen ( " \x \n-\J • Nakonec vybereme x ze všech n dvojčlenů, což lze provést jediným způsobem, a utvoříme jejich součin, který je roven x"; to je zároveň poslední člen celkového výsledku. " ^ „n-l Zjistili jsme tak, že platí: n\ i n \ 2 n\ 3 I n (1 +xf =l+yi)x+[2)x +[3)x +---+[n_]) x +x" ■ b Dosadíme-li do tohoto výsledku x= -, kde a ^0, dostaneme a b\" . fn\ fb\ fn\ (b\ (n\ //?\3 ( n \ f b\" ' /b^ \ a l + a =1+ 1 U + 2 U + 3 U + "Vn-l 84 kombinator Vynásobíme-li tuto rovnost mocninou a", bude na levé straně výraz b" a na strane pravé výraz A = an+ ' b + 1+- n 2 a 1 = (a+bf an~2b2 + ■,n-3 ui & + ■ n-\ abn~]+bn. Je tedy (a + b)" = A, a to i pro a = 0, jak se snadno můžete přesvědčit. Tímto způsobem jsme zdůvodnili, že výše uvedená domněnka je správná. Binomická věta Pro libovolná čísla a, b a pro všechna přirozená čísla n platí: (a+b)" = an + a"~lb+ a"-2b2 + - n—k uk bk + - abn-\ +bn_ Pravá strana této rovnosti se nazývá binomický rozvoj výrazu (a + b)": říkáme o ní. že vznikla rozvinutím výrazu (a + b)" podle binomické věty. Všimněte si. že tento rozvoj má /;+ I sčítanců a že v něm klesají exponenty mocnin o základu a a rostou exponenty mocnin o základu b tak, že součet těchto exponentu je stále roven číslu V tomto rozvoji jsme vynechali koeficient ^ u členu a" a koeficient ^" j u členu b", neboť jsou oba rovny jedné. Protože v binomickém rozvoji vystupují jako koeficienty kombinační čísla, používá se pro kombinační čísla také název binomické koeficienty. Rozviňte podle binomické věty ( 3x 2X5 2 Řešení: Ve dvojčlenu (a + b)5 položíme a = 3x2, b = —j- a dostaneme: = 3V° + 5 • 34 • (-2)^ +10 • 33 ■ (-2)2-. + +10.32.(-2)34+5-3.(-2)44 + ^rř- x8 x6 r4 x2 32 = 243x,0-81Q-,+ 1080-y-720"-, +240^--^. yi y6 y9 yl2 yl5 2.6 Binomická věta 85 Podle binomické věty (nikoli pomocí kalkulačky) vypočtěte 1,01 . Řešení: Užitím binomické věty dostaneme: i,oi4 = (i+o,oi)4 = i4+(;) i3 0,01+H) i2o,oi2+r j io,oi3+o,oi4 = IJ \2J ' \3/ + 4 0.01+6 0,0001 +4-0,000001+0,00000001 = 1.04060401. Pro rozvoj dvojčlenu (1 +x)n, kde x je malé číslo, se v praxi používá přibližný n 1. vzorec: (1 +.v)" = 1 + I " j x = 1 +nx. Jeho aplikací na předcházející příklad dosta ncme. že 1 .Ol4 = 1.04. Chcete-li znát v binomickém rozvoji daného výrazu pouze určitý člen, není nutné celý V rozvoj rozepisovat. Uvědomte si však, že člen s koeficientem I ] je v tomto rozvoji na místě s pořadovým číslem k+1; bereme-li totiž člen s koeficientem jako první, je člen s koeficientem druhý, člen s koeficientem třetí atd. Znamená to, že ( n binomický koeficient u k-tého členu rozvoje je roven I . Určete desátý člen binomického rozvoje výrazu (x2 — j3)15. ŘEŠENÍ: Binomický koeficient u desátého členu je ^gj > °dkud dostaneme, že desátý člen rozvoje daného vyřazuje roven xl2y27. ( n20 V binomickém rozvoji výrazu I 4x+ -j 1 určete člen, který neobsahuje x. ŘEŠENÍ: Vyjádříme obecný člen rozvoje daného výrazu: ^ (4x)2°-k (x-3)k = ^ .42°-¥Wíi-a'= ^ .^x20-4". Nemá-li tento člen obsahovat proměnnou x, musí být její exponent roven nule, tj. 20-4£ = 0 neboli k = 5. Clen rozvoje, který neobsahuje x, je tedy jediný a je roven číslu ( J -4i5; v rozvoji daného vyřazuje na šestém místě. Binomická věta se dá použít nejen k umocňování dvojčlenu, ale i k odvození některých vlastností kombinačních čísel. Například z binomického rozvoje výrazu (a + b)n dosazením a = b = 1 dostaneme: 86 2. Kombinatorika Pro všechna přirozená čísla n platí: Z této rovnosti plyne zajímavý důsledek: Protože kombinační číslo udává počet ^-prvkových podmnožin h-prvkové množiny, udává součet h-----h počet všech jejích podmnožin. Platí tedy: Každá n-prvková množina má 2" podmnožin. Podobně dosazením a = 1, b = -1 do výrazu (a + b)" dostaneme: Pro všechna přirozená čísla n platí: A na závěr si ještě ukážeme užití binomické věty v úloze na dělitelnost celých čísel. Dokažte, že číslo 7" -1 je pro všechna přirozená čísla n dělitelné šesti. Řešení: Mocninu 7" vyjádříme ve tvaru (6+ 1)" a tento dvojčlen rozvineme podle binomické věty: 7" = (6+1)" = 6"+M-6n~l + ('!)-6n-2 + ---+( n \ -6 + 1. 1/ \2J \n-l, Odtud už je vidět, že rozdíl 7"- 1 je pro všechna přirozená n dělitelný šesti. Cvičení Rozviňte podle binomické věty: 0(x3-2)'. b>(>+^)6. c)(?-I)4. d,^"3 Podle binomické věty (bez užití kalkulačky) vypočtěte 0.985 a výsledek zaokrouhlete na setiny. Vypočtěte sedmý člen binomického rozvoje výrazu (5 — \/5)12. f o 3 V V binomickém rozvoji výrazu 2a —= určete člen, který neobsahuje a. \ a2 J js8 Určete číslo y tak, aby v binomickém rozvoji výrazu ^4y- — ) byl čtvrtý člen roven —14. 2.6 Binomická věta 87 2.7 Úlohy k opakování I V šachovém turnaji, ve kterém každý ze zúčastněných hráčů odehrál s každým ze zbývajících jednu partii, bylo sehráno celkem 45 partií. Určete počet účastníků turnaje. Na schůzi má vystoupit pět řečníků: A, B, C, D, E. Kolik je možností pro pořadí jejich projevů, má-li A promluvit dříve než B? Kolik je možných pořadí, má-li A mít svůj projev bezprostředně před B? Určete, kolika způsoby se dají přemístit písmena ve slově SLAVIE tak, aby toto přemístění obsahovalo slovo LEV. Zvětší-li se počet prvků o jeden, zvětší se počet dvojčlenných variací z těchto prvků o deset. Jaký byl původní počet prvků? 15! 12! 8TTTT 9!5!' Vypočtěte: 24 • Určete všechna přirozená čísla x, pro která platí: {x-A)\ + {x-2)\ (x-3)\ Kolika způsoby se může 8 závodníků podělit o zlatou, stříbrnou a bronzovou medaili? Kolika způsoby se dá z patnácti vojáků utvořit tříčlenná hlídka? V rovině je dáno osm různých bodů, z nichž žádné tři neleží v přímce. Kolik přímek je těmito body určeno? V rovině je dáno osm různých bodů, z nichž právě čtyři leží v jedné přímce. Kolik přímek je těmito body určeno? Jediným kombinačním číslem vyjádřete součet: 20\ [20\ u^ (12\ HT >rw bl Uru Kolik podmnožin má šestiprvková množina? Kolik z nich je tříprvkových? / í \12 Určete osmý člen binomického rozvoje výrazu ( 2x3 - — \ 2x Určete počet všech čtyřciferných přirozených čísel, v jejichž zápisu se vyskytují pouze liché číslice, a to každá nejvýše jednou. Ve třídě je 15 hochů a 10 dívek. Kolika způsoby lze ze všech těchto žáků vybrat trojici, ve které jsou dva chlapci a jedna dívka? Kolika způsoby je možno na šachovnici 8x8 vybrat dvě různobarevná políčka tak, aby neležela ani v téže řadě, ani v temže sloupci? V kolika bodech se protíná 10 přímek v rovině, jsou-li právě čtyři navzájem rovnoběžné? a) 88 2. Kombinatorika 2.8 Perw lf:l Určete všechna přirozená čísla x, pro něž platí: iM Určete, kolika způsoby lze u startovní čáry seřadit šest závodních automobilů do dvou řad po třech vozech, jestliže a) v každé řadě záleží na pořadí, b) na pořadí v řadách nezáleží. Bliti Určete, kolika způsoby se dá z patnácti osob vybrat osm, mají-li být mezi vybranými pan A i paní B. 2.8 Permutace s opakováním Permutace, jak víme z článku 2.2, je uspořádaná w-tice sestavená z daných n prvků tak, že každý se v ní vyskytuje právě jednou. Nyní se budeme zabývat uspořádanými n-ticemi, v nichž se některé prvky mohou vyskytovat vícekrát. Uvažujme pětičlennou skupinu tvořenou dvěma hochy a třemi dívkami a vypišme všechny možné způsoby, jak se mohou postavit do řady; mezi oběma hochy ani mezi žádnými dvěma dívkami nebudeme přitom rozlišovat. Označíme-li písmenem H každého z obou hochů a písmenem D každou ze tří dívek, dostaneme těchto deset možných pořadí: (D, D, D, H, H), (D, D, H, D, H), (D, D, H, H, D), (D, H, D, H, D), (D, H, D, D, H), (D, H, H, D, D), (H, H, D, D, D), (H, D, H, D, D), (H, D, D, H, D), (H, D, D, D, H). Tyto uspořádané pětice jsou příkladem permutací s opakováním ze dvou prvků, z nichž jeden se opakuje dvakrát a druhý třikrát. Obecně definujeme: Permutace s opakováním z n prvků je uspořádaná fc-tice sestavená z těchto prvků tak, že každý je v ní aspoň jednou. Označíme-li k\, k2, ..., k„, kolikrát se jednotlivé prvky, kterých je n, opakují, platí zřejměk\ +k2-\-----\-k„ > n;prok\ =ki = • • ■ =kn = 1 dostaneme, žejek\ +k2-\-----\-k„ = n, což znamená, že se jedná o permutace bez opakování. (Permutace bez opakování jsou tedy zvláštním případem permutací s opakováním.) Abychom mohli určit počet permutací s opakováním z n prvků, musí být známo, kolikrát se v nich jednotlivé prvky opakují; opakují-li se fcj-krát, £2-krát, ..., fc„-krát, budeme počet těchto permutací značit p'(k\, k2, ..., k„). Výsledek, který jsme získali v úvodní ukázce pro počet permutací s opakováním ze dvou prvků, z nichž jeden se opakuje dvakrát a druhý třikrát, zapíšeme tedy takto: P'(2, 3) = 10. Tento výsledek, který jsme získali výčtem, nyní odvodíme následující úvahou. Uvažujme opět pětičlennou skupinu tvořenou dvěma hochy a třemi dívkami, ale na rozdíl od uvedené ukázky oba hochy i každé dvě dívky rozlišíme; nebudeme tedy tvořit permutace s opakováním ze dvou prvků H, D, ale permutace (bez opakování) z pěti prvků H], H2, Dl5 D2, D3. Představme si dále, že máme vypsáno všech 5! permutací z těchto pěti prvků, a zkoumejme, kolik z těchto permutací se ztotožní, jestliže u všech pěti prvků odstraníme indexy, tj. když položíme H4 = H2 = H, Dj = D2 = D3 = D. Které permutace splynou například s permutací (D, H, D, D, H)? Zřejmě to jsou tyto permutace: (Di H,, D2,D3,H2), (Dj,H2,D2, D3,HO, (D,, H,,D3,D2, H2), (D1; H2, D3, D2,H,), (D2,H,,D,,D3,H2), (D2,H2,Di,D3,HO, (D2,Hi,D3,D|,H2), (D2,H2,D3,D!,H,), (D3,H,,Di,D2,H2), (D3,H2,Dj,D2,H,), (D3, Ht, D2, D,,H2), (D3,H2,D2,D,,H,). Z tohoto výčtu je vidět, že permutace, které splynou s permutací (D, H, D, D, H), jsou právě ty, v nichž jsou prvky Hi, H2 na druhém a pátém místě a prvky Dj, D2, D3 na místech prvním, třetím a čtvrtém. Pro umístění na těchto místech je však pro prvky H], H2 celkem 2! možností a pro prvky Dj, D2, D3 je těchto možností 3!. Znamená to, že s permutací (D, H, D, D, H) splyne celkem 2!.3! permutací z prvků Hi, H2, Di, D2,D3. Tímto způsobem se všech 5! permutací z prvků H1, H2, D], D2, D3 rozloží do takových skupin, že v každé budou právě ty permutace, které se po odstranění indexů ztotožní. A protože každá tato skupina má 2! • 3! členů a odpovídá jediné permutaci s opakováním ze dvou prvků H a tří prvků D, platí pro jejich počet: k ' 2!3! 2!3! Zobecněním tohoto postupu dostaneme hledaný vzorec pro počet permutací s opakováním: Pro počet P'(ky, a:2,..., k„) permutací s opakováním z n prvků, které se opakují k\. kj.....a„-krát. platí: tím 1 1 i {k\+h + --+kn)\ .....ä,:a::...a,'-- Jakuž víme, j sou permutace bez opakování takovými permutacemi s opakováním, v nichž se každý z daných n prvků opakuje právě jednou, tj. v nichž je k\ = A2 = = ... = kn = 1. Znamená to, že by mělo platit P(n) = P'(\. 1,..., 1). To opravdu platí: Kolika způsoby je možné sestavit rychlíkovou soupravu, která má kromě čtyř vozů 2. třídy a jednoho vozu 1. třídy obsahovat ještě po jednom vozu lehátkovém, jídelním a poštovním? V kolika těchto soupravách nejsou všechny čtyři osobní vagony 2. třídy vedle sebe? 90 .ombinatorika řešení: Protože mezi čtyřmi osobními vagony 2. třídy nerozlišujeme, jde o počet permutací s opakováním z pěti prvků, z nichž jeden se opakuje čtyřikrát a každý ze čtyř zbývajících jednou. Počet těchto permutací je Počet souprav, v nichž čtyři osobní vozy 2. třídy nejsou vedle sebe, dostaneme tak, že 8! od počtu — všech souprav odečteme počet těch, ve kterých čtyři osobní vozy 2. třídy vedle sebe jsou. Považujeme-li tyto čtyři osobní vozy zajeden, dostaneme pět různých prvků (vůz 1. třídy, spojené vozy 2. třídy, vůz lehátkový, jídelní a poštovní), z nichž lze utvořit 5! permutací. Počet souprav, v nichž nejsou čtyři osobní vozy 2. třídy vedle sebe, je tedy o, p'(4,1, 1, 1, 1)-P(5) = --5! = 1680-120= 1560. Petr si zapamatoval, že v telefonním čísle jeho spolužáka jsou tři jedničky, dvě dvojky, dvě pětky a dvě sedmičky. Jaký nejmenší počet telefonních čísel s uvedenými vlastnostmi by musel vytočit, aby měl jistotu, že je mezi nimi to správné? Řešení: Hledaný počet čísel je roven počtu permutací s opako- y * ^ váním ze čtyř prvků, z nichž jeden se opakuje třikrát a každý ze j*- ^ zbývajících tří dvakrát. Aby měl Petr jistotu, že volá správné číslo, je počet možností, které musí vyzkoušet, roven í. lr Kí- , P'(3, 2, 2, 2) =^^=7560. Na týdenní výlet si Milan dal do batohu (mimo jiné) tři čokoládové, dvě oříškové a dvě kokosové tyčinky s tím, že každý den sní jednu. Kolika způsoby si může tyčinky rozdělit do jednotlivých dnů? Řešení: Jedná se o počet pořadí ze tří prvků, z nichž jeden se opakuje třikrát a každý ze zbývajících dvou dvakrát. Počet možností, jak realizovat spotřebu tyčinek, je TO 2,2)-^=210. Určete počet čtyřciferných přirozených čísel, k jejichž sestavení jsou k dispozici dvě dvojky, jedna trojka, dvě sedmičky a jedna devítka. Řešení: Uvědomte si nejprve, že pro sestavení těchto čtyřciferných čísel jsou jenom tyto možnosti: a) Skládají se ze čtyř různých číslic - počet těchto čísel je P(4) = 4! = 24. b) Skládají se ze dvou číslic stejných a dvou různých, takže jsou sestaveny z těchto číslic: 2,2,3,7; 2,2,3,9; 2,2,7,9; 7,7,2,3; 7,7,2,9; 7,7,3,9. Protože počet čísel sestavených z číslic každé z těchto čtyřčlenných skupin je 4! p'(2, 1,1)= = 12, je počet čísel sestavených ze všech těchto šesti skupin roven6P'(2. l.'l)' = 6- 12 = 72. 2.8 Permutace s opakováníi 91 c) Skládají se ze dvou dvojic stejných číslic, tj. z číslic 2, 2, 7, 7; počet čísel z této 4! čtyřčlenné skupiny sestavených je P'(2, 2) = = 6. Celkový počet čtyřciferných čísel, k jejichž zápisu lze užít dvě dvojky, jednu trojku, dvě sedmičky, jednu devítku a žádné jiné číslice, je roven součtu P(4) + 6P'(2, 1, 1) + P'(2, 2) = 24 + 72 + 6 =102. Přemístíme-li písmena nebo slabiky slova nebo věty do nového slovního nebo větného útvaru, vznikne tzv. anagram. Za anagram můžeme považovat např. seskupení písmen AAB1IKKMNOORT, které vzniklo přemístěním písmen slova KOMBINATORIKA; jiným přeskupením písmen slova KOMBINATORIKA dostaneme anagram zajímavější: MINTKABAROTOK. Cvičení Kolika způsoby se dají přemístit písmena slova INTERNET? WM Určete, kolika způsoby se dá na první řadu šachovnice postavit těchto osm bílých figur šachové hry: král, dáma, dvě věže, dva střelci a dva jezdci. B n. Počet fc-členných variací s opakováním z n prvků určíme snadno pomocí kombinatorického pravidla součinu. Stačí si uvědomit, že pro výběr každého členu uspořádané A-tice sestavené z daných n prvků máme n možností, a to nezávisle na tom, které prvky byly vybrány pro členy předcházející; na každém místě této uspořádané fc-tice může být jakýkoli z n prvků daných. Podle pravidla součinu je počet těchto uspořádaných k-ůc roven součinu n-n-n-... ■ n, ve kterém je k činitelů a který je tedy roven nk. Pro počet V'(k. n) všech A-členných variací s opakováním / n prvků platí: " \"(k.n) = nk. V Tramtárii je státní poznávací značka osobního auta uspořádaná sedmice, jejíž první tři členy jsou písmena a zbývající čtyři číslice; písmena i číslice se mohou opakovat, k dispozici je 24 písmen a deset číslic. Určete největší možný počet osobních aut, k jejichž označení tyto značky vystačí, nemají-li mít žádná dvě auta stejnou poznávací značku. řešení: První část poznávacích značek jsou uspořádané trojice vybrané z 24 písmen, která se mohou opakovat, takže jde o tříčlenné variace s opakováním z 24 prvků; jejich početje V/(3,24) = 243. Druhá část každé značky je uspořádaná čtveřice sestavená z deseti číslic, které se mohou opakovat, takže jde o čtyřčlenné variace s opakováním z 10 prvků; jejich počet je V"(4, 10)= 104. Protože pro výběr prvních tří míst v této značce je V (3, 24) možností a pro výběr čtyř míst následujících - nezávisle na výběru první trojice - je V'(4, 10) možností, je celkový počet uspořádaných sedmic dané vlastnosti roven součinu V'(3, 24) ■ V'(4, 10) = 243 • 104 = 13 8 240 000. Toto číslo udává i největší možný počet aut, k jejichž označení tyto značky stačí. 2.9 Variace s opakováním 33 Kufrík má heslový zámek, který se otevře, když na každém ze šesti kotoučů nastavíme správnou číslici; na každém kotouči jsou všechny číslice od jedné do osmi. Jaký nejmenší možný počet pokusů o otevření zajistí otevření kufříku? Řešení: Počet všech možných způsobů, kterými se dá nastavit šesticiferné číslo sestavené z osmi číslic, je roven počtu šestičlenných variací s opakováním z osmi prvků, tj. číslu V'(6, 8) = 86. Nejmenší možný počet pokusů, který zajistí otevření kufříku, je 86 = 262144! Určete počet všech pěticiferných přirozených čísel. řešení: První způsob: Seřaďme všechna přirozená čísla od jedné do 99 999 a následujícím způsobem je uzávorkujme: [(1, 2, 3,____9998, 9999), 10000, 10001, ..., 99998, 99999]. Počet všech pěticiferných přirozených čísel zřejmě dostaneme, když od počtu všech čísel v hranaté závorce odečteme počet všech čísel v závorce kulaté; hledaný počet všech pěticiferných přirozených čísel je proto roven číslu 99999-9999 = 90000. Druhý způsob: Každé pěticiferné přirozené číslo je uspořádaná pětice sestavená z deseti číslic tak, že na každém jejím místě je jakákoli z deseti číslic kromě místa prvního, na němž nemůže být nula. První člen této pětice lze tedy vybrat devíti způsoby a každý člen další po výběru všech předcházejících členů lze vybrat deseti způsoby, protože se číslice mohou opakovat. Počet všech pěticiferných přirozených čísel je podle pravidla součinu roven číslu 9-10-10-10-10 = 90000. Třetí způsob: Máme určit počet všech pětičlenných variací s opakováním z deseti číslic 0, 1, 2, ..., 9, které nemají na prvním místě nulu. Tento počet dostaneme tak, že od počtu V'(5, 10) všech pětičlenných variací s opakováním z daných deseti číslic odečteme počet všech takovýchto variací s opakováním, které mají na prvním místě nulu; těchto variací je V(4, 10). Hledaný počet pěticiferných čísel dané vlastnosti je roven číslu V'(5, 10)-V'(4, 10) = 105-104 = 104(10-1) = 90 000. Kolik značek Morseovy abecedy lze utvořit sestavením teček a čárek do skupin, v nichž záleží na pořadí a které jsou nejvýše čtyřčlenné? Řešení: Máme určit počet všech uspořádaných k-tic, kde k= 1, 2, 3,4, sestavených ze dvou prvků, které se v těchto ^-ticích mohou opakovat. Protože každá tato k-úce je /r-členná variace s opakováním ze dvou prvků, je hledaný počet značek roven součtu V'(í, 2) +V'(2, 2)+F'(3, 2) + V'(4, 2) = 21 +22 + 23 +24 = 30. Morseovu abecedu vytvořil Samuel F.B.Morse (1791-1872) pro telegrafický provoz na lince mezi městy Washington a Baltimore. Známý je signál SOS vysílaný v případě ohrožení a potřeby okamžité pomoci; v Morseove abecedě je to sled tří teček (písmeno S), tří čárek (písmeno O) a tří teček: • •-----• • 94 2. Kombinatorika Telegraf Cvičení | Určete počet všech přirozených čísel menších než jeden milion, v jejichž zápisu jsou pouze číslice 3 a 7, každá nejvýše šestkrát. tUM Kolik různých pěticiferných přirozených čísel lze napsat pomocí číslic 0, 2, 4, 6, 8, mohou-li se v zápisu těchto čísel opakovat? fjgcJI Na panelu je pět žárovek, z nichž každá může svítit červeně, zeleně nebo žlutě. Kolik různých signálů může být panelem vysláno, svítí-li vždy všech pět žárovek? | Určete všechna přirozená čísla x, pro něž platí: V (2, x) -10 = x ■ V''(2, 3). BM Určete počet všech pěticiferných čísel, v jejichž zápisu jsou pouze číslice 1, 3, 6, 9, každá nejvýše pětkrát. V článku 2.4 jsme probrali kombinace bez opakování, tj. skupiny, v nichž nezáleží na uspořádání a ve kterých se každý z daných prvků vyskytuje nejvýše jednou. Kombinace s opakováním se od těchto skupin odlišují tím, že jednotlivé prvky se v nich mohou opakovat vícekrát. Porovnejte tyto pojmy v následujícím srovnání: 2.1 0 Kombinace s opakováním Dvojčlenné kombinace ze tří prvků A, B, C bez opakování: s opako {A, B}, {A, C}, {B, C}. {A, A}, {A, 2.10 Kombinace s opakováním 95 Trojčlenné kombinace ze dvou prvků A, B bez opakování: s opakováním: neexistují - ze dvou prvků nelze utvořit {A, A, A}, {A, A, B}, trojčlennou skupinu, v níž se žádný prvek {A, B, B}, {B, B, B}. neopakuje. Obecně definujeme: Neuspořádaná Á-tice sestavená z daných n prvků tak, že každý je v ní nejvýše /:-krát. se nazývá A-tlenná kombinace s opakováním z /; prvků. Zatímco fe-členné kombinace bez opakování z prvků existují jen pro k existují k-c\cxmé kombinace s opakováním z n prvků i pro k> n. Ukážeme si nyní, jak se určí počet K'(k, n) všech ^-členných kombinací s opakováním z n prvků, a to na konkrétním příkladě pro k = n = 3. Pro dané tři prvky A, B, C si připravíme tři přihrádky, které budou odděleny dvěma přepážkami, znázorněnými svislými čárkami: 1. přihrádka | 2. přihrádka | 3. přihrádka Jednotlivé kombinace s opakováním z prvků A, B, C znázorníme tak, že do 1. přihrádky vložíme tolik koleček, kolikrát je v této kombinaci prvek A, do druhé tolik koleček, kolikrát je v této kombinaci prvek B, a do třetí tolik koleček, kolikrát je v této kombinaci prvek C: Trojčlenná kombinace s opakováním Znázornění pomocí koleček ze tří prvků A, B, C: {A, A, A} {A, A, B} {A, A, C} {A, B,B} {A, B, C} {A,C,C} {B, B, B} {B, B, C} {B,C, C} {C, C, C} ve třech přihrádkách: I <—> ■ < e • » m m i Z tohoto přehledného schématu je vidět, že každé trojčlenné kombinaci s opakováním ze tří prvků odpovídá právě jedno rozmístění tří koleček do tří přihrádek a také obráceně, každému tomuto rozmístění odpovídá právě jedna kombinace. Podíváte-li se však na každé z těchto rozmístění jiným způsobem, uvidíte, že každé z nich představuje permutaci s opakováním ze dvou prvků, z nichž jeden (svislá čárka) se opakuje dvakrát a druhý (kolečko) třikrát. 96 2. Kombinatorika Znamená to, že počet trojčlenných kombinací s opakováním ze tří prvků je roven počtu permutací s opakováním ze dvou prvků, z nichž jeden se opakuje dvakrát a druhý třikrát: ř/C3,3) = P'(3,2). Počet ^-členných kombinací s opakováním z n prvků určíme stejným způsobem: Každé této kombinaci s opakováním přiřadíme rozmístění k koleček do n přihrádek realizovaných n— 1 přepážkami a toto rozmístění si představíme jako permutaci s opakováním ze dvou prvků, z nichž jeden (kolečko) se opakuje Ä:-krát a druhý (svislá čárka) se opakuje (n— l)-krát. A protože toto přiřazení kombinací a permutací je vzájemně jednoznačné, platí K'(k, n) = P'(k, n-l). Tento výsledek dále upravíme: (n+k-lV. (n+fc-1)! fn + k-ť K'(k,n) = P'(k.n-\)=y k\{n-\)\ k\[(n+k-l)-k]\ V k Pro počet K'(k. n) všech /:-členných kombinací s opakováním z n prvků platí: n): Uvědomíme-li si, co udává kombinační číslo y ^ J. můžeme získaný výsledek formulovat i takto: Počet všech ^-členných kombinací s opakováním z n prvků je roven počtu všech Á-členných kombinací bez opakování z n+k - 1 prvků. V novinovém stánku se dá koupit pět druhů pohlednic. Kolik je možností koupě osmi pohlednic? (Předpokládáme, že ve stánku mají od každého druhu dostatečný počet pohlednic.) Řešení: Každých osm zakoupených pohlednic tvoří skupinu, ve které nezáleží na pořadí a v níž je každý z pěti různých druhů zastoupen nejvýše osmkrát. Pro zakoupení osmi pohlednic je proto tolik možností, kolikje osmičlenných kombinací s opakováním z pěti prvků. Dostáváme tak, že počet možností koupě osmi pohlednic je roven číslu Kolik různých trojúhelníků se dá sestrojit z úseček, jejichž délky v centimetrech jsou 4, 5, 6, 7, 8, 9? (Trojúhelníky mohou být i rovnostranné nebo rovnoramenné.) Řešení: Délky stran každého trojúhelníku tvoří neuspořádanou trojici, ve které je každá z těchto šesti délek nejvýše třikrát; jedná se tedy o trojčlenné kombinace s opakováním ze šesti prvků. Nesmíme však zapomenout, že tyto délky musí splňovat trojúhelníkovou nerovnost, podle které je součet délek každých dvou stran trojúhelníku větší než délka strany třetí. Snadno zjistíte, že z daných délek tuto nerovnost nesplňují pouze trojice: {4 cm, 4 cm, 8 cm}, {4 cm, 4 cm, 9 cm) a {4 cm, 5 cm, 9 cm}. Počet trojúhelníků, které se dají sestrojit z úseček daných délek, je tedy roven počtu 2.10 Kombinace s opakováním 97 trojčlenných kombinací s opakováním ze šesti prvků zmenšený o tři, tj. = ('3+^_1)-3= (T)-3 = 56-3 = 53. V sadě 32 karet je každá z následujících karet čtyřikrát: sedmička, osmička, devítka, desítka, spodek, svršek, král a eso; karty téže čtveřice jsou přitom rozlišeny těmito „barvami": červená, zelená, žaludy, kule. Určete, kolika způsoby se dá vybrat osm karet, jestliže se rozlišují pouze a) barvy, b) hodnoty jednotlivých karet. Řešení: a) Rozlišujeme-li pouze barvy, jde o to, kolika způsoby může být v osmi kartách každá z daných čtyř barev zastoupena. Tento počet způsobů je roven počtu K'(&, 4) neuspořádaných osmic s opakováním ze čtyř prvků, který snadno vypočteme: *