MASARYKOVA UNIVERZITA PŘÍRODOVĚDECKÁ FAKULTA Ústav matematiky a statistiky Diplomová práce Brno 2015 Monika Stančíková illK MASARYKOVA UNIVERZITA IMI * PŘÍRODOVĚDECKÁ FAKULTA ^xHIK<5? Ústav matematiky a statistiky Vytvoření webové učebnice kombinatoriky Diplomová práce Monika Stančíková Vedoucí práce: Mgr. Martin Panák, Ph.D. Brno 2015 Bibliografický záznam Autor: Monika Stančíková Přírodovědecká fakulta, Masarykova univerzita Ústav matematiky a statistiky Název práce: Vytvoření webové učebnice kombinatoriky Studijní program: Matematika Studijní obor: Učitelství matematiky pro střední školy, Učitelství informatiky pro střední školy Vedoucí práce: Mgr. Martin Panák, Ph.D. Akademický rok: 2014/2015 Počet stran: 10+106 Klíčová slova: Kombinatorika, pravidlo součtu, pravidlo součinu, variace, permutace, kombinace, faktoriál, kombinační číslo, binomická věta, Burnsideovo lemma, princip inkluze a exkluze Bibliographie Entry Author: Monika Stancikova Faculty of Science, Masaryk University Department of Mathematics and Statistics Title of Thesis: Web combinatorics textbook Degree Programme: Mathematics Field of Study: Supervisor: Academic Year: Number of Pages: Keywords: Upper Secondary School Teacher Training in Mathematics, Upper Secondary School Teacher Training in Informatics Mgr. Martin Panák, Ph.D. 2014/2015 10+106 Combinatorics, the rule of sum, the rule of product, variation, permutation, combination, factorial, combination number, the binomial theorem, Burnside's lemma, the inclusion-exclusion principle Abstrakt Cílem práce je přiblížit středoškolským studentům kombinatoriku ve formě webové prezentace. Kombinatorické pojmy jsou zde vysvětleny na základě řešení konkrétních problémů, příklady jsou obohacené o zajímavé ilustrace a interaktivní obrázky. Tato práce nemůže nahradit doporučené učební materiály, ale slouží jako rozšiřující doplněk při výuce. Práce je dostupná jako soubor pdf a ve formě webových stránek. Abstract The aim is to bring combinatorics to secondary school students in the form of website. Combinatorial terms are explained on the basis of the solution of concrete problems, examples are enriched with interesting illustrations and interactive images. This work can not replace the recommended teaching materials, but serves as an additional option in the classroom. Work is available as a pdf file and on web pages. Místo tohoto listu vložte kopii oficiálního (podepsaného) zadání práce. Poděkování Tímto bych ráda poděkovala Mgr. Martinu Panákovi, Ph.D. především za ochotu, vstřícnost a trpělivost, se kterými vedl moji diplomovou práci, za cenné rady i připomínky k ní. Dále bych chtěla poděkovat Bc. Markétě Kružliakové za užitečné poznámky ke grafické stránce webu, Mgr. Janu Šplíchalovi za korekturu češtiny v mé práci, Mgr. Martinu Stančíkovi za spoustu důležitých a zajímavých doporučení k celé práci a v neposlední řadě i s-technikům ze Servisního střediska IS MU za poskytnutí webové šablony. Prohlášení Prohlašuji, že jsem svoji diplomovou práci vypracovala samostatně s využitím informačních zdrojů, které jsou v práci citovány. Brno 13. května 2015 Monika Stančíková Obsah Úvod....................................................................... ix Přehled použitého značení................................................... x Kapitola 1. Základní kombinatorické pojmy................................. 1 1.1 Základní pravidla........................................ 1 1.1.1 Pravidlo součtu..................................... 1 1.1.2 Pravidlo součinu.................................... 1 1.1.3 Příklady na procvičení................................ 3 1.2 Variace bez opakování.................................... 8 1.2.1 Řešené příklady..................................... 8 1.2.2 Příklady k procvičení................................. 12 1.3 Permutace bez opakování.................................. 16 1.3.1 Řešené příklady..................................... 16 1.3.2 Příklady k procvičení................................. 19 1.4 Kombinace bez opakování.................................. 24 1.4.1 Úvodní příklady .................................... 24 1.4.2 Řešené příklady..................................... 27 1.4.3 Příklady k procvičení................................. 29 1.5 Variace s opakováním..................................... 34 1.5.1 Řešené příklady..................................... 34 1.5.2 Příklady k procvičení................................. 38 1.6 Permutace s opakováním................................... 41 1.6.1 Řešené příklady..................................... 41 1.6.2 Příklady k procvičení................................. 44 1.7 Kombinace s opakováním.................................. 49 1.7.1 Úvodní příklady .................................... 49 1.7.2 Řešené příklady..................................... 52 1.7.3 Příklady k procvičení................................. 53 1.8 Faktoriál a kombinační čísla................................ 58 1.8.1 Faktoriál.......................................... 58 1.8.2 Kombinační čísla.................................... 59 1.8.3 Binomická věta..................................... 63 1.9 Procvičování........................................... 68 - vii - Kapitola 2. Rozšiřující kombinatorické pojmy............................... 76 2.1 Burnsideovo lemma...................................... 76 2.1.1 Pojmy........................................... 76 2.1.2 Řešené příklady..................................... 78 2.1.3 Příklady k procvičení................................. 82 2.2 Princip inkluze a exkluze .................................. 88 2.2.1 Řešené příklady..................................... 88 2.2.2 Příklady k procvičení................................. 91 Závěr ...................................................................... 98 Přílohy..................................................................... 99 Seznam použité literatury................................................... 106 Úvod Kombinatorika je oblast matematiky, která je velmi zajímavá a využitelná v mnoha oborech, ale zároveň pro studenty jedna z nej náročnějších na pochopení. Také z mé dlouholeté praxe doučování studentů ze středních škol, jsem zjistila, že, ačkoli studenti jiné oblasti matematiky zvládali, s kombinatorikou měli potíže. Na základě této zkušenosti jsem se rozhodla přiblížit studentům kombinatoriku ve formě webové prezentace, která by byla přívětivá jak po grafické, tak po srozumitelné stránce. Má dosavadní učitelská praxe byla pouze z doučování, a proto ani tato prezentace nemůže nahradit doporučené učební materiály, ale slouží jako doplněk při výuce. Každý student je jedinečný, z toho důvodu jednotlivé pojmy může různý student pochopit na základě jiného příkladu stejného typu. Práci jsem proto koncipovala tak, aby obsahovala řešené příklady, které byly mým studentům blízké. Příklady j sem se snažila obohatit o zajímavé ilustrace, aby j sem vzbudila představivost a zaujala studenta při řešení. Využila jsem své znalosti i z mého druhého aprobačního oboru, informatiky, a poskytla studentům diplomovou práci ve webovém rozhraní. Práce je tak přístupná komukoli a odkudkoli prostřednictvím Internetu. Většina podkapitol obsahuje vždy alespoň dvě části - řešené příklady a příklady k procvičení. Na webových stránkách v části řešené příklady je uživateli řešení konkrétního příkladu zobrazeno implicitně a, pokud by chtěl, může si jej skrýt. V příkladech k procvičení je řešení implicitně schované a uživatel si jej může kdykoli zobrazit. Je tomu tak ve všech podkapitolách až na části Faktoriál a kombinační čísla a Procvičování, v nichž je řešení příkladů vždy implicitně skryté. Celá práce je rozdělena do dvou kapitol, Základní kombinatorické pojmy a Rozšiřující kombinatorické pojmy. První kapitola má 9 podkapitol. První z nich jsou Základní pravidla, pravidlo součtu a součinu. Následují Variace, Permutace a Kombinace bez opakování. Na to navazují podkapitoly Variace, Permutace a Kombinace s opakováním. Předposlední podkapitolou je Faktoriál a kombinační čísla, která také zahrnuje počítání příkladů s využitím binomické věty. Kapitola končí části Procvičování, kde jsou promíchány příklady všech doposud vysvětlených typů. Druhá kapitola rozšiřuje středoškolské učivo o Burnsideovo lemma a o Princip inkluze a exkluze. — ix— Přehled použitého značení Pro snazší orientaci v textu zde čtenáři předkládáme přehled základního značení, které v práci vyskytuje. N množina všech přirozených čísel S(X) množina všech permutací množiny X permutace na množině X ox orbita prvku x ď množina všech orbit množina pevných bodů permutace % Kapitola 1 Základní kombinatorické pojmy 1.1 Základní pravidla Základní kombinatorická pravidla, ačkoli jsou jen dvě, nám vystačí k řešení většiny kombinatorických úloh. Navzdory tomu, že jste o nich možná nikdy neslyšeli, určitě jste je někdy ve svém životě použili. Zřejmě se vám obě pravidla budou zdát jako samozřejmá, ovšem to jim neubírá na významu, obě budeme hojně používat ve všech částech této učebnice. 1.1.1 Pravidlo součtu Definice 1. Jsou-li Ai,Ä2, ... ,An konečné množiny, které mají po řadě pi,p2, ■ ■ ■ ,Pn prvků a jsou-li každé dvě disjunktní, pak počet prvků jejich sjednocení Ai UA2U ... UAn je roven px + p2+ ... + /?„. Příklad 1.1.1. Lehký příklad na objasnění definice Ve škole jsou dvě první třídy: 1. A a 1. B. Do třídy 1. A chodí 15 žáků, do třídy 1. B chodí 18 žáků. Kolik je ve škole prváků? Řešení: Tyto 2 množiny žáků (třídy) jsou konečné (počet žáků je konečný) a jsou disjunktní (žádný žák nemůže zároveň chodit do 1. A a do 1. B). Celkově v l.Aav l.Bje dohromady 15 + 18 = 33 žáků. 1.1.2 Pravidlo součinu Definice 2. Počet všech uspořádaných fc-tic, jejichž první člen lze vybrat n\ 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ů n^ způsoby, je roven n\ ■ n2- ... ■ n^. Příklad 1.1.2. Zvířata Adam má tři zvířata - ovci, psa a kočku. Rozhodl se, že dvě ze svých zvířat dá svým kamarádům. Jedno Honzovi a druhé Zbyňkovi. Kolik má možností, jak zvířata rozdělit -1- Kapitola 1. Základní kombinatorické pojmy_2 mezi Honzu a Zbyňka? Řešení: Poznámka: Řešení tohoto příkladu je vysvětleno také pomocí interaktivního obrázku, který je uveden v příloze 1. Přepis řešení: Adam chce dát 1 zvíře Honzovi(H) a 1 zvíře Zbyňkovi(Z): HZ^__ Pro Honzu vybírá 1 zvíře ze 3. Má tedy 3 různé možnosti, jak ho obdarovat: 3 _ Pro každou ze 3 možností výběru zvířete pro Honzu, má pro Zbyňka 2 možnosti, jak jej obdarovat: 3 2 Proto má celkem: 3-2 = 6 možností, jak zvířata rozdělit mezi své přátele. Příklad 1.1.3. Oblečení Bára má tři různá trička a pět různých sukní. Kolika způsoby si může vzít tričko a sukni, aby pokaždé vypadala jinak? V TV 0 000 0 Obrázek 1.1: Tři trička a pět sukní, zdroj: [11] Řešení: Počítáme počet možností, jak si Bára může vybrat 1 tričko(T) a k tomu 1 sukni(S): TS __ Bára má 3 různé možnosti, jak si vybrat tričko: 3 _ Potom, co si vybrala tričko, má 5 možností, jak si vybrat sukni: 3 5 Celkem má Bára 3-5 = 15 různých způsobů, jak se obléct. Příklad 1.1.4. Čísla Určete počet všech trojciferných přirozených čísel, v jejichž dekadickém zápisu se každá číslice vyskytuje nejvýše jednou. Kapitola 1. Základní kombinatorické pojmy 3 \A1 789 236 2$^ S03 460 Obrázek 1.2: Příklad čísel, jenž vyhovují zadání, i čísel, jenž nevyhovují zadání. Zdroj: autor. Počet různých číslic je 10, jsou to: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Pro vytvoření trojciferného čísla, potřebujeme 3 číslice —>___ Na první cifře nemůže být 0, proto máme 9 různých číslic, které můžeme použít: 9 _ _ Na druhé cifře už může být i 0, proto máme 10 možných číslic. Ale nesmíme použít tu číslici, která je na první cifře (číslice se nesmí opakovat), možností je tedy 9: 9 9 _ Pro třetí cifru ze všech možných číslic odečítáme dvě, které j sme použili pro první a druhou cifru, dostáváme 8 různých číslic: 9 9 8 Celkem takových čísel je: 9 • 9 • 8 = 648. 1.1.3 Příklady na procvičení Příklad 1.1.5. Ze Lhotky do Hradce vedou 3 různé cesty, z Hradce do Budína vedou 4 různé cesty. Určete počet způsobů, jimiž lze vybrat trasu: A) ze Lhotky přes Hradec do Budína a zpět. B) ze Lhotky přes Hradec do Budína a zpět tak, že žádná cesta není použita dvakrát. C) ze Lhotky přes Hradec do Budína a zpět tak, že právě jedna z cest je použita dvakrát, a to cesta mezi Lhotkou a Hradcem. Řešení: Řešení: Cesty si označíme: A: Lhotka —> Hradec B: Hradec —> Budín -1 ZE Hradec —> Lhotka D C: Budín —> Hradec a in 0 Obrázek 1.3: Označení cest, zdroj: autor Kapitola 1. Základní kombinatorické pojmy 4 A) Na trasu A máme 3 možné cesty, na trasu B 4 možné cesty, na trasu C opět 4 cesty a na trasu D opět 3 cesty: ABCD-^3443 Celkem: 3-4-4-3 = 144. B) Na trasu A a B máme stejný počet možností jako v případě 1.: A B C D —>■ 3 4___ Na trasu C už nemůžeme použít cestu, která byla vybrána pro trasu B. K výběru cesty máme tedy o jednu méně: 4-l=3.ABCD—^343_. Obdobně pro trasu D, jsou tři různé cesty, ale jednu z nich jsme už vybrali, tedy 3 -1=2. Celkem: 3 • 4 • 3 • 2 = 72. C) Na trasu A a B máme stejný počet možností jako v případě 1.: A B C D 3 4___ Trasa C má být jiná než B, tedy máme o jednu možnost méně: ABCD—^343_. Trasa D má být stejná jako trasa A, ale tu už máme vybranou, tedy máme jedinou možnost: ABCD^ 343 1. Celkem: 3 • 4 • 3 • 1 = 36. Příklad 1.1.6. ____ Čtverec o straně délky 4 cm je rozdělen rovnoběžkami se ---- stranami na 16 stejných čtverců. Určete, kolik je v daném obrazci I I I I čtverců. [1] Obrázek 1.4: Čtverec, zdroj: autor Řešení: Všechny čtverce rozdělíme do disjunktních skupin ČI, Č2, Č3 a Č4 tak, že ve skupině ČI jsou všechny čtverce o straně délky 1 cm, ve skupině Č2 jsou všechny čtverce o straně délky 2 cm, ve skupině Č3 jsou všechny čtverce o straně délky 3 cm a ve skupině Č4 jsou všechny čtverce o straně délky 4 cm. Ve skupině ČI je 16 čtverců, v Č2 je 9 čtverců, v Č3 jsou 4 čtverce a v Č4 je 1 čtverec. Celkový počet čtverců v daném obrazci je roven 16 + 9 + 4+1 =30. Příklad 1.1.7. Biatlonistka Katka má 5 zlatých, 3 stříbrné a 6 bronzových medailí, každou z jiné soutěže. Chtěla by si některých pět ze svých medailí pověsit na poličku, která má přesně 5 háčků na pověšení. Kolik různých možností Katka má, aby si medaile rozvěsila tak, že by na prvním háčku byla jedna ze zlatých medailí, na druhém jedna ze stříbrných, na třetím jedna z bronzových a na posledních dvou libovolná medaile? Řešení: Na poličce je pět háčků: 1.2.3.4.5._____ Na první háček můžeme vybrat jednu z 5 zlatých medailí, máme tedy 5 možností výběru: 5____ Kapitola 1. Základní kombinatorické pojmy 5 Po výběru na první háček můžeme na druhý háček vybrat jednu ze 3 stříbrných medailí: 5 3 ___ Po předešlém výběru můžeme na třetí háček vybrat jednu z 6 bronzových medailí: 5 3 6 __ Na čtvrtý háček nám po výběru prvních tří zbývá: 4 zlaté, 2 stříbrné a 5 bronzových medailí, vybíráme tedy libovolnou medaili z 11: 5 3 6 11 _ Na poslední háček po výběru prvních 4 nám zbývá 10 medailí: 5 3 6 11 10 Celkem má Katka možností: 5 • 3 • 6 • 11 • 10 = 9900. Příklad 1.1.8. Určete celkový počet tahů koněm na šachovnici 8x8. [1] Řešení: Počet tahů koněm z daného pole na šachovnici závisí na poloze tohoto pole na šachovnici. Rozdělíme si tedy všechna pole šachovnice do 5 skupin: A, B, C, D, E (viz obrázek 1.5). C\ \ JD Obrázek 1.5: Rozdělení části šachovnice podle možných pohybů koně, zdroj: autor Z rohového pole A má kůň 2 možné tahy, z pole typu B tři tahy, z pole typu C čtyři tahy, z pole typu D šest tahů a z pole typu E osm možných tahů. Celkový počet tahů koně na šachovnici 8x8 je: 4 • 2 + 8 • 3 + 20 • 4 + 16 • 6 + 16 • 8 = 336. Příklad 1.1.9. Kolika způsoby lze vybrat na šachovnici 8x8 jedno bílé a jedno černé pole? Kolika způsoby to lze učinit, nesmějí-li vybraná pole ležet ve stejném řádku ani ve stejném sloupci? ABCDEFGH Obrázek 1.6: Šachovnice, zdroj: autor Kapitola 1. Základní kombinatorické pojmy 6 Řešení: Bílé pole lze vybrat 32 způsoby, černé rovněž. Celkový počet způsobů výběru je tedy v prvním případě roven 32 • 32 = 1024. Vybereme-li v druhém případě jedno bílé pole (32 způsobů), lze černé vybrat už jen z řádků a sloupců, v nichž vybrané bílé pole neleží, tj. 24 způsobů. Počet výběrů je tedy 32 • 24 = 738. Příklad 1.1.10. Kolika způsoby lze z úplného souboru domina (28 kostek) vybrat dvě tak, abychom je mohli přiložit k sobě? Dvě kostky domina lze přiložit k sobě, jestliže se nějaký počet ok vyskytuje zároveň na obou kostkách. Řešení: Vybereme nejprve první kostku, to lze 28 způsoby, v 7 z nich bude v obou polích stejný počet ok (00, 11, 22,..., 66), ve zbylých 21 případech bude počet ok v obou polích vybrané kostky různý. Rozdělme tedy všechny uvažované dvojice kostek do dvou skupin podle toho, jakého z obou výše popsaných typů je první vybraná kostka. V prvním případě lze druhou kostku vybrat 6 způsoby (např. ke kostce 00 přidáme některou z kostek 01,02,..., 06). Ve druhém případě vybereme druhou kostku 12 způsoby (např. ke kostce 01 lze vybrat některou z kostek 00, 02, 03, ..., 06, 11,12,..., 16). Podle pravidla součinu je v prvním případě počet výběrů 7 • 6 = 42, ve druhém případě 21 • 12 = 252 a podle pravidla součtu je celkový počet výběrů roven 42 + 252 = 294. Protože však na pořadí vybraných kostek nezáleží, je celkový počet výběrů poloviční, tedy 294/2 = 147 (např. dvojice kostek 01 a 16 je započítána i jako 16 a 01). Příklad 1.1.11. Určete počet všech možných tanečních párů z 15 chlapců a 10 děvčat. Řešení: Celkový počet tanečních párů je podle pravidla součinu roven 15 • 10 = 150. Příklad 1.1.12. V košíku je 12 různých jablek a 10 různých hrušek. Petr si má z něho vybrat jedno ovoce tak, aby Věra, která si po něm vybere jedno jablko a jednu hrušku, měla co největší možnost výběru. Jaké ovoce si má Petr vybrat? [2] Řešení: Pokud si Petr vybere jablko, v košíku zůstane 11 jablek a 10 hrušek a počet možných výběrů pro Věru bude: 11-10=110. Pokud si Petr vybere hrušku, počet možných výběrů pro Věru bude: 12-9= 108. Aby Věra měla co největší možnost výběru, musí si Petr vzít jablko. Kapitola 1. Základní kombinatorické pojmy 7 Příklad 1.1.13. Ve třídě 5. A chodí 14 žáků na němčinu a 13 na francouzštinu. Každý žák navštěvuje právě jeden z uvedených předmětů. Kolika způsoby lze vybrat dvojici na týdenní službu tak, aby měl službu jeden žák z němčiny a jeden žák z francouzštiny? Kolik let by žáci museli chodit do školy, aby se všechny tyto dvojice vystřídaly? (Počítejte, že školní rok má 33 vyučovacích týdnů.) Řešení: Počet různých dvojic je 14 • 13 = 182. 182/33 = 5,515. Aby se všechny dvojice vystřídaly, museli by žáci chodit do školy přibližně 5 a půl roku. Příklad 1.1.14. Určete počet čtyřciferných přirozených čísel, které začínají cifrou 1 a nekončí cifrou 2, nebo končí cifrou 2 a nezačínají cifrou 1. [4] Řešení: Všechna čísla můžeme rozdělit do dvou disjunktních množin. První množina obsahuje čísla, která začínají cifrou 1 a nekončí cifrou 2. Druhá množina obsahuje čísla, která nezačínají cifrou 1 a končí cifrou 2. Celkový počet čísel ze zadání dostaneme podle pravidla součtu tak, že sečteme počty čísel v obou množinách. Počet prvků v první množině je: 1 • 10 • 10 • 9 = 900. První cifru známe, na každou z dalších cifer můžeme vybrat z 10 různých možností a při volbě poslední číslice nemůžeme použít cifru 2. Počet prvků v druhé množině je: 8 • 10 • 10 • 1 = 800. Na první cifře nemohou být číslice 0 a 1, na každou z dalších cifer můžeme vybrat z 10 různých možností a poslední cifra je určená. Celkový počet čísel odpovídajících zadání je 900 + 800 = 1700. Kapitola 1. Základní kombinatorické pojmy 8 1.2 Variace bez opakování Další z kombinatorických pojmů jsou variace. Tento pojem si vysvětlíme na příkladu s vlajkami. Chceme obarvit dvěma různými barvami vlajku sestávající se ze dvou pruhů, přičemž máme na výběr z 5 různých barev. Vybíráme tedy skupinu prvků z určité množiny těchto prvků, přičemž je důležité pořadí, v jaké prvky (barvy) uspořádáme. Jedna variace je právě jedna taková vybraná skupina prvků (dvojice barev). Nás zajímá, kolik takových variací, tedy kolik různých vlajek, lze vytvořit? Prvky, které vybíráme, mezi sebou rozlišujeme, jsou navzájem různé a neopakují se. Zkusíme si vše přiblížit na následujících příkladech. 1.2.1 Řešené příklady Příklad 1.2.1. Vlajky Mirek si chce vytvořit vlastní vlajku. Chtěl by, aby byla složena ze tří různobarevných svislých pruhů. K dispozici má látky 5 různých barev - fialovou, červenou, modrou, zelenou a žlutou. A) Určete, kolik různých vlajek si může Mirek sestavit. B) Kolik takových vlajek má jeden pruh žlutý? C) Kolik vlajek neobsahuje červený pruh? Obrázek 1.7: Vlajka, zdroj: autor Řešení: Poznámka: Řešení první části tohoto příkladu je vysvětleno také pomocí interaktivního obrázku, který je uveden v příloze 2. Přepis řešení: A) Doplňujeme barvy na tři různá místa na vlajce, vybíráme tedy 3 různé barvy z pěti celkem —>___ Na první místo vybíráme 1 z 5 barev, máme tedy 5 různých možností: 5 __ Na druhé místo vybíráme už jen ze 4 barev, protože jednu barvu jsme již použili a barvy se nemohou opakovat: 54_ Na třetí místo vybíráme už jen ze 3 barev, protože 2 barvy jsme již použili a barvy se nemohou opakovat: 543 Výsledek: 5 • 4 • 3 = 60. Proč počet možností pro každý pruh mezi sebou násobíme? Používáme pravidlo součinu. Kapitola 1. Základní kombinatorické pojmy 9 B) Vlajka má mít jeden pruh žlutý, proto může nastat jedna z těchto tří situací: Ž__ _Ž_ __Ž Obrázek 1.8: Eventuální umístění žlutého pruhu na vlajce, zdroj: autor Umístění žluté barvy tímto máme určené. Na toto místo máme pouze jednu možnost výběru barvy - žlutou: 1 __ _ 1 _ __1 Poté nám zůstanou 4 barvy, kterými můžeme doplnit další pruh. Po doplnění tohoto pruhu nám zůstanou 3 barvy na poslední pruh: 1 4 3 4 1 3 4 3 1 Jednotlivé možnosti: 1-4-3 = 12, 4-1-3 = 12, 4-3-1 = 12. Máme 3 disjunktní skupiny vlajek, celkový počet vlajek s jedním žlutým pruhem je podle pravidla součtu: 12+12+12 = 36. C) Pokud vlajka nemá červený pruh, je počet barev na vlajku je 4, získáváme výsledek: 4-3-2 = 24. Příklad 1.2.2. Předseda, místopředseda ... Sportovní klub Komárov vybírá osoby na pozice předsedy, místopředsedy, účetního a trenéra. K dispozici má 8 uchazečů a 5 uchazeček. Určete: A) Kolika způsoby z nich lze vybrat tyto funkcionáře? B) Kolika způsoby lze vybrat funkcionáře tak, aby předseda byl muž a místopředseda žena nebo obráceně? C) Kolika způsoby lze vybrat funkcionáře tak, aby právě jedním z nich byla žena? Řešení: A) 8 mužů + 5 žen = 13 lidí celkem. Předseda Místopředseda Účetní Trenér —>____ Pro výběr předsedy máme 13 možností, poté pro místopředsedu 12 možností, potom pro účetního 11 možností a nakonec pro trenéra 10 možností. Podle pravidla součinu dostáváme výsledek: 13-12-11-10= 17160. B) Příklad si rozdělíme na 2 různé, ale analogické situace: I. Předsedaje muž a místopředseda je žena: Na místo předsedy vybíráme jednoho z osmi mužů, na místo místopředsedy jednu Kapitola 1. Základní kombinatorické pojmy 10 z pěti žen: 8 5 _ _ Zbývá 7 mužů + 4 ženy = 11 lidí. Opět použijeme pravidlo součinu a výsledek je: 8 • 5 • 11 • 10 = 4400. II. Předsedaje žena a místopředseda je muž: 5 8 _ _ Zbývá 4 ženy + 7 mužů = 11 lidí. 5-8-11-10 = 4400. Užitím pravidla součtu dostáváme celkový výsledek: 4400 + 4400 = 8800. C) Nyní musíme uvažovat zvlášť situace, kdy žena je na místě předsedy (P) nebo místopředsedy (M) nebo účetního (U) nebo trenéra (T): P-žena: 5-8-7-6 = 1680, M-žena: 8-5 -7-6= 1680, Ú-žena: 8 • 7 • 5 • 6 = 1680, T-žena: 8-7-6-5 = 1680, 1680 + 1680 + 1680 + 1680 = 6720. Příklad 1.2.3. Čísla A) Určete počet všech nejvýše čtyřciferných přirozených čísel, v jejichž dekadickém zápisu se každá číslice vyskytuje nejvýše jednou? B) Kolik z nich je menších než 6000? 30 82 ? 236 A^1503 1976 Obrázek 1.9: Ukázka vyhovujících a nevyhovujících čísel, zdroj: autor Řešení: A) Úlohu si rozdělíme na 4 různé situace: I. Výběr čtyřciferných čísel. II. Výběr tříciferných čísel. III. Výběr dvouciferných čísel. IV. Výběr jednociferných čísel. I. Chceme určit počet čtyřciferných čísel, v jejichž dekadickém zápisu se číslice neopakují. Na první cifru můžeme umístit číslice: 1, 2, 3, 4, 5, 6, 7, 8, 9. Celkem 9 číslic. (Proč ne nulu? Čísla mají být čtyřciferné.) 9___ Na druhé místo už můžeme umístit i nulu: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 - celkem 10 číslic, ale odečítáme jednu číslici, kterou jsme již vybrali (číslice se nemohou opakovat): 99__ Kapitola 1. Základní kombinatorické pojmy 11 Na třetí místo analogicky: 10 číslic minus 2 z předchozích výběrů: 9 9 8 _ Jako poslední cifru můžeme zvolit opět jednu z 10 číslic mínus 3 z předchozích výběrů: 9 9 87 Celkově: 9 • 9 • 8 • 7 = 4536. II. Pro tříciferná čísla analogicky: 9 • 9 • 8 = 648. III. Pro dvouciferná čísla analogicky: 9-9 = 81. IV. Jednociferných přirozených čísel je: 9. Vypočítali jsme, kolik máme možností pro 4 různé (disjunktní) situace (pro čtyřciferné číslo, tříciferné, dvouciferné a jednociferné číslo). Dohromady podle pravidla součtu: 4536 + 648 + 81 + 9 = 5274. B) Postup řešení je podobný jako v úloze A). Rozdíl bude pouze pro výpočet čtyřciferných čísel. Na prvním místě mohou být číslice: 1, 2, 3, 4, 5 - celkem 5 možných číslic, proto dostáváme: 5 • 9 • 8 • 7 = 2520. Počet všech nejvýše čtyřciferných přirozených čísel menších než 6000 je: 2520 + 648+ +81+9 = 3258. Definice 3. fc-členná variace z n prvků je uspořádaná fc-tice sestavená z těchto prvků tak, že se v ní každý vyskytuje nejvýše jednou. Z předchozích úvah vyplývá následující věta: Veta 1. Počet V(k,n) všech k-členných variací z n prvků je: V(k,n) =n-(n- 1) ■ (n - 2) •... • (w -k+ 1). Pokud rozpoznáme, že se v úloze ptáme na počet jistých variací, je možné přímo použít vzorec. Vypočítáme si některé již řešené příklady s využitím vzorce. Příklad 1.2.1. Vlajky - podle vzorce Mirek si chce vytvořit vlastní vlajku. Chtěl by, aby byla složena ze tří různobarevných svislých pruhů. K dispozici má látky 5 různých barev - fialovou, červenou, modrou, zelenou a žlutou. Určete, kolik různých vlajek si může Mirek sestavit. Řešení: Kapitola 1. Základní kombinatorické pojmy 12 Počet prvků, z nichž vybíráme: n = 5. Kolika člennou variaci vybíráme: k = 3. V(3,5) =5-(5 - 1)-(5-2) = 5-4-3 = 60. Příklad 1.2.2. Predseda, místopředseda ... - podle vzorce Sportovní klub Komárov vybírá osoby na pozice předsedy, místopředsedy, účetního a trenéra. K dispozici má 8 uchazečů a 5 uchazeček. Určete kolika způsoby z nich lze vybrat tyto funkcionáře? Řešení: Počet prvků, z nichž vybíráme: « = 8 + 5 = 13. Kolika člennou variaci vybíráme: k = 4 (předsedu, místopředsedu, účetního a trenéra). V(4,13) = 13-(13-1)-(13-2)-(13-3) = 13 • 12-11 • 10 = 17160. Shrnutí počítání podle vzorce: Použití vzorce může urychlit řešení úlohy, vždy je však nezbytné do úlohy nejprve proniknout. 1.2.2 Příklady k procvičení Příklad 1.2.4. A) Určete, kolika způsoby lze sestavit rozvrh na pondělí pro 7. třídu ZŠ Hoštice, v níž se vyučuje 11 předmětů. Každý předmět je vyučován maximálně jednou denně a celkově se v pondělí vyučuje 6 vyučovacích hodin. B) Kolika způsoby lze sestavit takový rozvrh, který má jako druhý vyučovací předmět matematiku? (Matematika je jeden z jedenácti předmětů.) Řešení: A) 11 • 10-9-8-7-6 = 332640 [= V(6,ll)]. B) 10-l-9-8-7-6 = 30240. Příklad 1.2.5. Žáci třetí třídy chtějí nacvičit divadlo na vystoupení ke Dni matek. Paní učitelka musí vybrat 4 žáky z 23 žáků (16 chlapců a 7 děvčat) na divadelní role: Král Richard, služebná Agáta, podkoní Matěj a princezna Tiana. A) Kolik různých čtveřic žáků může na tyto role vybrat? B) Kolik různých čtveřic žáků může na tyto role vybrat tak, aby služebná i princezna byly dívky? (Král i podkoní žádné omezení nemají.) C) Kolik různých čtveřic žáků může na tyto role vybrat tak, aby služebná a princezna byla děvčata a aby král a podkoní byli chlapci? Řešení: Kapitola 1. Základní kombinatorické pojmy 13 A) 23-22-21-20 = 212520 [V(4,23)] B) 7-6-21-20= 17640 C) 7-6-16-15 = 10080 Příklad 1.2.6. Soňa zapomněla své telefonní číslo. Vzpomíná si, že mělo předčíslí 773 a poté jej tvořilo 6 různých číslic takových, že první tři číslice byly sudé nebo nula, další dvě číslice byly liché a poslední si nepamatuje vůbec. Kolik existuje telefonních čísel, která by odpovídala Soninu popisu? Řešení: Označme si číslice: S-sudá číslice nebo nula, L-lichá číslice, Č-libovolná číslice: SSSLLČ 5-4-3-5-4-(2 + 3) = 6000 "A/a přibližné telefonní číslo se nedovoláme. Daniela Fischer Obrázek 1.10: Citát od Daniely Fischer, zdroj: autor Příklad 1.2.7. Na dětském táboře dostalo 45 dětí za úkol vytvořit si každý svou vlajku. Přesné znění úkolu bylo: Vlajka bude složena ze tří různobarevných svislých pruhů. K dispozici máte látky 5 různých barev - černá, červená, modrá, oranžová a žlutá. A) Je možné, aby každé dítě mělo svou originální vlajku? B) Kolik lze sestavit vlajek se žlutým pruhem uprostřed? C) Kolik lze sestavit vlajek, které nemají prostřední pruh červený? Řešení: A) Počet různých vlajek, které lze sestavit, je: 5 • 4 • 3 = 60[= V(3,5)], což je více než je počet dětí (45 < 60), proto je možné, aby si každé dítě vytvořilo svou originální vlajku. B) Prostřední pruh má barvu určenou (= 1 možnost), na ostatní zbývají 4 barvy: 4-1-3 = 12 C) Můžeme počítat dvěma způsoby: A) Od počtu všech vlajek odečteme ty, které mají prostřední barvu červenou. Počet všech vlajek 5 • 4 • 3 = 60. Počet vlajek s červenou uprostřed 4 • 1 • 3 = 12. Počet vlajek bez prostředního pruhu červeného: 60 — 12 = 48. Kapitola 1. Základní kombinatorické pojmy 14 B) Máme obarvit 3 pruhy na vlajce. Začneme od prostředního pruhu. Na něj máme pouze 4 barvy (červenou nechceme): _4_ Teď už můžeme použít i červenou barvu, celkem je tedy 5 barev mínus ta barva, kterou už jsme vybrali pro prostřední pruh. Dostáváme: 4-4-3 = 48 Příklad 1.2.8. Určete počet všech pěticiferných přirozených čísel, v jejichž dekadickém zápisu se každá číslice vyskytuje nejvýše jednou. Kolik z nich je dělitelných pěti? Řešení: Počet takových pěticiferných čísel je: 9 • 9 • 8 • 7 • 6 = 27216. Dělitelné pěti jsou čísla, jejichž poslední cifra je: 0 nebo 5. Poslední cifra je 0: 9 • 8 • 7 • 6 • 1 = 3024, poslední cifra je 5: 8 • 8 • 7 • 6 • 1 = 2688. Celkem 3024 + 2688 = 5712. Příklad 1.2.9. Určete počet všech nejvýše čtyřciferných přirozených čísel s různými ciframi, která jsou sestavena z číslic 2, 4, 5, 6, 7, 9. Kolik z nich je sudých? Řešení: Takových nejvýše čtyřciferných čísel je: 6-5-4-3+ 6-5-4+ 6-5 +6 = 360+120 +30 + 6 = 516. [=V(4,6)+V(3,6)+V(2,6)+V(1,6)] Sudých: poslední cifra je 2, 4 nebo 6: 5.4.3.3 + 5.4.3 + 5.3 + 3 = 180 + 60+15 + 3 = 258. Poznámka: V druhém případě jsme si mohli počítání ulehčit, všech čísel sestavených z číslic 2, 4, 5, 6, 7, 9 je 516, a jelikož je přesně polovina z číslic 2, 4, 5, 6, 7, 9 sudá, proto také v polovině všech možností bude poslední cifra sudá: 516/2 = 258. Příklad 1.2.10. V naší nejvyšší fotbalové lize je 16 týmů. Kolik je různých možností obsazení prvních tří míst? Řešení: 16-15-14 = 3360 [=V(3,16)] Kapitola 1. Základní kombinatorické pojmy 15 Příklad 1.2.11. Určete počet všech čtyřciferných přirozených čísel s různými číslicemi, která jsou sestavena z číslic 1, 2, 3, 4, 5. Kolik z nich je dělitelných 5? Kolik z nich je lichých? Řešení: Takových čtyřciferných čísel je: 5 • 4 • 3 • 2 = 120 [= V (4,5)]. Dělitelných pěti: poslední cifra je 5: 4 • 3 • 2 • 1 = 24. Lichých: poslední cifra je 1, 3 nebo 5: 4 • 3 • 2 • 3 = 72. Příklad 1.2.12. Katka prodává svíčky, nyní má k dispozici 8 různě barevných vosků. Kolik různých svíček může vyrobit, pokud by chtěla, aby každá svíčka byla složena z 5 různobarevných vodorovných pruhů? Kolik různých svíček může vyrobit, pokud nejvyšší pruh bude modrý a nejnižší fialový nebo naopak? Kolik různých svíček může vyrobit, pokud by chtěla, aby prostřední 3 pruhy byly červené, oranžové a žluté barvy? Řešení: Počet různých svíček je: 8-7-6-5-4 = 6720. [=V(5,8)] S nejvyšším pruhem modrým a nejnižším fialovým či naopak je : 2 • 6 • 5 • 4 • 1 = 240. Prostřední 3 barvy jsou červená, oranžová a žlutá: 8-3-2-l-7 = 336. Obrázek 1.11: Ukázka svíčky, zdroj: autor Kapitola 1. Základní kombinatorické pojmy 16 1.3 Permutace bez opakování Permutace nebo též pořadí je název pro uspořádání prvků určité skupiny (např. seřazení 5 lidí do fronty). I nyní nás bude zajímat počet všech různých uspořádání, které můžeme s danými prvky učinit (např. kolika způsoby můžeme seřadit 5 lidí do fronty?). Rozdíl oproti variacím je pouze ten, že uspořádáváme všechny prvky. Opět tyto prvky mezi sebou rozlišujeme, jsou navzájem různé, neopakují se a opět záleží na jejich pořadí. 1.3.1 Řešené příklady Příklad 1.3.1. Zákon K návrhu zákona se mají postupně vyjádřit 4 poslanci: Adámek, Beneš, Coufal a Dupák. Určete počet: A) všech možných pořadí jejich vystoupení; B) všech možných pořadí jejich vystoupení, v nichž Dupák vystupuje hned po Adámkovi; C) všech možných pořadí jejich vystoupení, v nichž Beneš vystupuje kdykoli po Dupákovi. Řešení: A) Zajímá nás pořadí 4 poslanců:____ Na první místo můžeme vybrat jednoho ze 4, máme tedy 4 možnosti výběru: 4___ Zbývají nám 3 poslanci. Na druhé místo máme tedy 3 možnosti výběru: 4 3 _ _ Po výběru poslanců na první a druhé místo nám zůstávají 2 poslanci. Na třetí místo máme proto 2 možnosti výběru: 4 3 2 _ A už nám zůstal jen jeden poslanec, který půjde jako poslední: 4 3 2 1 Výsledek: 4 • 3 • 2 • 1 = 24. B) Dupák má jít hned po Adámkovi. Tak je spojíme dohromady a vznikne nám jeden celek: Adámek + Dupák —ř AD. (Dupák jde vždy po Adámkovi, proto ho můžeme v možnostech sloučit s Adámkem. Jeho výstup je určen tím, kdy vybereme Adámka.) Hledáme tedy rozmístění pro 3 „poslance", pro Beneše, Coufala a AD: —>___ Pro výběr prvního v pořadí máme na výběr ze 3 možností: 3 _ _ Pro další vystoupení máme už jen 2 možností: 3 2 _ A poslední možnost: 3 2 1 Obrázek 1.12: Socha spravedlnosti, zdroj: [11] Kapitola 1. Základní kombinatorické pojmy 17 Výsledek: 3-2-1=6. Můžeme si ověřit, že opravdu v těchto šesti možnostech máme rozmístěné 4 poslance podle zadání: 1) AD B C 2) AD C B 3) B AD C 4) C AD B 5) B C AD 6) C B AD C) Uvědomme si, že pořadí, kdy je Beneš před Dupákem, a pořadí, kdy je Beneš po Dupákovi, je stejný počet. Proto hned můžeme vidět, že výsledek je tedy počet všech pořadí děleno dvěma: (4-3-2-l)/2 = 24/2 = 12. Příklad 1.3.2. Předseda, místopředseda ... Vedení sportovního klubu 1. FK Zborovice tvoří 3 muži a 2 ženy. Určete: A) Kolika způsoby z nich lze vybrat předsedu, místopředsedu, účetního, hospodáře a trenéra? B) Kolika způsoby z nich lze vybrat funkcionáře jak v případě 1. tak, aby ve funkci předsedy byl muž a ve funkci místopředsedy žena nebo obráceně? Řešení: A) 3 muži + 2 ženy = 5 lidí celkem. P M U H T ( = Předseda Místopředseda Účetní Hospodář Trenér) _____^ 5 43 2 1 Výsledek: 5 • 4 • 3 • 2 • 1 = 120. (Připomeňme si, proč se čísla násobí. Používáme totiž pravidlo součinu.) B) Úlohu si rozdělíme na 2 různé situace: I. P-muž a M-žena: Na místo předsedy vybíráme jednoho ze tří mužů, na místo místopředsedy jednu ze dvou žen: 3 2___ Zbývají 2 muži + 1 žena = 3. 3-2-3-2-1 = 36. II. P-žena a M-muž: Na místo předsedy vybíráme jednu ze dvou žen, na místo místopředsedy jednoho ze tří mužů: 23___ Zbývají 2 muži + 1 žena = 3. 2-3-3-2-1 = 36. Výsledek: 36 + 36 = 72. (Připomeňme si, proč čísla sčítáme. Používáme totiž pravidlo součtu.) Kapitola 1. Základní kombinatorické pojmy 18 Příklad 1.3.3. Čísla A) Určete počet všech pěticiferných přirozených čísel, v jejichž dekadickém zápisu se vyskytují číslice 0, 4, 5, 6, 7 a každá z nich právě jednou? B) Kolik z nich je menších než 60 000? C) Kolik z nich je dělitelných 5? Řešení: A) Pěticiferné číslo:_____ Na první cifru můžeme umístit jednu ze čtyř číslic: 4____ Na další cifru máme k dispozici pět číslic bez jedné, kterou jsme už vybrali: 4 4___ A postupujeme dále, jak jsme zvyklí: 4 4 3 2 1 Celkově: 4-4-3 -2-1 = 96. B) Na první cifru můžeme dát jen jednu ze dvou číslic: 4 a 5. (Proč? Čísla mají menší než 6000.) Celkově: 2-4-3-2-1=48. C) Pěticiferné číslo je dělitelné pěti právě tehdy, když končí cifrou 0 nebo 5. Každou situaci si vypočítáme zvlášť. Číslo končící číslicí 0: na poslední cifru máme jen jednu možnost:____1 . Rozmístíme ostatní číslice: 4 • 3 • 2 • 1 • 1 = 24. Číslo končící číslicí 5: na poslední cifru máme jen jednu možnost:____1 . Rozmístíme ostatní číslice: 3-3-2-1-1 = 18. Celkem: 24+18 = 42. Definice 4. Permutace n prvků je uspořádaná w-tice sestavená z těchto prvků tak, že se v ní každý vyskytuje právě jednou. Jinak řečeno: Permutace n prvků jsou právě w-členné variace z těchto prvků. Definice 5. Pro každé přirozené číslo n definujeme: w! = w-(w-l)-...-2-l, kde0! = l. Číslo n\ čteme jako „n faktoriál". Z předchozích úvah vyplývá následující věta: Veta 2. Pro počet P (n) všech permutací z n prvků platí P {ti) = n\. Pokud rozpoznáme, že se v úloze ptáme na počet jistých permutací, je možné přímo použít vzorec. Vypočítáme si některé již řešené příklady s využitím vzorce. Kapitola 1. Základní kombinatorické pojmy 19 Příklad 1.3.1. Zákon - podle vzorce K návrhu zákona se mají postupně vyjádřit 4 poslanci: Adámek, Beneš, Coufal a Dupák. Určete počet všech možných pořadí jejich vystoupení. Řešení: Výsledek: P (A) = 4! = 4 • 3 • 2 • 1 = 24. Příklad 1.3.2. Předseda, místopředseda ... - podle vzorce Vedení sportovního klubu 1. FK Zborovice tvoří 3 muži a 2 ženy. Určete kolika způsoby z nich lze vybrat předsedu, místopředsedu, účetního, hospodáře a trenéra? Řešení: 3 muži + 2 ženy = 5 lidí celkem. Výsledek: P(5) = 5! = 5- 4- 3- 2- l = 120. Shrnutí počítání podle vzorce: Použití vzorce může urychlit řešení úlohy, vždy je však nezbytné do úlohy nejprve proniknout. 1.3.2 Příklady k procvičení Příklad 1.3.4. A) Určete, kolika způsoby lze sestavit rozvrh na úterý pro 8. třídu ZŠ Sýpky, v níž se vyučuje 6 předmětů. Každý předmět má právě jednu vyučovací hodinu denně a celkově se vyučuje 6 vyučovacích hodin denně. B) Kolika způsoby lze sestavit takový rozvrh, který má jako třetí vyučovací předmět zeměpis? (Zeměpis je jeden ze šesti předmětů.) Řešení: A) 6-5-4-3-2-l =720 [=P(6)j. B) 5-4-l-3-2-l = 120. Příklad 1.3.5. Určete, kolika způsoby se v pětimístné lavici může posadit: A) pět chlapců; B) pět chlapců, jestliže Kuba a Jirka chtějí sedět vedle sebe; C) pět chlapců, jestliže Kuba a Jirka chtějí sedět vedle sebe a Honza chce sedět na kraji. Řešení: A)_____^ 5 43 2 1 ->5-4-3-2-l = 120. [=^(5)] Kapitola 1. Základní kombinatorické pojmy 20 B) I. Kuba sedí vlevo od Jirky: 3 chlapci + KJ = 4 ^____^ 4 3 2 1 ^ 4 • 3 -2 • 1 = 24. [= P (A)] II. Kuba sedí vpravo od Jirky: 3 chlapci + JK = 4 ^____^ 4 3 2 1 ^ 4 • 3 -2 • 1 = 24. [= P (A)] Celkový počet jejich různých rozsazení je: 24 + 24 = 48. C) I. Nejprve spočítáme počet způsobů, kdy Honza sedí vlevo na kraji a Kuba hned vlevo vedle Jirky: H___->1321->l-3-2-l = 6. Výsledek vynásobíme dvěma, neboť počet způsobů, kdy Kuba a Jirka sedí vedle sebe opačně, je stejný počet: 2 • 6 = 12. II. Honza sedí vpravo na kraji a Kuba hned vlevo vedle Jirky: ___H->3211->3-2-l-l = 6. Výsledek opět vynásobíme dvěma, neboť počet způsobů, kdy Kuba a Jirka sedí vedle sebe opačně, je stejný počet: 2 • 6 = 12. Celkový počet jejich různých rozsazení je: 12 + 12 = 24. Příklad 1.3.6. Žáci 3. třídy chtějí nacvičit divadlo na vánoční besídku. Paní učitelka musí 9 žákům (5 chlapců a 4 děvčata) rozdělit divadelní role: Král, královna, princ, princezna, dvorní dáma, služebná, podkoní, kovář a rytíř. A) Kolika způsoby může tyto role rozdělit? B) Kolika způsoby může tyto role rozdělit tak, aby královna a princezna byla děvčata a král a princ byli chlapci? Ostatní mohou být jakkoli. C) Kolika způsoby může tyto role rozdělit tak, aby ženské role hrála děvčata a mužské role chlapci? Řešení: A) 9-8-7-6-5-4-3-2-1 B) 5-4-4-3-5-4-3-2-1 C) 5-4-4-3-2-1-3-2-1 Příklad 1.3.7. Určete počet všech sudých pěticiferných přirozených čísel vytvořených z cifer 1, 2, 3, 4, 5, nemůže-li se v daném čísle žádná cifra opakovat. [1] Řešení: 4-3-2-1-2 = 48 [=^(4)] = 362880 [=P(9)] =28800 = 2880 [=p(5)-P(4)] Kapitola 1. Základní kombinatorické pojmy 21 Příklad 1.3.8. Určete počet všech šesticiferných přirozených čísel vytvořených z cifer 0, 1,2, 3, 4, 5, v nichž se žádná cifra neopakuje. [1] Řešení: 5-5-4-3-2-1 = 600 Příklad 1.3.9. Kolika způsoby lze postavit do řady 4 Angličany, 2 Francouze a 3 Turky, musí-li osoby téže národnosti stát vedle sebe? [1] Řešení: Nejprve určíme pořadí 3 skupin osob: Angličanů, Francouzů a Turků: 3-2-1. A nakonec rozmístíme osoby v rámci skupiny: 4-3-2-1, 2-1, 3-2-1. Celkem: 3-2-1-4-3-2-1-2-1-3-2-1 = 1728 [= P(3)-P(4) ■ P(2)-P(3)]. Příklad 1.3.10. Určete počet všech pěticiferných přirozených čísel, v jejichž dekadickém zápisu je každá z číslic 0, 1, 3, 4, 7? A) Kolik z těchto čísel je dělitelných šesti? B) Kolik jich je větších než 74300? [2] Řešení: 4 • 4 • 3 • 2 • 1 = 96 A) Ciferný součet čísel je dělitelný 3, proto čísla dělitelná šesti jsou právě ta, která končí cifrou 0 nebo 4. 0 na konci: 4 • 3 • 2 • 1 • 1 = 24 4nakonci:3-3-2-l-l = 18 24+18 = 42 B) Větších než 74300 jsou pouze dvě čísla sestavená z těchto cifer, a to 74301 a 74310. Kapitola 1. Základní kombinatorické pojmy 22 Příklad 1.3.11. Určete, kolikrát lze přemístit slova ve verši od Jána Kollára „Sám svobody kdo hoden, svobodu zná vážiti každou" tak, aby se nepromíchala slova věty hlavní a vedlejší. [2] Řešení: 2-(4-3-2-1-4-3-2-1) =2-(4!)2= 1152 [= 2-P(4)-P(4)] Násobí se dvakrát, protože můžeme ještě prohodit celou větu hlavní s větou vedlejší. Příklad 1.3.12. Kolika způsoby můžeme rozestavit 6 dětí do kruhu? (Kruhy lišící se pouze pootočením, považujeme za shodné.) [3] Řešení: Do řady lze rozestavit 6 dětí 6-5-4-3-2-1 = 720[= P (6)] způsoby. Očíslujeme-li místa v kruhu postupně 1, 2, 3, 4, 5, 6, pak každou řadu můžeme uvážit jako kruh. Vzhledem k tomu, že však nerozlišujeme kruhy lišící se jen pootočením, je hledaný počet 720/6 = 120 (Pro každý kruh existuje 5 dalších kruhů lišících se pouze pootočením). Příklad 1.3.13. Kolik náhrdelníků lze utvořit ze 6 korálků různých barev? [3] Řešení: Mohlo by se zdát, že podle předchozího příkladu je správná odpověď 120. Protože však nerozlíšime dva náhrdelníky, z nichž jeden vznikl převrácením druhého, je hledaný počet 120/2 = 60. Příklad 1.3.14. Kolika způsoby můžeme posadit ke kulatému stolu 5 mužů a 5 žen tak, aby žádné dvě osoby téhož pohlaví neseděly vedle sebe, jestliže A) rozsazení lišící se pouze pootočením rozlišujeme. B) rozsazení lišící se pouze pootočením, považujeme za stejná. [1] Řešení: A) Pevně si určíme jedno místo u stolu, na něj usadíme muže a poté střídavě ostatní osoby: MŽMŽMŽMŽMŽ Obrázek 1.13: Socha svobody, zdroj: [11] Kapitola 1. Základní kombinatorické pojmy 23 Počet všech takových rozsazení kolem stolu je: 5-5-4-4-3-3-2-2-M = 5!-5! [= P(5)-P(5)] Ovšem na našem pevně určeném místě může sedět i žena (tedy muži a ženy si vymění pozice), proto celkový výsledek je: 2-(5!-5!) =28800. B) Podobně jako v předchozích příkladech ještě výsledek z a) vydělíme počtem možných pootočení libovolného rozsazení: 28800/(5 + 5) =2880 . Kapitola 1. Základní kombinatorické pojmy 24 1.4 Kombinace bez opakování Ve variacích (i permutacích) vždy záleželo na pořadí, v jakém jsme vybrané prvky uspořádávali. V kombinacích tomu tak není, na pořadí vybíraných prvků nezáleží. Ovšem stále prvky mezi sebou rozlišujeme a každý se může vyskytovat nejvýše jednou. 1.4.1 Úvodní příklady Příklad 1.4.1. Variace a dvojice Kolik existuje uspořádaných dvojic ze čtyř písmen - A B C D ? (Uspořádaných dvojic, proto záleží na pořadí prvků ve dvojici.) Řešení: dvojice: _ _ 4 • 3 = 12. Všechny dvojice ze čtyř písmen - A B C D jsou: AB AC AD BC BD CD BA CA DA CB DB DC Příklad 1.4.2. Kombinace a dvojice Kolik existuje neuspořádaných dvojic ze čtyř písmen - A B C D ? (Nezáleží na pořadí prvků, proto dvojice AB i B A je stejná kombinace.) (Jinými slovy: Kolik existuje 2-prvkových podmnožin 4-prvkové množiny?) Řešení: Uspořádaných dvojic bylo: 4-3 = 12. AB AC AD BC BD CD BA CA DA CB DB DC Když se pozorně podíváme na výpis, všimneme si, že neuspořádaných dvojic je přesně 2x méně. Každý sloupec tvoří 2 stejné písmena jinak uspořádané = permutace 2 prvků. Počet dvouprvkových permutací je 2! = 2, to určuje i počet řádků. Proto, pokud nezáleží na pořadí, vydělíme výsledek 2! a získáme počet neuspořádaných dvojic. 4-3 12 Výsledek: — = — = 6. Výpis všech neuspořádaných dvojic ze 4 prvků: AB AC AD BC BD CD Příklad 1.4.3. Variace a trojice Kolik existuje uspořádaných trojic ze čtyř písmen Řešení: - A B C D ? Kapitola 1. Základní kombinatorické pojmy 25 trojice:___^ 4 • 3 • 2 = 24 Všechny trojice ze čtyř písmen - A B C D jsou: ABC ABD ACD BCD ACB ADB ADC BDC BAC BAD CAD CBD BCA BDA CDA CDB CAB DAB DAC DBC CBA DBA DCA DCB Příklad 1.4.4. Kombinace a trojice Kolik existuje neuspořádaných trojic ze čtyř písmen - A B C D ? (Jinými slovy: Kolik existuje 3-prvkových podmnožin 4-prvkové množiny?) Řešení: Uspořádaných trojic bylo: 4 • 3 • 2 = 24. ABC ABD ACD BCD ACB ADB ADC BDC BAC BAD CAD CBD BCA BDA CDA CDB CAB DAB DAC DBC CBA DBA DCA DCB Každý sloupec tvoří 3 stejné prvky jinak uspořádané = permutace tří prvků. Počet tříprvkových permutací je 3! = 6, to určuje i počet řádků. Proto, pokud nezáleží na pořadí, vydělíme výsledek 3! a získáme počet neuspořádaných trojic. 4-3-2 24 Výsledek:-= — = 4. 3 3! 6 Výpis všech neuspořádaných trojic ze 4 prvků: ABC ABD ACD BCD Příklad 1.4.5. Zkoušení studentů Řešení: Vybereme trojici žáků: 30 • 29 • 28 Nezáleží na pořadí, proto vydělíme ještě 3!. 30-29-28 Výsledek:---= 4060. V Kralupech navštěvuje druhou třídu základní školy 30 žáků. Paní učitelka by chtěla 3 z nich vyzkoušet z matematiky. Kolika způsoby můžeme vybrat 3 žáky na zkoušení? [6] Obrázek 1.14: (Žáci jsou zkoušeni zároveň, proto nezáleží na jejich pořadí.) Zkoušení, zdroj: [11] Kapitola 1. Základní kombinatorické pojmy 26 Shrnutí: Všimněte si, že pokud jsme tvořili neuspořádané dvojice, vypočítali jsme variace a výsledek vydělili 2!. Pokud jsme chtěli neuspořádané trojice, vypočítali jsme opět variace a výsledek vydělili Jak by tomu bylo u čtveřic? ... Výsledek by se vydělil 4!. Uvědomili jste si na příkladech, proč tomu tak bylo? Definice 6. fc-členná kombinace z n prvků je neuspořádaná fc-tice sestavená z těchto prvků tak, že se v ní každý vyskytuje nejvýše jednou. Jinak řečeno: fc-členná kombinace z n prvků je fc-prvková podmnožina množiny těmito n prvky určená. Z předchozích úvah vyplývá věta: Věta 3. Počet K(k,n) všech k-členných kombinací z n prvků je: 3!. K(k,n) V{k,n) k\ Definice 7. Pro vyjádření K(k,n) užíváme i symbol , nazývá se kombinační číslo a čte se „n nad klí. Věta 4. Pro všechna celá nezáporná čísla n, k, kde k < n, platí: Kombinační číslo - odvození: Podle definice: K(k, n) V(k,n) k\ V{k,n) =n(n-l)(n-2)...(n-k+l) (n-k)\ Dohromady: K(k,n) V(k,n) _ {n-k)\ k\ ~ k\ k\(n-k)\ Kapitola 1. Základní kombinatorické pojmy 27 1.4.2 Řešené příklady Příklad 1.4.6. Knihy Alena má 10 knih, které ještě nepřečetla. Odjíždí na dovolenou a chtěla by si vzít dvě knihy s sebou. Kolik má různých možností, jaké knihy si vybrat? Řešení: Z 10 knih vybíráme 2 tak, že nezáleží na jejich pořadí: 10 Obvykle si s tímto výsledkem vystačíme. Ale zkusme si nyní i rozepsat: '10\ 10! 10! 10-9-8! 10-9 _ 45 2) 2!(10-2)! 2!8! 2!8! 2-1 10-9 10-9 Porovnejme s postupem z úvodu: ^ = = 5 • 9 = 45. Příklad 1.4.7. Šachovnice Určete, kolika způsoby lze na šachovnici (8x8 políček) vybrat: A) 3 políčka? B) 3 políčka neležící ve stejném sloupci? C) 3 políčka neležící ve stejném sloupci ani ve stejné řadě? D) 3 políčka, která nejsou všechna stejné barvy? Řešení: A) Na šachovnici je 64 políček. Z nich vybíráme 3: 64 J Zkusme si i nyní rozepsat: 64\ 64! 64! 64-63-62-61! 64-63-62 3!(64-3)! 3!-61! 3!-61! 3-2-1 64-21-31 =41664. B) Od všech trojic odečteme ty trojice, které leží ve stejném sloupci. Kolik je trojic, které leží ve stejném sloupci? Z 8 políček v jednom sloupci vybíráme 3: 8 3 Sloupců je 8, proto toto číslo musíme odečíst osmkrát. Náš výsledek: Kapitolo 1. Základní kombinatorické pojmy-28 C) Od výsledku v bodě B) ještě odečteme trojice, které leží ve stejné řadě. Kolik jich je? -e Výsledek: ?)-'-ffl-«-G)-®-''-G) [—81 D) Od všech trojic odečteme ty trojice, které jsou bílé barvy, a trojice, které jsou černé barvy. Políček bílé barvy je 32. Políček černé barvy je 32. Výsledek: 64\ /32\ /32\ /64\ „ f32 3 " 3 " 3 = 3 "2- 3 31744] V tomto případě jsme mohli postupovat i jinak. Chceme znát počet trojic, které nejsou stejné barvy. Tedy jsou to trojice, kde je buď 1 políčko černé a 2 bílé, nebo 2 černé a 1 bílé. Těch je: T)•(?)+(?)'(©+W] Příklad 1.4.8. Zeny a muži Určete, kolika způsoby je možno ze sedmi mužů a čtyř žen vybrat šestičlennou skupinu, v níž jsou A) právě dvě ženy? B) aspoň dvě ženy? C) nejvýše dvě ženy? Řešení: A) Vybíráme 2 ženy ze 4 a zároveň 4 muže ze 7, nezáleží na pořadí: 210] B) V tomto případě můžeme vybrat: 2 ženy a 4 muže nebo 3 ženy a 3 muže nebo 4 ženy a 2 muže Výsledek: 371] C) V tomto případě můžeme vybrat: 2 ženy a 4 muže nebo Kapitola 1. Základní kombinatorické pojmy 29 1 ženu a 5 mužů nebo žádnou ženu a 6 mužů Výsledek: :MKMKMM^(KMX) 1.4.3 Příklady k procvičení Příklad 1.4.9. Volejbalový turnaj je rozdělen na 3 skupiny. V každé skupině je 6 týmů. V rámci skupiny hraje každý tým s každým. A) Kolik zápasů se v turnaji odehraje? B) Kolik zápasů se v turnaji odehraje, hrají-li ještě vítězové všech skupin každý s každým o celkové první místo? Řešení: A) 3 • Q [= 45] B) 3-g) + g) [=48] Příklad 1.4.10. Jaký bude celkový počet podání rukou: A) jsou-li v místnosti 3 lidé a každý si podává ruku s každým? B) přijde-li dalších 5 lidí? Původní 3 lidé si už ruce mezi Obrázek 1.15: Podání sebou nepodávají. rukou, zdroj: [11] Řešení: A) Uvědomme si, že se jedná o počet neuspořádaných dvojic, které můžeme sestavit ze 3 lidí, výsledek: '3N [=3] Příklad 1.4.11. A) Kolika způsoby je možno z 18 kamarádů vybrat 9? B) Kolika způsoby je možno z 18 kamarádů vybrat 9, požadujeme-li, že kamarád Pepa nebude mezi vybranými? Kapitola 1. Základní kombinatorické pojmy 30 C) Kolika způsoby je možno z 18 kamarádů vybrat 9, požadujeme-li, že mezi vybranými nebudou zároveň obě kamarádky Katka a Žofka? D) Kolika způsoby je možno z 18 kamarádů vybrat 9 požadujeme-li, aby mezi vybranými byl alespoň jeden z kamarádů Honza nebo Sláva? Řešení: A) ^8) [=48620] B) 18-1 = 17, [=24310] C) Požadujeme, aby ve výběru nebyli obě kamarádky zároveň. Od všech možných způsobů výběru tedy odečteme ty, kde jsou obě kamarádky zároveň. '18N 9 Ke Katce a Žofce vybereme dalších 7 lidí, proto počet možností, kde jsou obě kama-'16N 7 Všech je: řádky zároveň je Celkem: - (^J [=37180] D) Způsoby rozdělíme na tři disjunktní případy: I. mezi vybranými je jen Honza; II. mezi vybranými je jen Sláva; III. mezi vybranými kamarády jsou Honza i Sláva zároveň. I. K Honzovi vybereme dalších 8 kamarádů, ze skupinky, kde není Sláva. II. Analogicky i ke Slávovi. III. K oběma kamarádům vybereme dalších 7 kamarádů. 8) V8 / V7/ V8. Příklad 1.4.12. Petr má sedm knih, o které se zajímá Ivana, Ivana má deset knih, o které se zajímá Petr. Určete, kolika způsoby si Petr může vyměnit dvě své knihy za dvě knihy Ivaniny. Obrázek 1.16: Knihy, [2] zdroj: [11] Řešení: '7\ /10 2 Příklad 1.4.13. 945] Vyjádřete kombinačními čísly, kolika způsoby může m chlapců a n dívek utvořit taneční pár. [2] Řešení: fm + n\ í m\ í n \ 2 )~\2)~\2 Kapitola 1. Základní kombinatorické pojmy 31 Příklad 1.4.14. Je dán čtverec KLMN. Na každé straně čtverce zvolíme 8 vnitřních bodů. A) Určete počet všech trojúhelníků, jejichž vrcholy leží v daných bodech. B) Určete počet všech trojúhelníků, jejichž vrcholy leží v daných bodech a každé dva vrcholy jednoho trojúhelníku leží na různých stranách čtverce. [6] Řešení: A) Od všech trojic z 32 bodů odečteme ty, které netvoří trojúhelník (ty co leží na jedné straně): B) Ze čtyř stran vybere tři a z osmi bodů na každé straně jeden: Příklad 1.4.15. Na běžecké trati běží 8 závodníků. Do finále postupují první tři. Kolik je možností na postupující trojici? [6] Řešení: '8'' ' 56] Příklad 1.4.16. Kolika způsoby lze rozdělit 12 hráčů na dvě šestičlenná volejbalová družstva? Řešení: g2) : 2 [= 462] Příklad 1.4.17. Kolika způsoby lze 4 dívky a 8 chlapců rozdělit na dvě šestičlenná volejbalová družstva tak, aby v každém družstvu byla dvě děvčata a 4 chlapci? Řešení: '4W:):2 [=210] Příklad 1.4.18. Ve skupině je 20 dětí, každé dvě děti mají jiné jméno. Je mezi nimi i Alena a Jana. Kolika způsoby lze vybrat 8 dětí tak, aby mezi vybranými: A) byla Alena, B) nebyla Alena, Kapitola 1. Základní kombinatorické pojmy 32 C) byla Alena a Jana, D) byla alespoň jedna z dívek Alena, Jana, E) byla nejvýše jedna z dívek Alena, Jana, F) nebyla ani Alena, ani Jana? [6] Řešení: Příklad 1.4.19. Kolika způsoby lze 20 dětí rozdělit do tří skupin tak, aby v první skupině bylo 10 dětí, ve druhé skupině bylo 6 dětí a ve třetí zbytek? [6] Příklad 1.4.20. V sérii 12 výrobků jsou právě 3 vadné. Kolika způsoby z nich lze vybrat: A) 6 libovolných výrobků, B) 6 výrobků bezvadných, C) 6 výrobků, z nichž právě 1 je vadný, D) 6 výrobků, z nichž právě 2 jsou vadné, E) 6 výrobků, z nichž právě 3 jsou vadné? [5] Řešení: [= 38798760] Řešení: [=84] [= 924] 378] 378] Kapitola 1. Základní kombinatorické pojmy 33 [= 84] Příklad 1.4.21. Kolika způsoby je možné vybrat z přirozených čísel menších nebo rovných 30 tři různá čísla tak, aby jejich součet byl roven sudému číslu? [1] Řešení: [= 2030] Kapitola 1. Základní kombinatorické pojmy 34 1.5 Variace s opakováním Vzpomínáte si na počítání variací bez opakování? Zjišťovali jsme počet výběrů prvků, kde záleželo na pořadí a kde se každý prvek vyskytoval nejvýše jednou. Jediný rozdíl u variací s opakováním je ten, že se prvky ve výběru mohou opakovat. Ukážeme si rozdíl na příkladech. 1.5.1 Řešené příklady Příklad 1.5.1. Vlajky Vlajka má být složena ze tří svislých pruhů, k dispozici máme 5 barev - bílou, červenou, hnědou, zelenou a žlutou. Každou barvu můžeme použít vícekrát. (Ovšem jeden pruh může být obarven pouze jednou barvou.) A) Určete počet vlajek, které lze z těchto barev sestavit. B) Kolik takových vlajek má žlutý pruh? C) Kolik vlajek má žlutý pruh uprostřed? D) Kolik vlajek nemá červený pruh? E) Kolik vlajek nemá červený pruh uprostřed? Řešení: A) Doplňujeme barvy na tři části vlajky, vybíráme tedy 3 barvy z pěti a přitom barvy můžeme použít vícekrát: 1.2.3.->___ Na první místo máme 5 možností: 5 __ Na druhé místo máme opět 5 možností, barvy se mohou opakovat: 55_ Na třetí místo máme opět 5 možností: 555 Výsledek: 5-5-5 = 125. B) Situaci si rozdělíme na tři případy: Buď žlutý pruh bude vlevo nebo uprostřed nebo vpravo na vlajce: Ž__ _Ž_ __Ž Umístění žluté barvy tímto máme určené. Na toto místo máme pouze jednu možnost výběru barvy = žlutou: 1 __ _ 1 _ __1 Na zbývající dvě místa máme k dispozici pět barev: 1 5 5 5 1 5 5 5 1 Kapitola 1. Základní kombinatorické pojmy 35 Jednotlivé možnosti: 1-5-5 = 25, 5-1-5 = 25, 5-5-1 =25. Jelikož se jedná o 3 různé případy, z nichž k obarvení každého případu máme 25 možností, celkem budeme mít podle pravidla součtu: 25 + 25 + 25 = 75 různých vlajek. C) Žlutý pruh uprostřed a na zbývající pruhy máme k dispozici 5 barev: 5-1-5 = 25. D) Nemá červený pruh, počet barev na vlajku je tedy 4: 4- 4-4 = 64. E) Dá se vypočítat dvěma způsoby: I. Můžeme od počtu všech vlajek odečíst ty, které mají prostřední barvu červenou. Tato čísla máme už vypočítané: Počet všech vlajek 5 • 5 • 5 = 125. Počet vlajek s červenou uprostřed 5 • 1 • 5 = 25. Vlajky bez prostředního pruhu červeného: 125 — 25 = 100. II. Máme obarvit 3 pruhy na vlajce: Začneme od prostředního pruhu. Na něj máme pouze 4 barvy - červenou nechceme: _ 4 _ Na zbývající dva pruhy můžeme použít 5 pět barev: 5 4 5 Celkem: 5- 4-5 = 100. Příklad 1.5.2. SPZ Bývalé české SPZ tvořily 3 písmena a 4 čísla, např. KME0782. Určete, kolik různých SPZ dříve mohlo být? Na SPZ se používalo 28 písmen a číslice 0, 1, 2, ..., 9. Řešení: Vybíráme prvky na 7 různých míst: ^__■ ^ Zbývající místa tvoří číslice 0, 1, 2,9, těch je 10: První tři místa tvoří písmena: 28 28 28 ____ 28 28 28 10 10 10 10 Celkem: 28 • 28 • 28 • 10 • 10 • 10 • 10 = 219520000. Obrázek 1.17: Auto, zdroj: [11] 43 Kapitola 1. Základní kombinatorické pojmy 36 Příklad 1.5.3. Čísla A) Určete počet všech nejvýše čtyřciferných přirozených čísel sestavených z číslic 1, 2,3,7, 8,9? B) Kolik z nich je menších než 6000? C) Určete počet všech nejvýše čtyřciferných přirozených čísel sestavených z číslic 0, 1,2,3,7, 8, 9? Řešení: A) Situaci si rozdělíme na případy: I. Výběr čtyřciferných čísel. II. Výběr tříciferných čísel. III. Výběr dvouciferných čísel. IV. Výběr jednociferných čísel. I. Máme čtyři cifry:____ Můžeme na ně umístit číslice: 1, 2, 3, 7, 8, 9. Celkem 6 číslic. 6 666 Celkově: 6 • 6 • 6 • 6 = 1296. II. Pro tříciferná čísla obdobně: 6 • 6 • 6 = 216. III. Pro dvouciferná čísla: 6-6 = 36. IV. Jednociferná čísla: 6. Vypočítali jsme, kolik máme možností pro výběr 4 různých čísel (nejprve čtyřciferného čísla, poté tříciferného, dvouciferného a jednociferného), proto výsledek je podle pravidla součtu: 1296 + 216 + 36 + 6= 1554. B) Postup řešení je stejný jako v A). Jediný rozdíl bude pro výpočet čtyřciferných čísel. Na prvním místě může být pouze jedna z číslic: 1, 2, 3. Celkem 3 číslice. (Proč? Čísla mají být menší než 6000.) 3-6-6-6 = 648 Počet všech nejvýše čtyřciferných přirozených čísel menších než 6000 je: 648 + 216 + 36 + 6 = 906. C) Opět si situaci rozdělíme na případy: I. Výběr čtyřciferných čísel. II. Výběr tříciferných čísel. Kapitola 1. Základní kombinatorické pojmy III. Výběr dvouciferných čísel. IV. Výběr jednociferných čísel. 37 I. Na čtyři cifry:____ můžeme umístit čtyři číslice z následujících 7 číslic: 0, 1, 2, 3, 7, 8, 9: 6777 Celkově: 6 • 7 • 7 • 7 = 2058. II. Pro tříciferná čísla analogicky: 6 • 7 • 7 = 294. III. Pro dvouciferná čísla: 6 • 7 = 42. IV. Jednociferná (přirozená) čísla: 6. Vypočítali jsme, kolik máme možností pro výběr 4 různých čísel (nejprve čtyřciferného čísla, poté tříciferného, dvouciferného a jednociferného), proto opět podle pravidla součtu je výsledek: 2058 + 294 + 42 + 6 = 2400. Definice 8. fc-členná variace s opakováním z n prvků je uspořádaná fc-tice sestavená z těchto prvků tak, že se v ní každý vyskytuje nejvýše fc-krát. Z předchozích úvah vyplývá následující věta: Věta 5. Počet V'(k,ri) všech k-členných variací z n prvků je: V'{k,ri) = nk. Vypočítáme si některé již řešené příklady s využitím vzorce. Příklad 1.5.1. Vlajky - podle vzorce Vlajka má být složena ze tří svislých pruhů, k dispozici máme 5 barev - bílou, červenou, hnědou, zelenou a žlutou. Každou barvu můžeme použít vícekrát. Určete počet vlajek, které lze z těchto barev sestavit. Řešení: Počet prvků, z nichž vybíráme: n = 5. Kolika člennou variaci vybíráme: k = 3. V (3,5) = 53 = 125. Příklad 1.5.2. SPZ - podle vzorce Bývalé české SPZ tvořily 3 písmena a 4 čísla, např. KME0782. Určete kolik různých SPZ dříve mohlo být? Na SPZ se používalo 28 písmen a číslice 0, 1, 2, 9. Kapitola 1. Základní kombinatorické pojmy 38 Řešení: SPZ si rozdělíme na dvě části, část písmen a část číslic. Písmena: Počet prvků, z nichž vybíráme: n = 28. Kolika člennou variaci vybíráme: k = 3. V (3,28) =283 =21952. Číslice: Počet prvků, z nichž vybíráme: n = 10. Kolika člennou variaci vybíráme: k = 4. V'(4,10) = 104 = 10000. Celkem: 283 • 104 = 219520000. Shrnutí počítaní podle vzorce: Použití vzorce může urychlit řešení úlohy, vždy je však nezbytné do úlohy nejprve proniknout. 1.5.2 Příklady k procvičení Příklad 1.5.4. Kolik značek Morseovy abecedy lze utvořit sestavením teček a čárek do skupin o jednom až čtyřech znacích? [2] Řešení: Počet jednoznakových prvků Morseovy abecedy: 2 [= V'(l,2)] Počet dvouznakových prvků Morseovy abecedy: 2 • 2 = 22 = 4 [= V'(2,2)] Počet tříznakových prvků Morseovy abecedy: 2 • 2 • 2 = 23 = 8 [= V'(3,2)] Počet čtyřznakových prvků Morseovy abecedy: 2 • 2 • 2 • 2 = 24 = 16 [= V'(4,2)] Celkem: 2 + 4 + 8 + 16 = 30. Příklad 1.5.5. Žofka zapomněla své telefonní číslo. Ví jen, že mělo předčíslí 773 a poté jej tvořilo 6 číslic takových, že: první tři číslice byly sudé nebo nula, další dvě číslice byly liché a poslední si nepamatuje vůbec. Kolik takových různých telefonních čísel lze sestavit? Řešení: Označme: S - sudá číslice nebo nula, L - lichá číslice, C - libovolná číslice SSSLLČ 5-5-5-5-5-10 = 31250. Kapitola 1. Základní kombinatorické pojmy 39 Příklad 1.5.6. Kolik je všech čtyřciferných čísel dělitelných čtyřmi, v nichž se vyskytují pouze cifry 1,2,3,4,5. Řešení: Máme k dispozici 5 číslic. Aby číslo bylo dělitelné 4, musí poslední dvojčíslí být dělitelné 4. V tomto případě tedy poslední dvě cifry mohou být: 12, 24, 32, 44, 52 = 5 možností Čtyřciferné číslo:____ Poslední dvě cifry mají dohromady 5 možností: __(__) —?■ _ _ 5 Doplníme počet možností na ostatní cifry: 5 5 5 Výsledek: 5-5-5 = 125. Příklad 1.5.7. Určete počet všech přirozených čísel menších než milión, která lze zapsat dekadicky pouze použitím číslic 5,8. Řešení: Rozdělíme si příklad na situace šesticiferných čísel, pěticiferných, čtyřciferných, tříci-ferných, dvouciferných a jednociferných. A výsledky z jednotlivých situací podle pravidla součtu sečteme. 26 + 25 + 24 + 23+22 + 21 = 126 [= V (6,2) + V'(5,2) + V(4,2) +V'(3,2) +V'(2,2) + V'(l,2)] Příklad 1.5.8. Jméno a příjmení každého obyvatele městečka s 1500 obyvateli může začínat jedním ze 32 písmen. Dokažte, že aspoň dva obyvatelé městečka mají stejné iniciály. Řešení: Všech možných variací iniciál je 32 • 32 = 1024[= V7(2,32)], což je méně než počet obyvatel. Podle Dirichletova principu1 musí v městečku existovat nejméně 2 lidé se stejnými iniciály. Příklad 1.5.9. Kufřík má heslový zámek, který se otevře, když na každém z pěti kotoučů nastavíme správnou číslici; těchto číslic je na každém kotouči devět. Určete největší možný počet ^irichletův princip je jedním ze základních principů používaných v kombinatorice. Jde o tvrzení: Umístíme-li m předmětů do n přihrádek, kde ra > n a ra, n e N, pak bude existovat alespoň jedna přihrádka, ve které budou alespoň dva předměty. Kapitola 1. Základní kombinatorické pojmy 40 pokusů, které je nutno provést, chceme-li kufřík otevřít, jestliže jsme zapomněli heslo. [2] Řešení: 9-9-9-9-9 = 59049 [=V'(5,9)] Příklad 1.5.10. Na panelu je k žárovek, z nichž každá může svítit zeleně, žlutě nebo červeně. Určete, kolik různých stavů může panel signalizovat. [2] Řešení: Ý [=V'(*,3)] Příklad 1.5.11. Určete počet všech šesticiferných přirozených čísel, jejichž ciferný součet je číslo sudé. Řešení: Na první cifru nemůže zvolit číslici 0, další čtyři cifry volíme libovolně a poslední cifru pak doplníme tak, aby ciferný součet byl sudé číslo: 9-10-10-10-10-5 = 450000 Příklad 1.5.12. Kolik různých vrhů lze provést A) dvěma, B) třemi šestibokými kostkami? (Stěny jsou označeny jednou, dvěma, ... až šesti tečkami.) Řešení: A) 6-6 = 36 [=V'(2,6)] B) 6-6-6 = 216 [=V'(3,6)] Příklad 1.5.13. A) Určete počet všech čtyřciferných přirozených čísel vytvořených z cifer 1, 2, 3, 4, 5, 6, která jsou dělitelná čtyřmi. B) Určete počet všech čtyřciferných přirozených čísel vytvořených z cifer 0, 1, 2, 3, 4, 5, která jsou dělitelná čtyřmi. [1] Řešení: A) Posledních dvojčíslí sestavených z uvedených číslic dělitelných 4 je 9, proto: 6-6-9 = 324. B) Posledních dvojčíslí sestavených z uvedených číslic dělitelných 4 je 9, proto: 5-6-9 = 270. Kapitola 1. Základní kombinatorické pojmy 41 1.6 Permutace s opakováním Při počítání s permutacemi bez opakování jsme počítali, kolik různých uspořádání můžeme utvořit ze všech předem daných prvků, kde se každý vyskytoval právě jednou. I nyní nás bude zajímat počet různých uspořádání dané délky ze všech předem daných prvků s tím, že některé prvky mezi sebou nerozlišujeme, jinak řečeno mohou se opakovat. Na pořadí prvků stále záleží. 1.6.1 Řešené příklady Příklad 1.6.1. Vagóny Strojvedoucí chce za lokomotivu připojit 3 vagóny, 1 je nákladní a 2 jsou osobní. Kolik různých možností má strojvedoucí, jak vagóny zapojit? (Osobní vagóny mezi sebou nerozlišujeme.) Obrázek 1.18: Vlak s 1 nákladním a 2 osobními vagóny, zdroj: [11] Řešení: Uspořádáme všechny vagóny: 3-2-1 = 3! Tím, že osobní vagóny mezi sebou nerozlišujeme, jsme započítali některá uspořádání vagónů víckrát. Nyní dostáváme tato uspořádání (N - nákladní vagón, Ol, 02 - osobní vagóny - sice je nerozlišujeme, ale pro vysvětlení počítání šije označíme): N 01 02 01 N 02 01 02 N N 02 01 02 N 01 02 01 N Jak to vyřešíme? Všimněte si, že sloupce tvoří pevně umístěný nákladní vagón a k němu různá umístění osobních vagónů. Počet různých umístění osobních vagónů je 2!. Proto pokud je nerozlišujeme, musíme výsledek vydělit počtem permutací osobních vagónů. Příklad 1.6.2. Vločky Petra má čtyři papírové sněhové vločky. Tři jsou bílé barvy a jedna je modrá. Kolik má možností uspořádání vloček, chce-li je zavěsit na čtyři okna tak, že na každém okně je právě jedna vločka? Řešení: Celkem jsou čtyři vločky, počet jejich možných uspořádání je 4!. Kapitola 1. Základní kombinatorické pojmy 42 Obrázek 1.19: Příklad uspořádání vloček, zdroj: [11] Jelikož bílé vločky mezi sebou nerozlišujeme, dělíme ještě počtem permutací třech bílých vloček a dostáváme výsledek: Íl=4 3! Proč dělíme počtem permutací třech vloček? Pokud si vypíšeme všechna uspořádání vloček s rozlišením bílých vloček, dostáváme: (Bi, B2, B3 - bílé vločky, M - modré vločky) MB1B2B3 B1MB2B3 B1B2MB3 B1B2B3M MB1B3B2 B1MB3B2 B1B3MB2 B1B3B2M MB2B1B3 B2MB1B3 B2B1MB3 B2B1B3M MB2B3B1 B2MB3B1 B2B3MB1 B2B3B1M MB3B1B2 B3MB1B2 B3B1MB2 B3B1B2M MB3B2B1 B3MB2B1 B3B2MB1 B3B2B1M V tabulce můžeme vidět, že sloupce tvoří právě ty čtveřice, které obsahují stejné postavení modré vločky vůči bílým. Tedy v rámci sloupce je umístění modré pevně dáno a bílé jsou propermutovány mezi sebou. Pokud tedy bílé vločky mezi sebou nerozlišujeme, musíme vydělit počtem řádků a těch je právě 3!. Příklad 1.6.3. Pěticiferná čísla Určete počet všech pěticiferných přirozených čísel sestavených z číslic 4 a 6, má-li číslice 6 být obsažena právě třikrát. Řešení: Jestliže číslice 6 má být obsažena třikrát, číslice 4 bude obsažena dvakrát. Rozmísťujeme 2 + 3 (= 5) číslic: 5-4-3-2-l = 5!. Číslice 6 mezi sebou nerozlišujeme, taktéž i číslice 4, proto ještě vydělíme počtem permutací jednotlivých číslic: Příklad 1.6.4. Abrakadabra A) Určete počet způsobů, jimiž lze přemístit písmena slova ABRAKADABRA. B) Určete, v kolika z nich žádná dvojice sousedních písmen není tvořena dvěma písmeny A. [2] Kapitola 1. Základní kombinatorické pojmy 43 Řešení: A) Jde o permutace s opakováním z pěti písmen A, B, D, K, R, v nichž je A pětkrát, B dvakrát, D jednou, K jednou a R dvakrát. Počet všech permutací tedy je: 11! 11! 5!-2!-2! -1! • 1! 480 B) Nemají-li být dvě písmena A vedle sebe, musí být každé z pěti písmen A na jednom ze sedmi míst vyznačených podtržítkem: _B _R_K_D_B _R_ Pět z těchto míst lze vybrat í ) způsoby a zbývající písmena lze přemístit v5y r J J J r r 2!-2! Počet všech „slov", v nichž žádná dvě písmena A spolu nesousedí, je ^ 6! 3780. 5/ 2!-2! Definice 9. Permutace s opakováním z n prvků je uspořádaná w-tice sestavená z těchto prvků tak, že se v ní každý vyskytuje aspoň jednou. Z předchozích úvah vyplývá následující věta: Veta 6. Počet P' (ki,Ji2,... ,kn) všech permutací z n prvků je: (kl+k2 + ...+kn)\ P'(h,k2,...,kl ' n> h\-k2\-...-kn\ Ukážeme si postup podle vzorce: Příklad 1.6.1. Vagóny - podle vzorce Strojvedoucí chce za lokomotivu připojit 3 vagóny, 1 je nákladní a 2 jsou osobní. Kolik různých možností má strojvedoucí, jak vagóny zapojit? (Osobní vagóny mezi sebou nerozlišujeme.) Řešení: K,.,2,-íl±2!-3 Příklad 1.6.4. Abrakadabra - podle vzorce Určete počet způsobů, jimiž lze přemístit písmena slova ABRAKADABRA. Řešení: P>(^ 1 9 9 M (1 + 1+2 + 2 + 5)! 11! P (1' X'2'2'5) = lM!.2!.2!o! = 2^5! = 83160 Kapitola 1. Základní kombinatorické pojmy 44 1.6.2 Příklady k procvičení Příklad 1.6.5. Určete počet způsobů, jimiž lze umístit všechny bílé šachové figurky (král, dáma, 2 věže, 2 jezdci, 2 střelci, 8 pěšáků) A) na dvě pevně zvolené řady šachovnice 8x8; B) na některé dvě řady šachovnice 8x8. Řešení: A) (1 + 1,+ 2 + 2+Q2 + 8)! = T~ť~~T~q" = 64864800 = [p'(l, 1,2,2,2,8)] 2!-2!-2!-8! 2-2-2-8I B) 8\ 16! 1816214400 ,2/ 2!-2!-2!-8! Příklad 1.6.6. Jistě jste poznali, že v anagramech AABIIKKMNOORT resp. MINIKABAROTOK je zašifrováno slovo KOMBINATORIKA. Určete počet všech anagramů, jež lze ze slova KOMBINATORIKA utvořit. [2] Řešení: Celkem je ve slově 13 písmen. Počet jednotlivých písmen je: A - 2, B - 1,1 - 2, K - 2, M - 1, N - 1, O - 2, R - 1, T - 1. Jelikož jednotlivá písmena mezi sebou nerozlišujeme, dostáváme výsledek: 131 389188800 = [^(1,1,1,1,1,2,2,2,2)] 2!-2!-2!-2! Příklad 1.6.7. Určete počet všech pěticiferných přirozených čísel, jež lze sestavit z číslic 5 a 7, má-li v každém z nich být číslice 5 A) právě třikrát; B) nejvýše třikrát; C) aspoň třikrát. [2] Řešení: A) B) 51 10 =[^(2,3)] 3!-2! 51 +^T + T^7T + 7#T7=26 =[JP/(3,2)+P/(2,3)+P/(l,4)+P/(0,5)] 3!-2! 2!-3! l!-4! 0!-5! Kapitola 1. Základní kombinatorické pojmy 45 C) éy.év.ůř. 16 =[p/(3'2)+p/(4>1}+p/(5'0)] Příklad 1.6.8. Určete počet všech čtyřciferných přirozených čísel dělitelných devíti, v jejichž dekadickém zápisu nejsou jiné číslice než 0, 1, 5, 7. [2] Řešení: Ciferný součet uvažovaných čísel je nejvýše 4 • 7 = 28. Podmínka dělitelnosti čísla devíti je ekvivalentní tomu, že ciferný součet je dělitelný devíti. Do úvahy tak připadají pouze ciferné součty 27, 18, 9. Ciferný součet 27 z uvažovaných číslic dostat nelze. Ciferný součet 18 lze dostat pouze použitím číslic 7, 7, 2, 2 anebo 7, 5, 5, 1. Ciferný součet 9 utvoří pouze číslice 7, 2, 0, 0 nebo 7, 1, 1,0 nebo 5, 2, 2, 0 nebo 5, 2, 1,1. Počet čtyřciferných čísel odpovídajících jednotlivým skupinám cifer: 4! 7,7,2,2 7,5,5,1 ... — = 12 7,2,0,0 ... — -3! = 6 2!-2! 4! 2! 4! 2! 4! 3! 7,1,1,0 ... ^-^ = 9 2! 2! 4! 3! 5,2,2,0 ... —- — = 9 5,2,1,1 ... — = 12 2! 2! 4! 2! V některých případech jsme odečítali situace, kdy na první cifře je číslice 0. Podle pravidla součtu je počet všech čtyřciferných čísel odpovídajících zadání roven: 6+12 + 6 + 9 + 9+12 = 54. Příklad 1.6.9. Určete počet všech anagramů, které lze získat z písmen slova ROKOKO, nesmějí-li v takovém anagramu stát všechna tři písmena O vedle sebe. [1] Řešení: Požadovaný výsledek získáme, pokud od počtu všech anagramů odečteme ty, kde se vyskytují tři písmena O vedle sebe (tři O vedle sebe budeme počítat jako jeden prvek). 6! 4! 60- 12 = 48 3!-2!■1! 2!-1!-1! Kapitola 1. Základní kombinatorické pojmy 46 Příklad 1.6.10. Určete počet všech anagramů, které lze vytvořit z písmen slova PARABOLA, jestliže požadujeme, aby se ve vytvořeném anagramu pravidelně střídaly samohlásky a souhlásky. [1] Řešení: Každý vyhovující anagram začíná buď samohláskou, nebo souhláskou (místa pro další samohlásky, resp. souhlásky jsou pak jednoznačně určena). Na zadaných místech lze pak 4! souhlásky umístit 4! způsoby, pro zápis samohlásek je pak — = [P'(l, 3)] možností. ' 4! Podle pravidla součinu je celkový počet anagramů 2 • (4! • —) = 192. Příklad 1.6.11. Pro osm studentů je připraveno v koleji ubytování ve 3 pokojích, z nichž 2 jsou třílůžkové, jeden dvoulůžkový. Kolik je způsobů rozdělení studentů do jednotlivých pokojů? [1] Řešení: _J1_ = 560 =[^(2,3,3)] Příklad 1.6.12. Rychlíková souprava bude tvořena ze dvou zavazadlových vozů, jednoho jídelního vozu, čtyřech vozů lůžkových a tří lehátkových. Kolik různých typů souprav lze sestavit? [1] Řešení: 10' -:— = 12600 =[^(1,2,3,4)1 2!-3!-4! Příklad 1.6.13. Když Christian Huygens objevil Saturnův prstenec, zašifroval svůj objev, jak bylo v té době časté, do následujícího anagramu: aaaaaaa ccccc d eeeee g h iiiiiii 1111 mm nnnnnnnnn oooo pp q rr s ttttt uuuuu Náležitým uspořádáním písmen dostaneme zprávu Annulo cingitur tenui, piano, nusquam cohaerente, ad eclipticam inclinato. Česky: Obklopen prstencem tenkým, plochým, nikde nezaveseným, nakloněným k ekliptice. Určete, za jak dlouho by počítač, který by vypsal milión permutací Huygensova anagramu za sekundu, vypsal všechny permutace. [3] Kapitola 1. Základní kombinatorické pojmy 47 Řešení: Všech permutací je: 62! _ 62! 9!-7!-7!-5!-5!-5!-5!-4!-4!-2!-2!-2! ~ 9! • (7!)2 • (5!)4 • (4!)2 • (2!)3 = [^(2,2,2,4,4,5,5,5,5,7,7,9)] Toto číslo je přibližně rovno číslu 3,573 • 1060. Počítač by potřeboval více než 1054 sekund. O velikosti tohoto čísla si uděláme představu, když si uvědomíme, že trvání našeho vesmíru (tj. přibližně 15 miliard roků) je méně než 1017 sekund. [3] Obrázek 1.20: Saturn, zdroj: [11] Příklad 1.6.14. Poznáte zprávu Gaia Iulia Caesara zaslanou do Říma po vítězství nad pontským králem Farnakem, která se skrývá v anagramu CDEIIIIINVVV? Kolika způsoby lze v ní přemístit písmena? [2] Řešení: Veni, vidi, vici (Přišel jsem, viděl jsem, zvítězil jsem). = 665280 = [P'(1,1,1,1,3,5)] Příklad 1.6.15. Určete počet všech deseticiferných přirozených čísel, jejichž ciferný součet je roven třem. Kolik z nich je sudých? [2] Řešení: Aby ciferný součet byl roven třem, můžeme použít následující skupiny číslic: I) jedna 3 a devět 0 1 možnost. II) jedna 2, jedna 1 a osm 0 Na první cifru můžeme zvolit jednu ze dvou možností (1 nebo 2) a k oběma těmto možnostem existuje pro umístění další nenulové číslice 9 různých možností. Celkem: 2 • 9 = 18 možností. III) tři 1 a sedm 0 První cifra je jednoznačně určená číslicí 1, poté pro rozmístění zbylých dvou 1 a sedmi 0 9! je možností-= 36. J 2!-7! Celkem podle pravidla součtu: 1 + 18 + 36 = 55 Aby číslo bylo sudé, na poslední cifře nesmí být lichá číslice, celkem takových čísel je:l + (9 + 8) + J^ = 46 Kapitola 1. Základní kombinatorické pojmy_48 Příklad 1.6.16. Určete, kolik čtyřciferných čísel lze sestavit z cifer čísla 238 832. [2] Řešení: 3-^ + 3-^ = 54 =[3-P'(2,2) + 3-P/(l,l,2)] Kapitola 1. Základní kombinatorické pojmy 49 1.7 Kombinace s opakováním V kombinacích s opakováním nás budou zajímat skupiny prvků, kde nezáleží na uspořádání vybraných prvků a kde se prvky mohou opakovat. Podívejme se hned na první příklad. 1.7.1 Úvodní příklady Příklad 1.7.1. Tři kuličky tří barev V sáčku je mnoho červených, modrých a žlutých kuliček. Kolik různých možností máme, chceme-li si vybrat 3 z nich? (Na pořadí vybraných kuliček nezáleží a kuličky téže barvy mezi sebou nerozlišujeme.) Řešení: Pokud si znázorníme všechny možnosti, zjistíme, že jich je 10: w J © J J > J Obrázek 1.21: Všechny kombinace kuliček, zdroj: autor Jak se početně dopočítáme k tomuto výsledku? Postup i pro další příklady si zkusíme odůvodnit. Každou kombinaci kuliček si zašifrujeme pomocí teček a čárek následovně: Mysleme si, že máme tři hromádky - na jedné jsou červené kuličky, na druhé jsou modré a na poslední jsou žluté kuličky. 4» «S» & Obrázek 1.22: Tři hromádky kuliček, zdroj: autor Pro každou kombinaci zakreslíme pod příslušnou hromádku tolik teček, kolikrát se v dané kombinaci tento prvek vyskytuje. A pro rozlišení mezi sousedními hromádkami použijeme svislou čáru (mezi první a druhou přihrádkou a mezi druhou a třetí). Není-li kulička některé barvy v dané kombinaci, nebude pod touto hromádkou žádná tečka. Dostaneme takové přiřazení: Kapitola 1. Základní kombinatorické pojmy 50 ►J —> •• • #WW —y | • | OvJvJ | | Všimněte si, že takové přiřazení je jednoznačné - každé tří prvkové kombinaci můžeme jednoznačně přiřadit pětici skládající se ze 3 teček a 2 svislých čar a obráceně. Uvědomme si, že ačkoli nám u výběru kuliček nezáleželo na pořadí, u uspořádání teček a čar už jejich pořadí důležité je. Od kombinací s opakováním jsme jednoznačně přešli k permutacím s opakováním, jejichž počet už umíme vypočítat, dostáváme výsledek: (3 + 2)! = _5!_ = 3!-2! 3!2! Poznámka: Na počet pětic složených ze tří teček a dvou čar se také můžeme dívat jako na výběr dvou míst z pěti, na kterých budou svislé čáry. Tento počet je tedy Příklad 1.7.2. Čtyři kuličky tří barev V sáčku je mnoho červených, modrých a žlutých kuliček. Kolik různých možností máme, chceme-li si vybrat 4 z nich? Řešení: Stále máme tři hromádky - jednu červených, druhou modrých a poslední žlutých kuliček. «3» tíuJ Obrázek 1.23: Tři hromádky kuliček, zdroj: autor Počet kuliček příslušné barvy opět určíme tečkami a pro rozlišení jejich barev opět použijeme 2 svislé čáry. Proč svislé čáry jsou právě dvě? Je to dáno počtem hromádek (různých prvků), pro rozdělení 3 různobarevných hromádek potřebujeme svislé čáry v počtu o jednu méně. Příklad jednoho přiřazení: •www —> • | | • Rozmísťujeme 4 tečky a 2 svislé čáry, kde záleží na jejich pořadí, dostáváme výsledek: (4 + 2)! 6! 4!-2! 4!2! Kapitola 1. Základní kombinatorické pojmy 51 Příklad 1.7.3. Tři kuličky čtyř barev V sáčku je mnoho červených, modrých, žlutých a zelených kuliček. Kolik různých možností máme, chceme-li si vybrat 3 z nich? Řešení: Nyní dostáváme čtyři hromádky - na jedné jsou červené kuličky, na druhé jsou modré, na třetí žluté a na poslední zelené kuličky. 4» «£» ^ 4fc Obrázek 1.24: Čtyři hromádky kuliček, zdroj: autor Zašifrováváme je stejným způsobem jako v předešlých dvou příkladech. Pomocí teček a svislých čar. Kolik bude nyní teček a čar? Vybíráme 3 kuličky, proto budou 3 tečky. Máme 4 různé barvy, proto budou 3 svislé čáry. Příklad jednoho přiřazení: 9yJ | . | . |. Rozmísťujeme 3 tečky a 3 svislé čáry, kde záleží na jejich pořadí, dostáváme výsledek: (3 + 3)! 6! 3!-3! 3!3! 20 Shrnutí: V úvodních příkladech jsme počítali počet všech kombinací s opakováním pomocí počtu všech permutací s opakováním. Pokud jsme měli vypočítat počet všech neuspořádaných fc-tic z prvků, kterých bylo n druhů, využili jsme k tomu počet všech permutací z [k+ (n — 1)] prvků (počet kuliček, které jsme vybírali + počet svislých čar, jenž rozdělovaly hromádky). Za chvíli si ukážeme, že tento postup opravdu vyhovuje i definici níže. Je důležité si uvědomit, že jsme doposud měli k dispozici vždy dostatečný počet prvků (kuliček) od každého druhu (barvy). Tzn. při počítání počtu všech neuspořádaných trojic, jsme měli k dispozici 3 kuličky od každé barvy. Pokud bychom měli jen 2 kuličky od některé barvy, musíme to při výpočtu zohlednit. V řešených příkladech pod definicí některé takové příklady spočítáme. Definice 10. fc-členná kombinace s opakováním z n prvků je neuspořádaná k-tice sestavená z těchto prvků tak, že se v ní každý vyskytuje nejvýše fc-krát. Z předchozích úvah vyplývá následující věta: Věta 7. Počet K'(k,n) všech k-členných kombinací s opakováním z n prvků je: Kapitola 1. Základní kombinatorické pojmy 52 Odvození: 'n + k-l\ [k+(n-l)]\ k\(n-l)\ K'(k,n)=P'(k,n-l) nebo-li ^ + ^ ^ Rozepsáním podle definic permutací s opakováním, kombinací s opakováním a kombinačního čísla dostáváme: K'(k,n) n + k-l\ (n + k-l)\ (n + k-l)\ k J k\[(n + k-l)-k]\ k\{n-\)\ ! V ' ; k\{n-\)\ k\{n-\)\ n + k- IV Dohromady: K'(k,n) = —-=P'(k,n-V. k\(n — 1)! 1.7.2 Řešené příklady Příklad 1.7.4. Kvádr Určete počet kvádrů, jejichž velikosti hran jsou přirozená čísla, která jsou nejvýše rovná deseti. Kolik je v tomto počtu krychlí? [2] Řešení: Vybíráme 3 číslice z deseti, číslice se mohou opakovat a nezáležím nám na jejich pořadí. (3 tečky a 9 svislých čar) 3+in-c?) Krychle má všechny délky hran stejně dlouhé, my máme k dispozici 10 různých číslic, proto je 10 krychlí. Příklad 1.7.5. Koláče Obrázek 1.25: Tři druhy koláčů, zdroj: [11] Matějova maminka upekla 3 druhy koláčů - makové, ořechové, tvarohové. Od každého 5 kusů. Určete, kolika způsoby si Matěj může vybrat A) 4 koláče; B) 6 koláčů. Kapitola 1. Základní kombinatorické pojmy 53 Řešení: A) Vybíráme 4 koláče ze 3 různých druhů: 4 / W 4!2! B) V tomto případě si Matěj nemůžeme vybrat 6 koláčů stejného druhu. Přesto vypočítáme počet všech kombinací, jak si může vybrat 6 koláčů, a od tohoto počtu odečteme počet případů, které nelze sestavit. Nemůže si vybrat kombinaci šesti makových, šesti ořechových a šesti tvarohových koláčů, tedy 3 případy. 6+P-1))-3 = 28-3 = 25 Příklad 1.7.6. Pohlednice V novinovém stánku je ke koupi deset druhů pohlednic, přičemž každý druh je k dispozici v padesáti exemplářích. Určete, kolika způsoby lze zakoupit A) 15 pohlednic; B) 51 pohlednic; C) 8 různých pohlednic. [2] Řešení: A) Vybíráme 15 pohlednic z 10 různých druhů: 15 + (10-1)\ /24\ . 24! v r 1307504] 15 ) \15J 1 15!9! B) V tomto případě nemůžeme vybrat 51 pohlednic jednoho druhu. Proto odečteme počet případů, kdy jsou všechny pohlednice stejné, a dostaneme náš výsledek: 51 + 51° ~ ^) ~ 10 = (51) ~ 10 ^= 14783142660 - 10 = 14783142650] C) Vybíráme 8 různých pohlednic, tzn. že se prvky nemohou opakovat: '10N 8, ,45] 1.7.3 Příklady k procvičení Příklad 1.7.7. Určete počet všech trojúhelníků, z nichž žádné dva nejsou shodné a jejichž každá strana má velikost vyjádřenou jednou z číslic 4, 5, 6, 7. Řešení: '3) ^ Kapitola 1. Základní kombinatorické pojmy 54 Příklad 1.7.8. Ze všech bílých šachových figurek bez krále a dámy (tj. z osmi pěšců, dvou věží, dvou jezdců a dvou střelců) vybereme A) trojici, B) dvojici. Jaký je počet možností pro jejich složení? T¥tí Obrázek 1.26: Bílé šachové figurky, zdroj: [11] Řešení: A) (3)-3 [=20-3 = 17] (Odečítáme možnosti, kdy jsme vybrali 3 věže, 3 jezdce nebo 3 střelce.) B) (T) H 10] Příklad 1.7.9. 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, eso; karty téže hodnoty jsou přitom rozlišeny těmito „barvami": červená, zelená, žaludy, kule. Určete, kolika způsoby je možno vybrat čtyři karty, jestliže se A) rozlišují pouze „barvy" jednotlivých karet; B) rozlišují pouze hodnoty jednotlivých karet. [2] Řešení: A) B) 35] = 330] Příklad 1.7.10. Kolik různých neuspořádaných trojic mohou dát počty teček na jednotlivých šestibokých kostkách při vrhu třemi kostkami? (Stěny kostek jsou označeny jednou, dvěma, ... až šesti tečkami.) Obrázek 1.27: Tři kostky, zdroj: [11] Řešení: 56] Kapitola 1. Základní kombinatorické pojmy 55 Příklad 1.7.11. Klenotník vybírá do prstenu tři drahokamy; k dispozici má tři rubíny, dva smaragdy a pět safírů. Kolika způsoby může tento výběr provést, považujeme-li kameny téhož druhu za stejné? [2] Řešení: '3J-I [=10-1 = 9] Příklad 1.7.12. Mezi 6 dětí rozdělujeme 15 (stejných) tenisových míčků. A) Určete počet všech možných rozdělení. B) Určete počet všech rozdělení, při kterých každé dítě dostane aspoň jeden míček. [1] Řešení: A) Uvědomme si, že tentokrát rozdělující svislé čáry dáváme mezi děti. Proto výsledek je '15 + (6— 1)\ /20N 15 j viv 1 155041 B) Nejprve dáme každému dítěti jeden míček a poté rozdělíme zbylých devět míčků. '9 + (6-l)\ /14N Příklad 1.7.13. , . n , 1 2002] 9 I V 9 ' J Kolika způsoby si mohou tři osoby rozdělit 7 stejných hrušek a 5 stejných jablek, aniž by je krájely? (Připouštíme i situace, že některé osoby nic nedostanou.) [1] Řešení: Nalezneme nejprve počet všech rozdělení hrušek mezi 3 osoby, podobně jako v před- 7 + (3-l)\ /9N chozím příkladu, zjistíme, že jich je ( A po,é poce, väech rozdelení jablek, ,élo je (5 + \ ~ ") = g Podle pravidla součinu je možné rozdělení obou druhů ovoce provést (^) ■ (c ) =756 způsoby. Kapitola 1. Základní kombinatorické pojmy 56 Příklad 1.7.14. V lahůdkářství mají kávu pěti ruzných druhů. Kolika způsoby je možné provést nákup 12 balíčků kávy? Kolika způsoby je to možné, požadujeme-li, aby v nákupu bylo alespoň po dvou balíčcích každého druhu kávy? [1] Obrázek 1.28: Káva, zdroj: [11] Řešení: Nákup káv je možný Požadujeme-li, aby v nákupu bylo alespoň po dvou balíčcích každého druhu kávy a kávy je pět druhů, deset balíčků je už určeno. Stačí tedy vybrat jen dva balíčky kávy, Příklad 1.7.15. Kolika způsoby lze do 9 různých přihrádek rozmístit 7 bílých a 2 černé koule A) nesmí-li žádná přihrádka zůstat prázdná? B) mohou-li některé přihrádky zůstat prázdné? [1] A) Nesmí-li žádná přihrádka zůstat prázdná, tzn. že v každé bude právě jedna koule. Stačí vybrat 2 přihrádky z devíti, v nichž budou černé koule. Do zbylých přihrádek je rozmístění bílých koulí jednoznačné. Poznámka: Všimněte si, že v případě a) se jednalo o kombinace bez opakování. V přihrádce mohla být pouze jedna koule, tato přihrádka se tedy nemohla opakovat ve výběru pro umístění další koule. V případě b) v přihrádce mohlo být více koulí a mohli jsme ji tedy použít opakovaně pro výběr umístění dalších koulí. Příklad 1.7.16. V prodejně mají na výběr 12 různých lízátek. Určete, kolika způsoby si lze z nich koupit A) 15 lízátek; B) 7 lízátek; C) 7 různých lízátek. [5] Řešení: [=36] B) Rozmístíme bílé koule a poté černé koule: [= 289575] Řešení: Kapitola 1. Základní kombinatorické pojmy * G2) [= 7726160] [=31824] [= 792] Kapitola 1. Základní kombinatorické pojmy 58 1.8 Faktoriál a kombinační čísla V této podkapitole si připomeneme, co to je faktoriál a kombinační číslo, a ukážeme si, jak se s těmito čísly počítá. Poté s využitím obou vyslovíme a dokážeme velmi užitečnou Binomickou větu. 1.8.1 Faktoriál Než začneme řešit příklady, připomeňme si definici faktoriálu z podkapitoly 1.3 Permutace bez opakování. Definice 5. Pro každé přirozené číslo n definujeme: w! = w-(w-l)-...-2-l,kde0! = 1. Číslo n\ čteme jako „n faktoriál". Poznámka: Všimněte si, že pro všechna přirozená čísla n,k, kde k < n platí: n-(n-l)-(n-2)-...-(n-k+l) (n-k)\ Příklad 1.8.1. Zjednodušte výrazy: (w + 1)! n\ (n-l)\ n\ A) V ; B) --— C) --- D) n\ (n+l)\ n\ (n-\)\ Řešení: A) = = =n | i b) h' h' - 1 n\ n\ 1 (h+1)! (n+l)-n\ (n+l) (»-!)! 1 D, n\ n-(n-l)! n ' n\ n-(n-l)\ n {n-\)\ (w-1)! 1 Příklad 1.8.2. Zjednodušte výraz: (m+1)! (2m)! (3m-l)! + ■ Řešení: m! (2m+l)! (3m-2)! (m+1)! (2m)! (3m-l)!_ m\ (2m+l)! + (3m-2)! ~ (m+l)-m! (2m)! (3m-1) • (3m-2)! m\ (2m+l)-(2m)! H (3m-2)! . 1 8m2 + 4m-l = m+1)-—--+ 3m-l = —--—- v ' (2m+l) v 7 (2m+l) Kapitola 1. Základní kombinatorické pojmy 59 Příklad 1.8.3. Zjednodušte výraz: (z+1)! z! (z!)2 [(z-1)!]2 Řešení: z\ -z! z-(z-l)! = (z+l) z (z!)2 [(z-1)!]2 z!-z! (z-l)I-(z-l)! z! (z-1)! _ (z+1) | z-z _ (z+1) | z2 _ z2 + z+l z! (z— l)!-z z! z! z! Příklad 1.8.4. Zjednodušte výrazy[2]: 1 3 n2-4 n2-9 6 1 A) — — t TTTT — 7 77TŇ7 B) -——— + ■ n! (n + l)! (n + 2)! (n + 3)! (n + 2)! (n + l) (fc + 2)! (fc+1)! fc! (fc + 2)! (fc+1)! ; fc! (fc-l)! (fc-2)! (£+1)! fc! Řešení: AS 1 3 n2-A n+l 3 (n-2)-(n + 2) A) — - 0 n! (n + l)! (n + 2)! (n + l)-n! (n+l)! (n + 2)-(n+l)! n + l 3 (n-2) _ (n + 1) - 3 - (n - 2) _ 0 ~ (n+l)! ~ (n+l)! ~ (n+l)! ~ (n + l)! ~ (n+l)! ~ C) 2 D) l 1.8.2 Kombinační čísla Opět si na úvod připomeňme definici kombinačního čísla z podkapitoly 1.4 Kombinace bez opakovaní. Definice 7. Pro vyjádření K(k,n) užíváme i symbol , nazývá se kombinační číslo a čte se „n nad k". Veta 4. Pro všechna celá nezáporná čísla n, k, kde k < n, platí: Kapitola 1. Základní kombinatorické pojmy Příklad 1.8.5. A) Ověřte, zda platí rovnosti: '3\ /3\ /12\ f\2\ fl\ fl\ /41\ /41 K2J \IJ \1 J \5 J \1 J \IJ \4 J V37 B) Dokažte, že pro všechna celá nezáporná čísla k, kde k < n platí: n \ ín n —k) \k Řešení: 3\ 3! 3! /2 2!(3-2 ! 2!1! 1 x3\ 3! 3! 3 ' IJ 1!(3-1)! 1!2! 1 12\ 12! /12\ 12! ANO 7 J 7!5!' \5 J 5!7! 7\ 7! 7! /7\ 7! 7 — = 1, L=tttt = -=7 =^ NE 7y 7!0! 7! \IJ 1!6! 1 41\ 41! /41\ 41! ANO B) Aj 4!37! V37/ 37!4! « \ n\ n\ In Kn-k) (n-k)\-[n-(n-k)]\ (n-k)\-k\ \k Příklad 1.8.6. A) Vypočítejte: B) Dokažte, že pro všechna přirozená čísla n platí: /n\ fn\ In I. J = =1, II. 0/ \n ' VI Řešení: '5\ 5' 5' A) ■ X OJ 0!(5-0)! 5! 14\ 14! 14/ 141(14-14)! 38\ 38! 38! 38 „n ^t = ^ = 38 1 J 1!(38-1)! 37! 1 n\ n\ B)I vO; 0!-(n-0)! n\ I /n\ = ín /n\ n\ n\ .IVO/ \n n J (w-0)!-0! n\ Kapitola 1. Základní kombinatorické pojmy 61 II. IJ l!-(w-l)! (w-1)! Příklad 1.8.7. Dokažte, že platí: Řešení: '0' 0! 0/ 0!-0! Příklad 1.8.8. A) Ověřte rovnosti: 21\ /21 2 + 3 22 3 Ml B) Dokažte, že pro všechna celá nezáporná čísla n, k, kde k < n platí: n \ I n k) + U+l Řešení: 21\ f 21 2 + 3 7! 7! + ■ 5!2! 6!1! 21! 21! + 28, Ml B)lJ + Ui 2!19! 3!18! 5! 5! + ■ 2!3! 3!2! 20, + ■ 8 6 1540, «+1 yt+1 8! 6!2! 22' 3 6! 4!2! = 28 = 22! = 3!19! 15 =; ANO 1540 NE k\-{n-k)\ (k+l)\-[n-(k+l)}\ A, ANO k\-(n-k)-[n-(k+l)}\ (k+l)-k\-[n-(k+l)}\ n\ fl 1 (n + 1)! \n-k k+1 n\ n+1 (n-k)-(k+l) (k+ 1)! • (n - k)\ n + ľ k+l Příklad 1.8.9. Vyjádřete jediným kombinačním číslem součet: IHl Kapitola 1. Základní kombinatorické pojmy 62 Řešení: Protože Platí [1) + í] Příklad 1.8.10. Vyjádřete jediným kombinačním číslem součet: Řešení: Protože platí: 6 Ml +i3i+ + 4) + (3/ v4 Pascalův trojúhelník Vlastnosti kombinačních čísel ilustruje následující schéma, které se nazývá Pascalův trojúhelník: Kapitola 1. Základní kombinatorické pojmy 63 Pokud si čísla ve schématu vyčíslíme, dostaneme Pascalův trojúhelník tvaru: 1 1 1 2 1 13 3 1 1 4 6 4 1 1 5 10 10 5 1 Všimněte si v trojúhelníku všech výše dokázaných vlastností: Platí také symetrie od středu každého řádku: Součet dvou sousedních čísel je číslo nacházející se o řádek níž mezi nimi: Jistě všichni víte, čemu se rovná (a + bf [=1] (a + b)1 [=a + b] (a + b)2 [=a2 + 2ab + b2] Někteří možná tušíte, čemu se rovná (a + b)3 [=a3 + 3a2b + 3ab2 + b3} Dokázali byste určit i na čtvrtou? (a + b)4 [=a4 + 4a3b + 6a2b2 + 4ab3 + b4] A co (a + b)i5? S pomocí Binomické věty snadno určíte i tento rozklad. Všimněte si koeficientů u jednotlivých mnohočlenů. 1.8.3 Binomická věta Kapitola 1. Základní kombinatorické pojmy 64 1 <—► 1 1 <—► 12 1 <—>■ 13 3 1 <—► 4 6 4 1 ^ O i)'G o G G ž) G) G) G í) í G G G Jaké by tedy byly koeficienty u (a + b)57 1 5 10 10 5 1 neboli '5\ /5\ /5\ /5\ /5\ /5 oy v1/ v2/ v3/ w V5 Koeficienty mnohočlenů snadno určíme z Pascalova trojúhelníku. Všimli jste si ještě, jak je to s exponenty? U „a" postupně klesaly, u „b" se postupně zvyšovaly a přitom jejich součet je vždy roven exponentu u závorky (a+b). Nyní už můžeme snadno určit celý rozvoj: (a + b)5 = Q a5b° + Q + Q '»7 - G>y+G>v+G>v+G>v+G + x1/ + Q A7 = A'7 + 7x6y + 2 lx5/ + 35xV + 35rV + 2 ljry5 + 7xy6 + y1 Kapitola 1. Základní kombinatorické pojmy 66 Příklad 1.8.12. Vypočtěte podle binomické věty: (*2 + l)4 Řešení: (*2+1)4=Q (*2)4i°+(í) í^2)3!1+Q) (-2)2i2+Q) (-2)1!3+(4) (-2)°i4= = x*+4x6 + 6x4 + 4x2 + l Příklad 1.8.13. Vypočtěte podle binomické věty: (*2-l)4 Řešení: (*2 -1)4=Q) (^2)4(-i)°+(i) (^2)3(-i)1+Q) (^2)2(-i)2+ + ^2)1(-1)3+(4) (^2)°(-l)4 = = x8-4/ + 6x4-4x2 + l Příklad 1.8.14. Vypočtěte podle binomické věty: (2c + V3)6 Řešení: (2c + V3)6 = = Q (2c) W + Q (2c)^(V3)1 + Q (2c)4(^3)2+ Q (2c)3(,/3)3+ + Q (2c)2(V3)4 + Q (2c)HV3)5 + Q (2c)°(VŠ)6 = = 64-c6 + 6-32-\/3-c5 + 15-16-3-c4 + 20-8-(\/3)3-c3+ +15-4-32-c2 + 6-2-(\/3)5-c + 33 = = 64-c6+192-V3-c5+720-c4 + 160-(\/3)3-c3+540-c2 + 12-(^)5-c + 27 Kapitola 1. Základní kombinatorické pojmy 67 Příklad 1.8.15. Vypočtěte bez kalkulačky užitím binomické věty: 2,014 Řešení: 2,014 = (2+KT2^4 24 • (lír2)0 + Q 23 • (10-2)1 + Q22 • (10-2)2+ + Q2i.(10-2)3+Q20.(10- = 16 + 4 • 8 • 0,01 + 6 • 4 • 0,0001 +4-2-0,000001 + 0,00000001 = = 16.32240801 Poznámka: Příklad by se dal sice počítat i roznásobením 2,01 -2,01- 2,01 -2,01, ale bylo by to mnohem pracnější a složitější. Můžete si vyzkoušet sami. Příklad 1.8.16. Vypočtěte bez kalkulačky užitím binomické věty: 1,994 Řešení: 1,994 = (2- 10~2^4 4 ) 24 • (-10-2)0 + Q23 • (-10-2)1 + Q 22 • (-10-2)2+ + Q2i.(-10-2)3+Q2o.(-10-2)4 = 16 - 4 • 8 • 0,01 + 6 • 4 • 0,0001 -4-2-0,000001 + 0,00000001 15.68239201 Poznámka: Příklad by se dal sice počítat i roznásobením 1,99 • 1,99 • 1,99 • 1,99, ale bylo by to opět mnohem pracnější a složitější. Můžete si vyzkoušet sami. Kapitola 1. Základní kombinatorické pojmy 68 1.9 Procvičování Příklad 1.9.1. Volejbalový turnaj je rozdělen na 4 skupiny. V každé skupině je 5 týmů. V rámci skupiny hraje každý tým s každým. A) Kolik zápasů se v turnaji odehraje? B) Kolik zápasů se v turnaji odehraje, hrají-li ještě vítězové všech skupin každý s každým o celkové první místo? Řešení: [=46]. Příklad 1.9.2. Kolik anagramů lze vytvořit z názvu brněnského prvoligového fotbalového týmu? (k 26.4.2015) Řešení: Počet písmen: A - 1, B - 1, J - 1, K - 1, O - 2, R - 1, V - 1, Z - 1 |1 = 181440 [=/"(l, 1,1,1,1,1,1,2)] Příklad 1.9.3. Z čety 14 vojáků sestavujeme dvojčlenné hlídky, kde jeden z vojákuje velitelem. Kolik hlídek můžeme sestavit? Řešení: Velitel a voják: 14 ■ 13 = 182 [= V(2,14)] Obrázek 1.29: Znak fotbalového klubu, zdroj: [11] Příklad 1.9.4. Kuba má tři červené a dvě modré kostky, čtyři z nich chce postavit na sebe. Kolik barevně různých věží může postavit? Obrázek 1.30: Červené a modré kostky, zdroj: [11] Řešení: Kapitola 1. Základní kombinatorické pojmy_69 Může použít buď 2 červené a 2 modré kostky nebo 3 červené a 1 modrou. --1--= 10 3! 2!-2! Příklad 1.9.5. Určete počet trojciferných přirozených čísel, ve kterých se nevyskytuje číslice 2? Řešení: 8 • 9 • 9 = 648 Příklad 1.9.6. Na cestu z Lísek do Bylnice si musíme koupit lístek na autobus. Na lístku je uvedených 9 číslic. Řidič může označit 1-8 číslic. Kterých možností je více, když označí dvě anebo sedm číslic? Řešení: = 36, možností je stejný počet. Příklad 1.9.7. Kolik různých způsobů máme, chceme-li postavit 10 osob (Alenu, Danu, Elišku, Petru, Zdenu, Karla, Luboše, Ondřeje, Petra a Viktora) do řady tak, aby žádné dvě ženy ani muži nestáli vedle sebe? Řešení: Pokud jako první bude jedna z žen, způsobů je: 5-5-4-4-3-3-2-2-M = 5!-5! = 14400. [= P(5)-P(5)] Ovšem na prvním místě může být také muž, proto celkový počet způsobů je: 2■14400 = 28800. Příklad 1.9.8. Kolik sudých tříciferných přirozených čísel můžeme sestavit z číslic 0, 1,5, 6, 8, 9 tak, že se číslice mohou opakovat? Řešení: 5 • 6 • 3 = 90 Kapitola 1. Základní kombinatorické pojmy 70 Příklad 1.9.9. Na visacím zámku jsou tři kolečka číslic 0, 1,2, 3, 4, 5, 6, 7, 8, 9. Pro jeho odemknutí musíme zadat správnou posloupnost tří číslic. Kolik nejvíc minut nám může trvat jeho odemknutí, jestliže zadání jedné posloupnosti trvá průměrně 1,5 sekundy? Řešení: Jedná se o 1000 různých čísel, tedy 1000 různých variací. 1,5 • 1000 = 1500 sekund = 25 minut. Příklad 1.9.10. V prodejně mají na výběr 15 různých hrníčků a skleniček. Určete, kolika způsoby si lze z nich koupit A) 17; B) 8; C) 8 různých. Obrázek 1.31: Hrnky a skleničky, zdroj: [11] [=265182525] [=319770] [= 6435] Řešení: Příklad 1.9.11. Z pěti děvčat Báry, Evy, Lídy, Niny a Verči a ze čtyř chlapců Marka, Olina, Pavla a Vaška vybírá paní učitelka dvojici (dívka a chlapec) na jízdu na dvojkole. Kolik takových různých dvojic může utvořit? Řešení: 5-4 = 20 Příklad 1.9.12. V sérii 11 výrobků jsou právě 3 vadné. Kolika způsoby z nich lze vybrat: A) 5 libovolných výrobků, B) 5 výrobků bezvadných, C) 5 výrobků, z nichž právě 1 je vadný, D) 5 výrobků, z nichž právě 2 jsou vadné, Kapitola 1. Základní kombinatorické pojmy 71 E) 5 výrobků, z nichž právě 3 jsou vadné? Řešení: A) (y) [=462] B) Q [=56] 3\ /8 C)WW 1=2101 3\ /8 E)(3j.^| [=28] Příklad 1.9.13. V restauraci nabízí 4 různé polévky, 12 hlavních jídel a 6 moučníku. Kolik různých obědů tvořených z polévky, hlavního jídla a moučníku si můžeme vybrat? Řešení: 4-12-6 = 288 Příklad 1.9.14. Autobus linky 84 přijel na zastávku Slovanské náměstí, otevřely se troje dveře a nastoupila pouze Jitka se Zuzkou. Kolik bylo různých možností, jak mohly dívky nastoupit do autobusu? (Možnosti považujeme za různé, pokud alespoň jedna osoba nastoupila jinými dveřmi.) Řešení: 3-3 = 9 [=V'(2,3)] Příklad 1.9.15. Děti se měly ve škole fotit. Klára, Petra, Šimon, Honza a Jirka chtěli společnou fotku, ovšem za podmínek, že dívky chtějí stát vedle sebe a Jirka chce být na kraji. Kolikrát by musel fotograf vyfotit děti, aby zachytil všechny možnosti, jak děti mohou stát v jedné řadě? Řešení: Jirku nejprve postavíme vlevo, Kláru a Petru sloučíme k sobě a rozmísťujeme tedy 4 „děti": 1-3-2-1 = 6 Dívky si mohou ještě prohodit místa: 6 • 2 = 12 Jirka může stát také vpravo, proto celkový počet fotografií by byl 12 • 2 = 24. Kapitola 1. Základní kombinatorické pojmy 72 Příklad 1.9.16. Maminka chce Jeníkovi a Mařence rozdělit tři stejné hrušky a dvě stejná jablka. Kolika způsoby to může udělat, aniž by ovoce krájela? Obrázek 1.32: Ovoce, (Připouštíme i situaci, že některé z dětí nic nedostane.) [4] zdroj: [11] Řešení: Tři hrušky samostatně může maminka rozdělit čtyřmi způsoby. (Rozdělení je určeno tím, kolik hrušek dá Jeníkovi, zbytek připadne Mařence.) Dvě jablka pak nezávisle třemi způsoby. Podle pravidla součinu pak obě ovoce současně může rozdělit 4-3 = 12 způsoby. Příklad 1.9.17. Určete počet čtyřciferných čísel sestavených z právě dvou různých číslic. [4] Řešení: Dvě různé číslice použité na zápis můžeme vybrat { ) způsoby, ze dvou vybraných 2, číslic můžeme sestavit 24 — 2 různých čtyřciferných čísel (dvojku odečítáme za dvě čísla sestavená pouze z jedné číslice). Celkem máme (^^j ' ^ — ^) = ^30 čísel. Nyní jsme ale započítali i čísla začínající nulou, těch je • (23 — 1) = 63. Celkově dostáváme 630 - 63 = 567 čísel. Příklad 1.9.18. V rovině je dáno 10 různých bodů. Kolik přímek tyto body určují, jestliže: A) žádné tři neleží na jedné přímce, B) právě 6 z nich leží na jedné přímce? Řešení: A) Přímka je určena dvěma body a na jejich pořadí nezáleží, proto: ^ [= 45] B) Q-0 + . [-3.1 Příklad 1.9.19. H/^A (Jb\^ é £f\ ^ Kolika způsoby lze rozestavit v první řadě šachovnice tyto bílé figurky: 2 koně, 2 střelce, Obrázek 1.33: Šachové figurky, zdroj: 2 věže, 1 krále a 1 dámu? [11] Řešení: _11_ = 5040 [=P'(1,1,2,2,2)] Kapitola 1. Základní kombinatorické pojmy 73 Příklad 1.9.20. Máme-li k dispozici neomezené množství mincí o hodnotách 10,20 a 50 haléřů. Kolika způsoby z nich lze vybrat 20 mincí? [1] Řešení: '22 20 Příklad 1.9.21. 231] Kolika způsoby lze na šachovnici vybrat: A) dvě pole, B) dvě pole různých barev, C) dvě pole neležící ve stejné řadě ani ve stejném sloupci, D) dvě pole různé barvy neležící ve stejné řadě ani ve stejném sloupci? Řešení: A) ([= 2016] B) Í3,2VÍ3,2) H1024, 1 / V 1 64\ „ /8\ „ /8 °Ur8"Ur8'W 1= 15681 Příklad 1.9.22. Sešlo se pět přátel a navzájem si potřásli rukama. Určete počet všech potřesení. Obrázek 1.34: Pět přátel, zdroj: [11] Řešení: '5 10] Příklad 1.9.23. Král Artuš posílá 6 spěšných zpráv svým rytířům. Každý ze tří připravených poslů může doručit libovolnou ze zpráv. Kolika způsoby může král Artuš rozdělit dopisy mezi kurýry? [1] Řešení: 36 = 729 [=V'(6,3)] Kapitola 1. Základní kombinatorické pojmy 74 Příklad 1.9.24. Kolik anagramů lze vytvořit z písmen názvu nej starší brněnské univerzity? Řešení: A - 3, K - 1, M - 1, O - 1, R - 1, S - 1, V - 1, Y - 1: ^ = 604800 [=P'(1,1,1,1,1,1,1,3)] Příklad 1.9.25. U rovnice X\ +X2 +Xt, +X4 = 9 určete počet řešení v množině celých nezáporných čísel. [1] Řešení: Zašifrujeme pomocí nul a jedniček tak, že mezi 9 jedniček (součet je 9) vložíme (4-1) nul (určíme tím rozdělení na 4 čísla). 9+rK92) ™ Příklad 1.9.26. Máme čtyři bílé koule, čtyři černé koule a čtyři červené koule. Kolika způsoby je můžeme rozdělit do 6 rozlišitelných přihrádek? [3] Řešení: 3-(')■(') »76i Příklad 1.9.27. Kolik přirozených čísel menších než 105 lze zapsat pouze pomocí cifer 7 a 9? [1] Řešení: 2 + 22 + 23 +24 + 25 = 62 [= V'(l,2) + V'(2,2) + V'(3,2) + V'(4,2) + V(5,2)] Příklad 1.9.28. Řešení: Počet semiciferných palindromů: Stačí rozmístit číslice na první čtyři cifry, poslední tři j sou jednoznačně určené výběrem prvních tří. 9-10-10-10 = 9000 Počet osmiciferných palindromů lze spočítat podobně (vybíráme jen první čtyři cifry): 9-10-10-10 = 9000 Kapitola 1. Základní kombinatorické pojmy 75 Palindrom je posloupnost symbolů, která je stejná, čteme-li 5 7 O je zepředu i zezadu (např. „tabat"). ^ 5 2 Určete počet sedmiciferných a osmiciferných palindromů (v dekadickém zápisu), nesmí-li se žádná číslice užít více , , . „_ , v . . r„. Obrázek 1.35: Palindrom, nez jednou.131 . . zdroj: autor Příklad 1.9.29. V městské radě je 10 zástupců levice a 11 zástupců pravice. Levici zastupují 4 ženy, pravici 3 ženy. Určete, kolika způsoby lze sestavit osmičlenný výbor, v němž má být stejný počet zástupců levice i pravice a stejný počet mužů i žen. [3] Řešení: Vybíráme 2 ženy a 2 muže z levice a stejný počet i z pravice: [= 7560] Příklad 1.9.30. Kolika způsoby lze postavit do řady na poličku 10 různých knih českých a 5 různých knih anglických tak, že nejprve budou knihy české a vedle nich knihy anglické? [6] Řešení: 10!-5! =435456000 Příklad 1.9.31. P(10)-P(5)] V krabičce je 10 pastelek, z toho 4 stejné červené, 3 stejné modré, 2 stejné žluté a jedna zelená pastelka. Kolika způsoby lze pastelky v krabičce uspořádat? [6] Obrázek 1.36: Pastelky, zdroj: [11] Řešení: 10! 4!-3!-2! 12600 ni,2,3,4)] Příklad 1.9.32. V cukrárně mají pět druhů dortů v dostatečném množství. Kolika způsoby si můžeme koupit 8 dortů? [6] Řešení: [= 495] Kapitola 2 Rozšiřující kombinatorické pojmy 2.1 Burnsideovo lemma Toto důležité lemma zformuloval anglický matematik William Burnside (1852 - 1927). Díky němu můžeme velice jednoduše spočítat na první pohled velmi složité příklady. Než přistoupíme k samotnému lemmatu, zopakujeme si některé důležité pojmy. 2.1.1 Pojmy Permutace, grupa Buď X libovolná konečná množina. Symbolem S(X) značíme všechny permutace množiny X. Připomeňme si, že permutace n prvků je uspořádaná w-tice sestavená z těchto prvků tak, že se v ní každý vyskytuje právě jednou. Což můžeme říci i slovy, že permutace na množině X je zobrazení z X do X, které je prosté (žádné dva prvky se nezobrazí na stejný prvek) a na každý prvek se nějaký prvek zobrazí. Množinu všech permutací na množině X budeme značit S(X), jednotlivé permutace budou značeny řeckými písmeny (n, p,...). Permutace lze skládat a k dané permutaci lze najít permutaci inverzní. Poznamenejme jenom, že % o p značí permutaci vzniklou provedením p a pak provedením %. Pro další úvahy ještě vezměme jednu pevnou podmnožinu množiny S(X), která je uzavřená na skládání permutací, a označme ji G. Poznamenejme, že G je podmnožina permutací taková, že s každou permutací obsahuje i její inverzi a se dvěma permutacemi obsahuje i jejich složení (mj. tedy obsahuje i identitu, tj. permutaci, která všechny prvky nechává na místě). [8] Orbita Pro x EX označme Ox = {n(x) \tz EG} takzvanou orbitu prvku x; to jsou body, kam se můžeme z x dostat použitím permutací z G. Množinu všech orbit, tj. {Ox\x E X}, budeme značit 6. Všimněte si, že pokud y E Ox, tak Ox = Oy. Intuitivně - pokud se z x mohu dostat do y, tak se z obou mohu dostat do týchž míst. [8] -76- Kapitola 2. Rozšiřující kombinatorické pojmy 77 Z toho ovšem plyne důležitý důsledek: orbity tvoří rozklad množiny X. Tzn., že každé x EX leží v právě jedné orbitě. Zjevně totiž x E Ox. Pokud by x ležel ještě v nějaké jiné orbitě, tj. x E Oy a Ox ^ Oy, pak dle předchozího odstavce Ox = Oy, což je spor. V množině ď jsou tedy množiny, které jsou po dvou disjunktní a jejichž sjednocení je celé X. [8] Pevné body, stabilizátor Je-li % E S(X), označme Pn = {x E X \ n(x) = x] množinu tzv. pevných bodů permutace %, tj. těch bodů, které % nechává na místě. Pro x EX označme Stx = {n E G \ Tt{x) = x] množinu těch permutací z G, pro které je x pevným bodem. Lemma 1. Burnsideovo lemma kde ď je množina všech orbit a G je nějaká množina permutací X, která je uzavřená na skládání. Jinými slovy: Počet orbit je průměrný počet pevných bodů permutací z G. K důkazu použijeme následující lemma. Lemma 2. Vlastnosti St (1) Je-li x EX, tak\Ox\-\Stx\ = |G|. (2) Jsou-li x,y E X a y E Ox, tak \Stx\ = \Sty\. Důkaz vlastností St[8]: (1) Pro y E Ox označme %y libovolnou permutaci z G, která převádí x na y, tj. 7ty (x) = y (nějaká taková určitě existuje, jinak by y nebylo v Ox). Chceme ukázat, že dvojic (y,p), y E Ox, p E Stx,je stejný počet jako prvků G. Nejlépe to uděláme tak, že najdeme předpis, jak takové dvojici přiřadit prvek G tak, aby různým dvojicím odpovídaly různé prvky G a každý prvek v G byl použit. Dvojici (y, p) přiřaďme prvek F (y, p) = %y o p. Protože %y i p byly prvky G, je i jejich složení prvek G. Nyní je třeba ukázat, že zobrazení F je prosté a na každý prvek se nějaký prvek zobrazí. F je prosté: vezměme (y\,p\) ^ (>"2,P2)- Nechť nejprve y\ j^y2- Potom F (yi, pi)(x) = = yi, F(y2,P2)(x) = yi, a tedy zobrazení F(ji,pi) a i7(>>2,P2) se liší alespoň hodnotou v prvku x. Nechťje tedy y\ = y2 = y, a tudíž pi ^ p2- Existuje proto nějaké z EX, pro něž Pi(z) ^P2(z). OvšempakiF(j,pi)(z) ^ F(y,p2)(z). Takže F je prosté. Na každý prvek se nějaký prvek zobrazí: mějme c G G a hledejme y EX, p E Stx, že F(y7p) = o. Stačí vzíty = o(x) a p = o o. (2) Abychom ukázali, že \Stx\ = \Sty\, najdeme nějaké zobrazení F : Stx —ř Sty, které bude prosté a kde na každý prvek se nějaký prvek zobrazí. Položme F (p) =iyopo(iy)_1. Kapitola 2. Rozšiřující kombinatorické pojmy 78 Ihned vidíme, že pro p G Stx je F (p) G Sty. Nepříliš těžko vidíme, že F je prosté a na každý prvek se nějaký prvek zobrazí. Důkaz Burnsideova lemmatu[8]: Dokazovanou rovnost upravme na tvar \&\ ■ \ G\ = Y,neGUvažme nyní množinu A = {(tt,x) I % G G, jc G Pn}. Nyní použijeme poměrně častý trik: budeme počítat velikost množiny A dvěma způsoby. Nejprve berme permutace % z G jednu po druhé a pro každou zjistěme, kolik x G X je možno k % přidat, aby vznikla dvojice z A. Tímto postupem zjistíme, že \A\ = Y.neG \pn\- A teď naopak probírejme prvky X a pro každý určeme, kolik k němu můžeme přidat permutací %. Takto zjistíme, že |A| = Y*xex \Stx\- Vzhledem k předchozímu lemmatu, části (2), je toto rovno Y,oeff \ Ox01' \^x0V kde xo je libovolný prvek O. Vzhledem k lemmatu, části (1), můžeme toto dále upravit na Y,oeff 1^1 = 1^1' 1^1 • Dohromady tedy dostáváme I @\' \ G\ = Y,7zeG l-řjrl' c°ž jsme chtěli dokázat. 2.1.2 Řešené příklady Příklad 2.1.1. Náhrdelníky Máme tři brilianty a pět safírů. Kolik různých náhrdelníků z nich můžeme sestavit? Náhrdelníkem rozumíme navlečení drahokamů na šňůrku (ta je vzadu svázaná, čili je to kruh). Přitom dva náhrdelníky, které se liší jen pootočením, považujeme za shodné. [8] Řešení: S náhrdelníkem můžeme provést celkem osm rotací Rq, Ri, R2, R3, R4, R5, R(,, R7, přičemž R^ je rotace o k- 45° (360°/8 = 45° - pootočení o jeden drahokam). Každé této rotaci odpovídá permutace na množině všech pevných náhrdelníků. Např. rotaci Ri odpovídá permutace Tt\, která každý pevný náhrdelník zobrazí na jiný pevný náhrdelník, oproti původnímu otočený o 45 °. Nyní počet orbit, tj. \&\, je hledaný počet různých náhrdelníků. Jedna orbita je totiž tvořena pevnými náhrdelníky, které jdou na sebe převést otočením a které tedy považujeme za jeden náhrdelník. Burnsideovo lemma nám říká, že tento počet můžeme zjistit tak, že pro fto,..., Ttq určíme počet pevných bodů a spočteme průměr. TtQ je identita, má \X\ =56 pevných bodů (je to počet různých pevných náhrdelníků). Snadno se rozmyslí, že ostatní permutace žádné pevné body nemají (pokud otočím jakkoli uspořádaný náhrdelník, nikdy jej nemohu otočit na stejně uspořádaný). Průměrný počet pevných bodů je tedy |^| = 1.(56 + 0 + 0 + 0 + 0 + 0 + 0 + 0) =7. 8 Hledaný počet náhrdelníků je tedy 7. Příklad 2.1.2. Monomino Kolika způsoby můžeme umístit jedno monomino do tabulky SxS tak, že nerozlišujeme situace vzniklé pootočením i překlopením? Kapitola 2. Rozšiřující kombinatorické pojmy 79 (Monomino je čtvereček o straně délky 1.) Řešení: Permutace v tomto případě představují 4 rotace a 4 osové souměrnosti. Rotace o 0°, 90°, 180° a 270°. Osové souměrnosti s osou horizontální(/z), vertikální(v) a 2 diagonální osy( s pak v žádném. Proto celkový příspěvek prvku m k pravé straně vzorce je podle identity níže. Na levé straně vzorce je prvek m ovšem započten také právě jednou. Tím je důkaz tvrzení ukončen; zpřesnili jsme v něm názornou myšlenku, která k odvození vzorce vede: v součtu \M\ \ + \M2 \ +... \Mn\ jsou započteny právě jednou ty prvky, které leží v právě jedné z množin M f, ty prvky, které leží zároveň v několika množinách, jsou zde započteny vícekrát. Odečteme-li £ |Mř- C\Mj\, uvedeme na pravou míru ty prvky, které leží právě ve dvou množinách, přitom počty prvků patřících do aspoň tří množin jsou redukovány příliš. To se pro ty prvky, které patří do právě tří množin, napraví přičtením součtu £ \Mi n M j n Mk I atd. Identita: Pro n > 1 platí: Příklad 2.2.3. Ve zverimexu mají 15 zvířat, jenž žerou rostlinnou stravu, a 9 zvířat, jenž žerou maso. 5 z těchto zvířat jsou všežravci. Kolik zvířat mají ve zverimexu? Řešení: Označíme si: zvířata, jenž žerou rostlinnou stravu = R, zvířata, jenž žerou maso = M, zvířata, která jsou všežravci = R fl M, všechna zvířata = RUM. \RUM\ = |Z?| + |Ař|- |Z?nAř| = 15 + 9-5 = 19. Příklad 2.2.4. Dopravní kontrola zjišťovala technický stav brzd a ojetí pneumatik. Za špatný stav brzd uložila pokutu 15 řidičům, za ojeté pneumatiky uložila pokutu 12 řidičům. Ze všech 53 kontrolovaných řidičů nezjistila žádnou chybu u 30. Vypočítejte, kolik řidičů zaplatilo pokutu za oba zmíněné nedostatky svého vozidla, kolik jen za špatný technický stav brzd, a kolik jen za ojetí pneumatik. [7] 2.2.2 Příklady k procvičení Kapitola 2. Rozšiřující kombinatorické pojmy 92 Řešení: Kontrolováno bylo 53 řidičů. U 30 aut kontrola nenašla žádnou chybu. Proto počet aut s nějakou závadou je 53 — 30 = 23. Označíme si: auta se špatnými brzdami = B, \B\ = 15, auta s ojetými pneumatikami = P, \P\ = 12, auta s nějakou závadou = B U P, \B U P\ = 23, auta s oběma závadami = B n P, \B n P\ =?. Obrázek 2.10: Označení množin aut, zdroj: autor Kolik bylo aut s oběma závadami? \BUP\ = \B\ + \P\-\Bí)P\ \Bf]P\ = \B\ + \P\-\BUP\ = 15 + 12-23 = 4 Kolik bylo aut jen se špatnými brzdami? |fí|-|fínP| = 12-4 = 8 Kolik bylo aut jen se špatnými pneumatikami? \P\-\Br\P\ = 15-4= 11 Příklad 2.2.5. Ve vědeckém ústavu pracuje několik lidí, z nichž každý zná alespoň 1 cizí jazyk. 6 ovládá angličtinu, 6 němčinu a 7 francouzštinu. 4 umějí angličtinu i němčinu, 2 angličtinu a francouzštinu, 3 němčinu a francouzštinu. 1 člověk ovládá všechny 3 jazyky. A) Kolik osob pracuje v ústavu? B) Kolik z nich ovládá pouze angličtinu? C) Kolik z nich umí jen francouzsky? [7] Řešení: Označíme si: lidé, kteří umí anglicky = A, lidé, kteří umí německy = N, lidé, kteří umí francouzsky = F. A) |A|U|iV|U|F| =? |A| U \N\ U |F| = |A| + \N\ + |F| - |AHAr| - |ADF| - |A^nF| + |AnA^nF| = Kapitola 2. Rozšiřující kombinatorické pojmy_93 = 6 + 6 + 7-4-2-3 + 1 = 11 B) Z náčrtku vyčteme, že jen angličtinu ovládá: |A| — |AfliV| — |AflF| + |AnATlF| = 6-4-2 + 1 = 1 C) Z náčrtku vyčteme, že jen francouzsky umí: \F\-\AnF\-\NnF\ + \AnNnF\ = 7-2-3 + 1 = 3 Příklad 2.2.6. Z 326 žáků určité školy hraje 92 žáků odbíjenou, 143 žáků nehraje fotbal. Právě jeden z těchto dvou sportů pěstuje 213 žáků. Kolik žáků hraje fotbal i odbíjenou? [7] Řešení: Označíme si: žáci hrající odbíjenou = O, \0\ = 92, žáci hrající fotbal = F, žáci nehrající fotbal ani odbíjenou = N, všichni žáci = O UF U N, \OUF UN\ = 326, Jaký je počet žáků hrajících fotbal? |F| = počet všech žáků - počet žáků nehrajících fotbal = 326 — 143 = 183. Dále víme, že právě jeden ze dvou sportů pěstuje 213 žáků. Tzn.: |0| + |F|-2-|0nF| =213. Z toho vyplývá, že žáků, kteří hrají fotbal i odbíjenou, je lODFl =31. Příklad 2.2.7. Personalistka jisté firmy poskytla řediteli následující informaci: ve firmě pracuje 250 mužů a 200 žen, přitom 160 mužů a 140 žen má vysokoškolské vzdělání, do práce dojíždí 180 mužů a 100 žen, vysokoškolsky vzdělaných mužů dojíždí 150 a vysokoškolsky vzdělaných žen 20. Co z toho může ředitel usoudit? Řešení: Ve firmě podle údajů pracuje celkem 250 + 200 = 450 lidí. Kolik z nich je žen bez vysokoškolského vzdělání, které do práce nedojíždějí? Kapitola 2. Rozšiřující kombinatorické pojmy 94 Označme vlastnosti osob: mužské pohlaví = M, ženské pohlaví = Z, všichni lidé =MUZ = L, má vysokoškolské vzdělání = V, nemá vysokoškolské vzdělání = nV, dojíždí do zaměstnání = D, nedojíždí do zaměstnání = nD. Platí: \M\ =250, |AřUZ| =450, \V\ = 160+140 = 300, |D| = 180+100 = 280, |AřnV| = 160, |AřnD| = 180, |VnD| = 150 + 20= 170, \MnVC)D\ = 150. \Zr\nVr\nD\ = \L\- \M\-\V\- \D\ + \Mf]V\ + \Mf]D\+ \V f]D\ - \MC]VnD\ \Z n nV n nD\ = 450 - 250 - 300 - 280 + 160 + 180 + 170 - 150 = -20 To samozřejmě není možné. Ředitel může usoudit, že personalistka udělala někde chybu. Příklad 2.2.8. Kolik přirozených čísel mezi 1 a 300 je A) dělitelných 3, 5 nebo 7; B) dělitelných 3 a 5, ale nedělitelných 7; C) dělitelných 5, ale ne 3 nebo 7 ? [7] Obrázek 2.11: Označení množin zaměstnanců, zdroj: autor Řešení: Označíme si: čísla dělitelná 3 = A = {«; 1 které zvíře 2) ^B) vybereme Honzovi: Honza Zbyněk 'Pro každou '* ^ *> ^ 2> || z těchto . 3 možností ,1 CB> ^ , jn »2. pro Honzu 2) W '> ® :> § máme s, 2 možnosti 3) KS _^ t) ^ 2) fá% pro Zbyňka: Honza Zbyněk 5) Z předešlého obrázku můžeme vidět, že celkový počet možností je: *x® 3X2=6 ir* -99- Přílohy_ 2. Řešení příkladu 1.2.1. Vlajky, části A) i oo 1) Doplňujeme barvy t na 3 svislé pruhy: 1 2) K dispozici máme 5 barev: O O O O O 3) Na první pruh máme 5 možností výběru barvy. 1 4) Barvy se nemohou opakovat, proto po obarvení 1. pruhu zbývají pro 2. pruh 4 barvy. I 5) Po obarvení 1. a 2. pruhu, zbývají pro 3. pruh 3 barvy. I 033 6) Kolik různých vlajek si může Mirek sestavit? 5 x 4 x 3 = 60 Přílohy_ 3. Řešení příkladu 2.2.1 Turnaje 101 1 Množina hráčů fotbalu 2) Množina hráčů volejbalu 3) Množina hráčů obou sportů ___Fnv____ ^) 4) Kolik se zúčastnilo celkem všech hráčů? 5) Množina všech hráčů ____F U V (g) 3) |F U V| = ? 6) Pokud sečteme počet hráčů fotbaíu a počet hráčů volejbalu: přičítáme dvakrát počet hráčů obou sportů |FnV|... 7) ... proto stačí jednou odečíst počet hráčů obou sportů |FnV|: OOO-o |FuV| = |F| + |V|-|FnV| |FU V| =35 + 32- 12 =55 Přílohy 102 4. Náhled webových stránek i':\u i Přílohy 5. Náhled příkladu a jeho zdrojového kódu Příklad 5 Kolika způsoby lze vybrat na šachovnici 3x3 jedno bílé a jedno černě pole? Kolika způsoby to lze učinit, nesmějí-li vybraná pole ležet ve stejném řádku ani ve stejném sloupci? Řešení: (skrýt text) Bílé pole lze vybrat 32 způsoby, černé rovněž. Celkový počet způsobů výběru je ( tedy v prvním případě roven 32 ■ 32 = 1024, ■ Vybereme-li v druhém případě jedno bílé pole (32 způsobů], lze černé vybrat už jen , z řádků a sloupců, v nichž vybrané bílé pole neleží, tj. 24 způsobů. Počet výběrů je tedy ' 32-24= 738. a 376 377 378 379 380 35 L 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 Fříklad b

Kolika způsoby lze vybrat na šachovnici 3x3 jedno bilé a jedno černé pole?

Kolika způsoby to lze učinit, nesněji-li vybraná pole ležet ve ste jnérr. řádku ani ve e; r.s sloupci?

Řešeni : Náhled šachovnice3ílé pole lze vybrat 32 způsoby, černé rovnéž. Celkový počet způscbů výběre je tedy v prvníir. případě roven ^32 \cdot 32 = 1024£.

Vybererr.e-li v druhéir. případě jedno bílé pole (32 způsobů) , lze černé vybrat jž jen z řádků a slojpců, v nichž vybrané bílé pole neleží, tj. 24 způscbů. Počet výběrů je tedy $32 Vcdot 24 = 738$.

Přílohy 6. Náhled příkladu se skrytým a zobrazeným řešením 104 Příklad 10 V prodejně mají na výběr 15 různých hrníčků a skleniček, Určete, kolika způsoby si lze z nich koupit A) 17; B) 8; C) 3 různých. Řešení: (zobrazit text) Příklad 10 V prodejně mají na výběr 15 různých hrníčku a skleniček, Určete, kolika způsoby si lze z nich koupit A) 17; B) 8; C) 8 různých. Řešení: A; (skryt tex±} [= 265182525] [= 319770] [= 84351 Přílohy 105 7. Náhled příkladu s interaktivním řešením Řešené příklady Příklad 1 - Turnaje V Husovicích se konal fotbalový a volejbalový turnaj. Na fotbalový turnaj přišlo 35 účastníků, na volejbalový 32 účastníku. 12 se jich zúčastnilo fotbalového i volejbalového turnaje, Kolik přišlo sportovců celkem? Řešení: (skrýt text} Označme si jednotlivé množiny: Množina hráčů fotbalu = F Množina hráčů volejbalu = V Množina hráčů obou sportů = fn V Množina všech hráčů = F U V Pro připomenutí, počet prvků dané množiny M označujeme \M\, Počítáme počet všech sportovců, kteří se zúčastnili obou turnajů: Množina väech h ráčil FuV 35 12 32 |F U V| = ? '"Interaktivním obrázkem můžete pohybovat pomocí modrých bodu ve spodní části obrázku anebo kliknutím a tažením pravým tlačítkem myši. Přepis řešení: Zajímá nás počet všech hráčů: F U V = ? V množině hráčů fotbalu jsou i hráči, kteří hráli také volejbal. A v množině hráčů volejbalu jsou i hráči, kteří hráli také fotbal, Z toho důvodu, pokud sečteme počet hráčů fotbalu a počet hráčů volejbalu, přičteme dvakrát počet hráčů obou sportů (Fn V}. Počet všech hráčů tedy obdržíme, pokud sečteme IFI + IVI a jednou odečteme F n V: |FuV| = |F| + |V|- |FnV| Dosazením: IFUVI = 35 + 32 - 12 = 55 Seznam použité literatury [1] HERMAN, Jiří, Radan KUČERA a Jaromír ŠIMŠA. Metody řešení matematických úloh. 3., přeprac. vyd. Brno: Masarykova univerzita, 2004,355 s. ISBN 80-210-3569-2. [2] CALDA, Emil a Václav DUPAČ. Matematika pro gymnázia: kombinatorika, pravděpodobnost, statistika. 5.vyd. Praha: Prométheus, 2012, 170 s. Učebnice pro střední školy (Prométheus). ISBN 978-807-1963-653. [3] FUCHS, Eduard. Diskrétní matematika pro učitele. 2. vyd. Brno: Masarykova univerzita, 2011, 178 s. ISBN 978-802-1054-592. [4] SLOVÁK, Jan, Martin PANÁK a Michal BULANT. Matematika drsně a svižně. 1. vyd. Brno: Masarykova univerzita, 2013, 773 s. ISBN 978-80-210-6307-5. [5] POLÁK, Josef. Přehled středoškolské matematiky. 8. vyd. Praha: Prométheus, 2003, 608 s. ISBN 8071962678. [6] Petáková, Jindra. Matematika příprava k maturitě a k přijímacím zkouškám na vysoké školy. 1. vyd. Praha: Prométheus, 2007, 288 s. ISBN 978-80-7196-099-7. [7] ZAGOROVÁ, Pavla. MuDisMat: Multimediální Diskrétní Matematika [online]. 2007 [cit. 2015-05-03]. Dostupné z: http://xzagorov.webzdarma.cz/MuDisMat3/ [8] ŠÁMAL, Robert. Burnsideovo lemma aneb kterak náhrdelníky spočítati. Matematický korespondenční seminář [online]. Rokytnice, 1998 [cit. 2015-05-03]. Dostupné z: http://mks.mff.cuni.cz/library/BurnsideovoLemmaRS/BumsideovoLernmaRS.pdf [9] BENDOVÁ, Hána. Burnsideovo lemma. Matematický korespondenční seminář [online]. Domaslav, 2010 [cit. 2015-05-03]. Dostupné z: http://mks.mff.cuni.cz/library/BurnsideovoJemmaJiB/BurnsideovoJemma JŤB.pdf [10] FARSKÁ, Jana. Kombinační čísla: Binomická věta. Laboratoř Carolina, Karlova Univerzita: Centrum podpory studia zrakově postižených na Universitě Karlově [online]. 2015 [cit. 2015-05-03]. Dostupné z: http://carolina.mff.cuni.cz/jana/kombina-torika/04binomicka_veta .htm [11] Pixabay: Volné obrázky vysoké kvality, které můžete použil kdekoli [online]. 2015 [cit. 2015-05-03]. Dostupné z: http://pixabay.com/ -106-