Diskrétní matematika (Kombinatorika) Helena Durnová 20. prosince 2013 Obsah 1 Úvod do diskrétni matematiky 2 2 Rozklady konečných množin 5 3 Princip inkluze a exkluze 8 4 Rozklady a kompozice přirozených čísel 13 5 Rozdělování do přihrádek 18 6 Rekurentní formule 23 7 Magické a latinské čtverce 26 8 Konečné roviny 28 1 Kapitola 1 Uvod do diskrétní matematiky Toto je pracovní verze studijního textu pro studenty matematiky Pedagogické fakulty Masarykovy univerzity v Brně. Obtížnější příklady jsou označeny hvězdičkou (*). Připomínky vítám. Pište, prosím, na adresu hdurnova@ped.muni.cz Staré kombinatorické úlohy Ve Rhindově papyru (matematika ve starém Egyptě) lze například najít tuto úlohu: Ve městě je 7 domů, v každém domě 7 koěek, každá koěka sežere 7 myší, každá myš sežere 7 zrnek pšenice, z každého zrnka pšenice by napřesrok vyrostlo 7 hekatů obilí. Kolik hekatů úrody zachrání kočky v 7 domech? Podobně vyznívá populární dětská říkanka o cestě do St. Ives: As I was going to St. Ives, I met a man with seven wives, Each wife had seven sacks, Each cat had seven kits, Kits, cats, sacks, and wives, How many were going to St. Ives? Ve Fibonacciho Liber abaci najdeme podobnou úlohu (převzato z [1]): Seven old women are going to Rome; each of them has seven mules; each mule carries seven sacks; each sack contains seven loaves; each loaf has seven knives; and each knife has seven sheaths. What is the total number of things? V těchto a podobných úlohách se využívá jednoduchých kombinatorických pravidel, která jsou tak zřejmá, že je autoři často nepovažovali za nutné explicitně uvádět. 2 Základní pojmy a pravidla V tomto odstavci jsou uvedeny některé definice, věty a pravidla, které se probírají na střední škole a v předmětu Kombinatorika. Pravidlo součtu říká, že pro počet prvků sjednocení množin A, B, jejichž průnik je prázdný, je roven součtu počtů prvků těchto množin; symbolicky zapisujeme takto: Toto pravidlo můžeme použít v kombinatorických výpočtech vždy, když lze množinu objektů rozdělit na disjunktní části (např. počítáme-li počet všech podmnožin čtyřprvkové množiny, rozdělíme si všechny podmnožiny na skupiny podle počtu prvků: prázdná množinu a jedno- až čtyřprvkové podmnožiny). Pravidlo součinu využívá vzorce pro počet prvků kartézského součinu množin, V kombinatorice lze toto pravidlo formulovat takto: pokud můžeme 1. prvek vybrat libovolně z množiny A a 2. prvek nezávisle na prvním z množiny B, potom všechny takové dvojice jsou prvky kartézského součinu. Toto pravidlo se dá pochopitelně rozšířit pro vybírání uspořádaných fc-tic prvků z množin po řadě A±,..., A\~. Faktoriál je funkce, která každému přirozenému číslu přiřadí součin všech čísel od 1 do n. Toto číslo značíme n\, čteme „n faktoriál" a zapisujeme takto: AU B\ = \A\ + \B A x B\ = \A\ ■ \B n! = 1 • 2 n Platí 1! = 1;2! = 2;3! = 6,4! = 24: Definitoricky klademe 0! = 1. ■;...; n\ = {n — 1)! • n. Kombinační číslo (^) je vlastně zkráceným zápisem zlomku k\(n-k)\ Odtud již přímo vyplývá následující tvrzení: 3 Permutace (bez opakování) z n prvků označují všechny možnosti sestavení n prvků do posloupnosti tak, aby se v posloupnosti každý z prvků vysktl právě jednou (někdy je označujeme také jao pořadí n-prvkové množiny). Jejich počet vypočteme takto: P{n) = n! Variace (bez opakování) k-prvkové z n (různých) prvků (tj. všechny možnosti výběru uspořádaných fc-tic z n-prvkové množiny) Jejich počet vypočteme takto: Til V(k, n) = n ■ (n — 1).....(n — k + 1) =--— [n — k)\ Kombinace (bez opakování) jsou fc-prvková seskupení z n druhů prvků (tj. všechny možnosti výběru neuspořádaných fc-tic z n-prvkové množiny). Jejich počet vypočteme takto: C(k,n) = Q = n-(n-l)...^(n-k + l) Permutace (s opakováním) z ri\ prvků 1. druhu, ..., n& prvků k-tého druhu (tj. všechny možnosti pro pořadí těchto prvků) Jejich počet vypočteme takto: pc(ni,..., nk) =-j-- Variace (s opakováním) jsou fc-prvková uspořádaná seskupení z prvků n druhů (tj. všechny možnosti výběru uspořádaných fc-tic z prvků n druhů). Jejich počet vypočteme takto: V0(k,n) = nk Kombinace (s opakováním) fc-prvkové z prvků n druhů (tj. všechny možnosti výběru neuspořádaných fc-tic z prvků n-druhů) Jejich počet vypočteme takto: 4 Kapitola 2 Rozklady konečných množin Opakování z algebry V dalším výkladu budeme používat následující pojmy z algebry: • Relace • Vlastnosti relace: - Reflexivní - Symetrická - Antisymetrická - Transitivní • Uspořádání (hasseovský diagram) • Ekvivalence na množině a rozklad množiny Určení počtu rozkladů na množině Rozklad množiny A na třídy: třídy jsou podmnožiny množiny A, každý prvek množiny A je obsažen v právě jedné této podmnožině Rozklady 4-prvkové množiny jsou tyto systémy podmnožin: {{1,2,3,4}} {{1,2},{3,4}} {{1},{4},{2,3}} {{1,2,3},{4}} {{1,3},{2,4}} {{2},{3},{1,4} } {{1,2,4},{3}} {{1,4},{2,3}} {{2},{4},{1,3} } {{1,3,4},{2 }} {{1},{2},{3,4}} {{3},{4},{1,2} } {{2,3,4},{1}} {{1},{3} {2,4}} {{1},{2},{3},{4}} 5 Bellova čísla Bellovo číslo Bn určuje počet všech rozkladů na n—prvkové množině. Rekurentní formule pro výpočet Bellových čísel: r-«=(ô)b«+('i)bi+-+C;)b» Přitom BQ = 1 Tedy: Bl = 1,B2 = 2, B3 = 5, B4 = 15, atd. Stirlingova čísla 2. druhu Stirlingova čísla S{n, k) udávají počet rozkladů n—prvkové množiny na k tříd. Je zřejmé, že S (n,n) = 1 = S(n,l). Rekurentní formule pro výpočet Stirlingových čísel pro 1 < k < n: S {n + 1, k) = S(n, k - 1) + k ■ S{n, k), Formuli lze odvodit úvahou: známe-li počet rozdělení n-prvkové množiny na k nebo {k — 1) tříd, rozdělení (n + l)-prvkové množiny může vzniknout přidáním nového prvku do existující třídy, nebo vytvořením samostatné třídy pro tento nový prvek. Cvičení Cvičení 2.1 Určete počet surjekcí tříprvkové množiny na dvouprvkovou. [6] Cvičení 2.2 Kolik existuje zobrazení čtyřprvkové množiny na tříprvkovou? [81] Cvičení 2.3 Ověřte pro nějaká k a n, že platí: (a) £2=1fc.fc! = (n+l)!-l; (b) ££=1(-l)TJ = (-im1) = Cvičení 2.4 Určete počet všech rozkladů množiny M = {a,b,c,d,e, f} na dvě třídy. [5(6,2)] Cvičení 2.5 Určete počet všech rozkladů množiny M = {a, b, c, d}. m 6 Cvičení 2.6 Určete počet všech rozkladů množiny M = {a, b, c, d, e, f} na tři třídy. [5(6,3)] Cvičení 2.7 Určete, kolik existuje (a) surjekcí dvouprvkové množiny na čtyřprvkovou; (b) surjekcí čtyřprvkové množiny na dvouprvkovou; (c) bijekcí mezi dvěma čtyřprvkovými množinami. [(a) neexistuje; (b) 14; (c) 24.] Cvičení 2.8 Dokážte, že počet všech rozkladů šestiprvkové množiny platí Cvičení 2.9 Dokažte, že pro Stirlingova čísla 2. druhu platí: (a) S(n,2) = T1'1 - 1; (b) S(n,n-1) = Q; (c) S(n + 1, m) = S(n, m — 1) + m • m); (d) 5(7i, 77í.) = EjfcCV) S{k,m - 1) (sčítame „přes všechna vhodná k11). 7 Kapitola 3 Princip inkluze a exkluze Příklad 3.1 Ve třídě je 30 žáků. Kroužek košíkové chce navštěvovat 18 z nich, kroužek atletiky 20 a ani jeden z těchto kroužků nechce navštěvovat 5 žáků. Kolik žáků chce navštěvovat oba kroužky, atletiky i košíkové? Řešení: Nechť A označuje množinu žáků, kteří chtějí chodit do atletiky a K množinu žáků, kteří chtějí chodit do košíkové. Víme, že \A\ = 20,\K\ = 18, \AUK\ = 25(= 30 - 5) Dále víme, že platí \AUK\ = \A\ + \K\ - \Ar\K\, oba kroužky, atletiky i košíkové, chce navštěvovat \AnK\ = \ A\ + \K\ - | A U K\ = 20 + 18 - 25 = 13 žáků. Protože \ A\ — \ AC\K\ =20 — 13, jen kroužek atletiky chce navštěvovat 7 žáků, analogicky \K\ — \AC\K\ = 18 — 13, tedy jen kroužek košíkové chce navštěvovat 5 žáků. Poznámka / zkouška: 7 + 5 +13+ 5 = 30 Příklad 3.2 Kolik je prvočísel < 100? Eratosthenovo síto: vyškrtáváme čísla složená, zbydou prvočísla Mezi čísly 2 až 100 je čísel dělitelných 2: 50 dělitelných 3: 33 dělitelných 5: 20 dělitelných 7: 14 dělitelných 2 i 3: 16 dělitelných 3 i 5: 6 dělitelných 2 i 5: 10 dělitelných 3 i 7: 4 dělitelných 2 i 7: 7 dělitelných 5 i 7: 2 dělitelných 2, 3 i 5: 3 dělitelných 2, 3 i 7: 2 dělitelných 3, 5 i 7: 0 dělitelných 2, 5 i 7: 1 dělitelných 2, 3, 5 i 7: 0 8 z toho je čísel složených: dělitelných 2: 50-1 dělitelných 3: 33-1 dělitelných 5: 20-1 dělitelných 7: 14-1 dělitelných 2 i 3: 16 dělitelných 3 i 5: 6 dělitelných 2 i 5: 10 dělitelných 3 i 7: 4 dělitelných 2 i 7: 7 dělitelných 5 i 7: 2 dělitelných 2, 3 i 5: 3 dělitelných 2, 3 i 7: 2 dělitelných 3, 5 i 7: 0 dělitelných 2, 5 i 7: 1 dělitelných 2, 3, 5 i 7: 0 Zřejmě tedy mezi prvními 100 čísly je prvočísel 99 -49 - 32 - 19 - 13+ 16+ 10+ 7 + 6 + 4 + 2- 3- 2-1-0 + 0 = 25 Můžeme postupovat i jinak, totiž tak, že spočítáme, kolik čísel od 2 do 100 není dělitelných ani 2, ani 3, ani 5, ani 7: 99- 50- 33- 20- 14+ 16+ 10+ 7 + 6 + 4 + 2- 3- 2-1-0 + 0 = 21, ale mezi těmito prvočísly chybí právě čtyři prvočísla: 2, 3, 5 a 7. Princip inkluze a exkluze pro 2 a 3 množiny Pro tyto případy se dá s výhodou využít Vennových diagramů. Formálně zapisujeme postup přo výpočtu takto: |MiUM2| = \Mi\ + |M2| - |Mi n M2| |MiUM2UM3| = \Mi\ + |M2| + |M3| - \MX U M2 U M3| = |Mi| + |M2| + |M3| - |Mi n M2| - |Mi n M3| - -|M2 n M3| + \Mi n M2 n M3| Analogicky postupujeme pro 4 a více množin: střídavě odečítáme průniky po dvou, přičítáme průniky po třech, odečítáme průniky po čtyřech, atd. Obecný princip inkluze a exkluze. Nechť M(a'ľ,..., a'n) obsahuje prvky množiny M, které nemají žádnou z vlastností a^,..., a'n a nechť M(aj) obsahuje prvky množiny M s vlastností aj pro i = 1,.. .n, dále M(a,i,a,j) obsahuje prvky množiny M s vlastnostmi aj, aj pro i, j = 1,... n, i ^ j atd. Pak platí: 9 n n \M(a[,...,a'n)\ = \M\-^2\M(ai)\+ ^ \M(ai,aj)\- i=l *ii=l n - Y, \M{ai,aj,ak)\ + --- + {-l)n\M{a1,...,an)\ i,j,k=l Speciální princip inkluze a exkluze. Pokud počet prvků s danými vlastnostmi nezávisí na konkrétni vlastnosti, ale pouze na jejich počtu, vypočteme počet prvků množiny M, které nemají žádnou z daných vlastností, takto: \M(a[,...,a'n)\ = |m|-q|m(1)| + q|m(2)|- -(g)l^(3)| + --- + (-l)nQ|M(n)| Pomocí speciálního principu inkluze a exkluze lze vyřešit např. problém roztržité sekretářky. Příklad 3.3 Sekretářka má čtyři různé dopisy a čtyři obálky nadepsané adresami čtyř různých adresátů. Kolika způsoby může vložit dopisy do obálek tak, aby žádný adresát nedostal svůj dopis? Řešení: Je zřejmé, že všech možností, jak vložit dopisy do obálek, je 4! = 24. Tyto možnosti jsou uvedené v následující tabulce, kde jednotlivé čtveřice čísel udávají po řadě, ve které obálce je vložen který dopis: číslo 3 n 2. místě např. značí, že ve 2. obálce je dopis pro adresáta číslo 3. 1234 2134 3124 4123 1243 2143 3142 4132 1324 2314 3214 4213 1342 2341 3241 4231 1423 2413 3412 4312 1432 2431 3421 4321 Zadání zřejmě vyhovuje 9 permutací (najděte je v tabulce). Pomocí principu inkluze a exkluze je spočítáme takto: 4! - q • 3! + q 2! - q 1! + q 0! = 24 - 24 + 12 - 4 + 1 = 9. Cvičení Cvičení 3.1 Máme pět obálek s pěti různými adresami (různých lidí) a pět různých dopisů pro tyto adresáty. Kolika způsoby můžeme vložit dopisy 10 do připravených obálek (do každé obálky jeden dopis) tak, aby ani jeden adresát nedostal svůj dopis? [44] Cvičení 3.2 V poušti kráčí karavana devíti velbloudů. Cesta trvá mnoho dní a všem velbloudům se protiví vidět před sebou stále téhož velblouda. Kolika způsoby lze velbloudy přemístit tak, aby před každým velbloudem šel jiný než doposud? [148329] Cvičení 3.3 * Určete počet permutací z n čísel 1,2,3,n takových, v nichž se nevyskytuje žádná z dvojic (1, 2), (2, 3),... {n — l,n). Cvičení 3.4 Na kolotoči sedí n dětí. Před druhou jízdou se rozhodly, že si přesednou tak, aby před každým z nich seděl někdo jiný než doposud. Kolika způsoby to mohou provést? Cvičení 3.5 Určete, kolik slov je možno sestavit z písmen slova (a) SEMESTR (b) PARAPLE (c) OUAGADOUGOU (d) AALKMOOST (e) ACAPULCO tak, aby žádná dvě stejná písmena nestála vedle sebe. Cvičení 3.6 Určete, kolik různých čísel vznikne záměnou pořadí číslic v čísle 56567849. Určete, v kolika z nich nebudou stát žádné dvě stejné číslice vedle sebe. Cvičení 3.7 Určete, kolik z permutací čísel 5, 6, 7, 8, 9 nemá na 1. místě číslo 5, na 2. místě číslo 6 atd. Cvičení 3.8 Určete, kolik z permutací písmen a, b, c, d, d, f nemá na 1. místě písmeno a, na 2. místě písmeno b atd. 11 Cvičení 3.9 Určete, kolik z permutací čísel 1, 3, 5, 7, 9 nemá na 1. místě číslo 1, na 2. místě číslo 3, na 3. místě číslo 5, na 4. místě číslo 7, ani na 5. místě číslo 9. Cvičení 3.10 Na taneční zábavu přišlo pět manželských párů. Určete, kolik tanců mohou odtancovat tak, že žádní manželé netančí spolu. (Tanec se začne tančit poté, co si každý z pěti pánů vyhovujícím způsobem vybere tanečnici. Pokud pán X již tančil s paní Y, nevadí to, jen nesmí spolu tančit manželé.) Cvičení 3.11 Určete, kolik různých čísel vznikne záměnou pořadí číslic čísla 678679123. Určete, v kolika z nich nebudou stát žádné dvě stejné číslice vedle sebe. Cvičení 3.12 Osm mužů si v šatně odloží klobouky. Kolika způsoby si je mohou nasadit na hlavu tak, aby žádný neměl na hlavě svůj klobouk? Cvičení 3.13 Určete počet přirozených čísel menších než p, která nejsou dělitelná číslem p, kde p je prvočíslo. (Číslo 1 nepočítáme mezi prvočísla.) Cvičení 3.14 Určete, kolik různých čísel vznikne záměnou pořadí číslic čísla 474568792. Určete, v kolika z nich nebudou stát žádné dvě stejné číslice vedle sebe. Cvičení 3.15 Určete, kolik z permutací písmen slova LAVICE nemá na 1. místě písmeno L, na 2. místě písmeno A, na 3. místě písmeno V, na 4. místě písmeno I, na 5. místě písmeno C, ani na 6. místě písmeno E. Cvičení 3.16 Kolika různých čísel lze zapsat pomocí číslic 1,2,3,4,5 tak, aby 1 nestála před 2, 2 před 3, 3 před 4 a 4 před 5? 12 Kapitola 4 Rozklady a kompozice přirozených čísel Kombinatorický pohled Otázka, kterou se budeme v této kapitole zabývat, zní: Kolika způsoby můžeme dané zapsat přirozené čísla na zadaný počet přirozených sčítanců? (Připomeňme, že nulu mezi přirozená čísla nepočítáme!) Odpověď závisí na tom, jaké rozklady bereme v úvahu: je-li dán počet sčítanců či zda je počet sčítanců libovolný a zda záleží či nezáleží na pořadí sčítanců. Je například zřejmé, že číslo n můžeme rozložit na n přirozených sčítanců jediným způsobem: n = 1 + lH-----h 1 y__• v n Rozklad čísla na sčítance Definice 4.1 Rozkladem čísla na sčítance rozumíme vyjádření přirozeného čísla jako součtu přirozených čísel. Na pořadí sčítanců nezáleží. (Jinými slovy, rozkladem čísla n na k sčítanců rozumíme každou neuspořádanou k-tici přirozených čísel, pro niž platí, že součet všech jejích čísel je n). Příklad 4.2 Uveďme například rozklady čísla 10: - všechny rozklady čísla 10 na 2 sčítance (5): 5+5 4+6 3+7 2+8 1+10 - všechny rozklady čísla 10 na 3 sčítance (8): 8+1+1 7+2+1 6+3+1 6+2+2 5+4+1 5+3+2 4+4+2 4+3+3; - všechny rozklady čísla 10 na 4 sčítance (9): 7+1+1+1 6+2+1+1 5+3+1+1 5+2+2+1 4+4+1+1 4+3+2+1 4+2+2+2 3+3+2+2 3+3+3+1; 13 - všechny rozklady čísla 10 na 5 sčítanců (7): 6+1+1+1+1 5+2+1+1+1 4+3+1+1+1 4+2+2+1+1 3+3+2+1+1 3+2+2+2+1 2+2+2+2+2; - všechny rozklady čísla 10 na 6 sčítanců (5): 2+2+2+2+1+1 3+2+2+1+1+1 3+3+1+1+1+1 4+2+1+1+1+1 5+1+1+1+1+1; - všechny rozklady čísla 10 na 7 sčítanců (3): 3+2+1+1+1+1+1 2+2+2+1+1+1+1 4+1+1+1+1+1+1; - všechny rozklady čísla 10 na 8 sčítanců (2): 2+2+1+1+1+1+1+1 3+1+1+1+1+1+1+1; - všechny rozklady čísla 10 na 9 sčítanců (1): 2+1+1+1+1+1+1+1+1; - všechny rozklady čísla 10 na 10 sčítanců (1): 1 + 1+1+1+1+1+1+1+1+1; - všechny rozklady čísla 10 na 11 (a více) sčítanců: neexistuje. V následujícím odvodíme počet rozkladů čísla n na k sčítanců a na libovolný počet sčítanců. Počet rozkladů čísla n na k sčítanců budeme označovat p(n, k). Nejprve uvedeme příklad. Příklad 4.3 Kolik existuje rozkladů čísla 11 na 4 sčítance? Předpokládejme, že známe počet rozkladů čísel 1 až 10 na 1 až 4 sčítance (můžeme jistě odvodit stejným způsobem jako všechny rozklady čísla 10, viz výše). Rozklady čísla 11 můžeme odvodit z rozkladů čísla 10 a menších tak,že rozložíme: - číslo 10 na 3 sčítance, čtvrtý sčítanec je 1; - číslo 10 na 4 sčítance, k jednomu ze sčítanců přičteme 1. V prvním případě je situace jednoznačná: z rozkladů čísla 10 na 3 sčítance Ve druhém případě však z rozkladů čísla 10 dostáváme toto (sčítance zapisujeme od největšího po nejmenší): dostáváme následující rozklady 11 na 4 sčítance: 10 = 8+1+1 11 8+1+1+1 7+2+1+1 6+3+1+1 6+2+2+1 5+4+1+1 5+3+2+1 4+4+2+1 4+3+3+1 = 7+2+1 = 6+3+1 = 6+2+2 = 5+4+1 = 5+3+2 = 4+4+2 = 4+3+3 14 = 7+1+1+1 - » 11 =8+1+1+1 = 7+2+1+1 = 6+2+1+1 - » =7+2+1+1 = 6+3+1+1 = 5+3+1+1 - » =6+3+1+1 =5+4+1+1 =5+3+2+1 =5+3+1+2 = 5+2+2+1 - * =6+2+2+1 =5+3+2+1 =5+2+3+1 =5+2+2+2 = 4+4+1+1 - » =5+4+1+1 =4+5+1+1 =5+4+1+1 =4+5+1+1 =4+4+2+1 =4+4+1+2 = 4+3+2+1 - » =5+3+2+1 =4+4+2+1 =4+3+3+1 =4+3+2+2 = 4+2+2+2 - » =5+2+2+2 =4+3+2+2 =4+2+3+2 =4+2+2+3 = 3+3+2+2 - * =4+3+2+2 =3+4+2+2 =3+3+3+2 =3+3+2+3 = 3+3+3+1 - » =4+3+3+1 =3+4+3+1 =3+3+4+1 =3+3+3+2 Je vidět, že některé z rozkladů se opakují. Bude tedy vhodné podívat se, z čeho vznikly jednotlivé rozklady — totiž z rozkladů čísel menších než 10 na méně než 4 sčítance. Nechť n = xi + x2 H-----h xk je rozklad čísla n na k sčítanců, v němž jsou sčítance seřazeny dle velikosti (x\ je nej větší). Odečteme-li od každého sčítance 1, dostáváme n - k = (xi - 1) + (x2 - 1) H-----h (xk - 1), což je rozklad čísla (n — k) na nejvýše k sčítanců. V našem případě tedy počet rozkladů čísla 11 vypočteme rekurentně takto: p(ll,4) = p(7,4)+p(7,3)+p(7,2)+p(7,l) = p(3,3)+p(3,2)+p(3,l)+4 + 3 + l = 1 + 1 + 1 + 8 = 11 Všech 11 rozkladů čísla 11 na 4 sčítance je uvedeno v následující tabulce: 11 = 8+1+1+1 = 7+2+1+1 = 6+3+1+1 = 6+2+2+1 = 5+4+1+1 = 5+3+2+1 = 5+2+2+2 = 4+4+2+1 = 4+3+3+1 = 4+3+2+2 = 3+3+3+2 15 Věta 4.4 Počet všech rozkladů čísla n na k sčítanců vypočteme podle rekurentního vzorce k p(n, k) = ^2p(n - k,i), i=i přičemž zřejmě p(n, 1) = 1 = p(n, n). Věta 4.5 Počet všech rozkladů čísla n na libovolně mnoho sčítanců je roven n PÍ.n) = ^2v{n,i). i=i Kompozice čísla ze sčítanců Zatímco u rozkladu nezáleží na pořadí sčítanců, u kompozice ano. Například rozkladů čísla 4 je 5: 4 = 4 = 2 + 2 = 3+1=2 + 1 + 1 = 1 + 1 + 1 + 1; přitom kompozic čísla 4 (z libovolného počtu sčítanců) je 8: 4=4=2+2=3+1=1+3= =2+1+1=1+2+1=1+1+2=1+1+1+1 Definice 4.6 Kompozicí čísla nz k sčítanců rozumíme každou uspořádanou fc-tici přirozených čísel, pro niž platí, že součet všech jejích čísel je n. Věta 4.7 Pro libovolná přirozená čísla n a k platí, že počet kompozic čísla n z (právě) k čísel je roven počtu kombinací Cn_i5fc_i Zajímavosti • Ferrersovy diagramy • Adjungovaný rozklad • Uspořádání rozkladů (znázornění pomocí hasseovského diagramu) Cvičení Cvičení 4.1 Určete počet rozkladů (a) rozkladů čísla 14 na 4 sčítance; (b) kompozic čísla 14 ze 4 sčítanců; (c) rozkladů čísla 16 na 4 sčítance; (c) kompozic čísla 16 ze 4 sčítanců. 16 Cvičení 4.2 Definujte (nějakou) relaci uspořádání na množině všech rozkladů čísla 4. Nakreslete odpovídající hasseovský diagram. Cvičení 4.3 Rozhodněte, zda platí následující tvrzení: počet všech rozkladů n na lichý počet sčítanců roven počtu rozkladů čísla n na navzájem různé liché sčítance. [Neplatí, stačí najít protipříklad.] Cvičení 4.4 Dokažte, že počet všech rozkladů n (na libovolné přirozené sčítance) je roven počtu rozkladů čísla 2n na právě n sčítanců. Cvičení 4.5 Určete počet všech rozkladů čísla 8. 17 Kapitola 5 Rozdělování do přihrádek V této kapitole se budeme zabývat příklady, v jejichž zadání dokážeme rozpoznat rozdělování n předmětů do k přihrádek. Přihrádky i předměty mohou být navzájem stejné nebo navzájem různé a my si odvodíme vzorce pro výpočet všech čtyř případů vzniklých kombinováním rozlišitelných a nerozlišitelných předmětů a rozlišitelných a nerozlišitelných přihrádek: rozlišitelné přihrádky nerozlišitelné přihrádky rozlišitelné předměty ? ? nerozlišitelné předměty ? ? V této kapitole nahradíme postupně otazníky na všech čtyřech místech tabulky příslušnými vztahy. Nejprve uvedeme větu, jejíž důkaz je zřejmý, ale která se dá elegantně použít: Věta 5.1 (Dirichletův princip) Při každém rozdělení n předmětů do k přihrádek, kde k < n, existuje alespoň jedna přihrádka obsahující alespoň dva předměty. Příklad 5.2 Na čtvercové mřížce zvolíme libovolně 5 bodů. Dokažte, že mezi těmito body existují dva body takové, že na úsečce, která je spojuje, leží alespoň jeden mřížový bod (tj. průsečík přímek, které vytvářejí danou mřížku). Jednotlivá políčka výše uvedené tabulky se dají doplnit použitím vztahů, které již známe: vzorců pro výpočet počtu variací a kombinací s opakováním, Stirlingových čísel 2. druhu a počtu rozkladů čísla na sčítance. Odvodíme 18 také, kolik je požadovaných rozdělení takových, při nichž žádná přihrádka nezůstane prázdná; k tomu budeme v některých případech potřebovat princip inkluze a ezkluze. Rozdělování různých předmětů do různých přihrádek Věta 5.3 Nechť n, k jsou libovolná přirozená čísla. Pak počet rozdělení n rozlišitelných předmětů rozdělit do k rozlišitelných přihrádek vypočteme podle vzorce pro variace s opakováním, tj. Důkaz 5.4 Při rozdělování rozlišitelných prvků do rozlišitelných přihrádek máme pro každý z n prvků k možností umístění do přihrádky. Použitím pravidla součinu dostáváme dokazovaný vztah. Rozdělování různých předmětů do různých přihrádek tak, aby žádná přihrádka nezůstala prázdná Věta 5.5 Nechť n, k jsou libovolná přirozená čísla, n > k. Pak lze n rozlišitelných předmětů do k rozlišitelných přihrádek tak, aby žádná přihrádka nezůstala prázdná, rozdělit právě způsoby. Důkaz 5.6 Použijeme principu inkluze a exkluze. Rozdělování stejných předmětů do různých přihrádek Věta 5.7 Nechť n, k jsou libovolná přirozená čísla,. Pak počet rozdělení n nerozlišitelných předmětů do k rozlišitelných přihrádek vypočteme podle vzorce pro kombinace s opakováním, tj. Důkaz 5.8 Záleží nám pouze na počtu prvků v každé přihrádce, neboi jsou všechny stejné. Můžeme si to představit např. tak, že prvky, které rozdělujeme, jsou např. míčky a mezi ně pokládáme všemi možnými způsoby kostky. Před první kostkou jsou prvky z první přihrádky, mezi první a druhou kostkou jsou prvky ze druhé přihrádky, atd. Je zřejmé, že kostek potřebujeme jen {k — 1), neboi za k—tou kostkou už stejně žádné míčky nemohou být. kn - 1 n 19 Počet všech možností je tedy roven počtu všech způsobů, jak seřadit n míčků a {k — 1) kostek; tento počet zřejmé vypočteme podle vzorce pro permutace s opakováním z prvků dvou druhuů (míčků a kostek); odtud známým způsobem dostaneme výše uvedené kombinační číslo: (n + k—l)\ fn + k — l\ fn + k— 1 nl(k — 1)1 \ k — 1 J \ n Rozdělování stejných předmětů do různých přihrádek tak, aby žádná přihrádka nezůstala prázdná Věta 5.9 Nechť n, k jsou libovolná přirozená čísla,. Počet rozdělení n nerozlišitelných předmětů do k rozlišitelných přihrádek rozdělit tak, aby v každé přihrádce bylo aspoň r předmětů, vypočteme takto: n — kr + k — 1 k - 1 Pro r = 1 je tento počet zřejmě n — 1 k - 1 Důkaz 5.10 Uvažujeme takto: nejprve dáme do každé přihrádky požadovaný minimální počet předmětů a potom rozdělíme zbývající stejným způsobem jako v předchozím případě. Rozdělování různých předmětů do stejných přihrádek Věta 5.11 Nechť n, k jsou libovolná přirozená čísla. Pak lze n rozlišitelných předmětů do k nerozlišitelných přihrádek rozdělit právě S(n, 1) + S(n, 2) + • • • + S(n, k) způsoby. Počet rozdělení n rozlišitelných předmětů do k nerozlišitelných přihrádek je pak zřejmě roven S(n, k). Důkaz 5.12 S(n, k) jsou Stirlingova čísla 2. druhu (viz dříve), která udávají počet rozkladů n-prvkové množiny na k prvků. Je zřejmé, že právě toto číslo odpovídá součtu počtů rozdělení n rozlišitelných předmětů do jedné až k nerozlišitelných přihrádek. 20 Rozdělování stejných předmětů do stejných přihrádek Věta 5.13 Nechť n, k jsou libovolná přirozená čísla. Pak lze n nerozlišitelných předmětů do k nerozlišitelných přihrádek rozdělit právě p(n, 1) + p(n, 2) H-----h p(n, k) způsoby; chceme-li, aby všechny přihrádky byly neprázdné, je tento počet p(n, k). Důkaz 5.14 Číslo p(n,k) označuje počet rozkladů čísla n na k sčítanců, kdy na pořadí sčítanců nezáleží, je zřejmé, že toto číslo odpovídá hledanému počtu. Důkaz 5.15 S(n, k) jsou Stirlingova čísla 2. druhu (viz dříve), která udávají počet rozkladů n-prvkové množiny na k prvků. Je zřejmé, že právě toto číslo odpovídá počtu rozdělení n rozlišitelných předmětů do k nerozlišitelných přihrádek. Cvičení Cvičení 5.1 Dokažte, že když v obdélníku 5 cm x 3 cm vybereme libovolných 25 bodů, najdeme mezi nimi dva takové, jejichž vzdálenost je menší než 1, 5 cm. [Návod: Využijte toho, že úhlopříčka ve čtverci o hraně délky 1 má velikost V2, což je méně než 1,5.] Cvičení 5.2 Dokažte, že mezi sedmi různými přirozenými čísly jsou alespoň dvě taková, jejichž součet nebo rozdíl je dělitelný 10. [Návod: Rozdělte čísla do tříd podle dělitelnosti 10.] Cvičení 5.3 Na hřišti bylo 23 chlapců z jedné pětitřídní základní školy bez paralelních tříd. Všichni si během odpoledne zahráli košíkovou, vybíjenou, nebo obojí. Košíkovou hrálo 13 chlapců, vybíjenou 16. Ukažte, že mezi chlapci, kteří hráli košíkovou i vybíjenou, byli alespoň 2 spolužáci. Cvičení 5.4 Kolika způsoby lze rozdělit jablko, hrušku, banán, pomeranč a švestku třem dětem? Ko Cvičení 5.5 Kolika způsoby lze rozdělit 17 švestek mezi 3 děti tak, aby každé dítě dostalo alespoň čtyři švestky? 21 Cvičení 5.6 Kolika způsoby lze rozdělit 3 korunové a 10 dvoukorunových mincí do 4 různých peněženek? Cvičení 5.7 Kolika způsoby lze rozdělit 3 stejné bílé a 3 stejné černé koule do 6 různobarevných sáčků, pokud (a) některý sáček může zůstat prázdný; (b) žádný sáček nesmí zůstat prázdný? (Poznámka: Všech 6 koulí se vejde do jednoho sáčku.) Cvičení 5.8 Kolika způsoby lze rozdělit 15 jablek a 9 hrušek třem dětem? Kolik takových rozdělení je „spravedlivých" (tj. každé dítě dostane stejný počet kusů jablek a stejný počet kusů hrušek)? Cvičení 5.9 Kolika způsoby lze rozdělit 5 různých knih mezi 4 děti tak, aby každé dítě dostalo alespoň jednu knihu? Cvičení 5.10 Kolika způsoby lze rozdělit 7 různých fotografií do 4 různých obálek? Cvičení 5.11 Kolika způsoby lze rozdělit jablko, hrušku, banán, pomeranč, mandarinku a švestku dvěma dětem? Kolik takových rozdělení je „spravedlivých" (tj. každé z dětí dostane 3 kusy ovoce)? Cvičení 5.12 Kolika způsoby lze rozdělit 6 různých knih mezi 5 dětí tak, aby každé dítě dostalo alespoň jednu knihu? Cvičení 5.13 Kolika způsoby lze rozdělit 3 stejné bílé a 3 stejné černé koule do 6 různobarevných sáčků, pokud (a) některý sáček může zůstat prázdný; (b) žádný sáček nesmí zůstat prázdný? (Poznámka: Všech 6 koulí se vejde do jednoho sáčku.) Cvičení 5.14 Ukažte, že mezi čtyřmi různými přirozenými čísly existují vždy čísla x, y taková, že x + y nebo x — y je dělitelné 5. 22 Kapitola 6 Rekurentní formule Rekurentní formule, s nimiž jsme se již setkali • Faktoriál: (n + 1)! = (n + 1) • nl • Bellova čísla pro výpočet počtu rozkladů konečné množiny: Bn+i=y2 {i,)b° = 1 • Stirlingova čísla 1. druhu, neboli koeficienty u xk v polynomu {x)n = x ■ {x — 1) • {x — 2).....{x — n + 1): s{n + l,k) = s(n, k — 1) — n ■ s(n, k); s(n, 0) = 0, S(n, n) = 1 • Stirlingova čísla 2. druhu pro určení počtu rozkladů n-prvkové množiny na k tříd (1 < k < n): S (n + l,k) = S(n, k - 1) + k • S(n, k);S(n, n) = S(n, 1) = 1 Čím se uvedené formule liší? • Faktoriál: pro výpočet dalšího stačí znát předchozí člen • Stirlingova čísla 1. i 2. druhu: potřebujeme znát dva předchozí členy • Bellova čísla: pro výpočet dalšího člene potřebujeme znát všechny Dennice 6.1 [Rád rekurentní formule] Číslo k nazveme řádem formule f (n), pokud lze pro kažé n G N určit f{n + k) pomocí f (n), f(n+l),... f{n + k — l) a A: je nejmenší přirozené číslo s touto vlastností. Příklad 6.2 • rekurentní formule 3. řádu: f {n + 3) = f {n + 2) — 5 f (n) • rekurentní formule 1. řádu: f (n + 1) = log f (n) 23 Řešení lineárních rekurentních formulí s konstatními koeficienty Nyní si ukážeme řešení rekurentních formulí pro jednu speciální třídu rekurentních formulí, pro niž je řešení relativně jednoduché. Definice 6.3 Lineární rekurentní formule s konstantními koeficienty je rekurentní formule tvaru f(n + k)=a1-f(n + k-l)+a2-f(n + k-2) + - + ak- f(n) Poznámka 6.4 Řešením rekurentní formule je posloupnost. Věta 6.5 Jsou-li nějaké posloupnosti řešením dané rekurentní formule, pak je jejícm řešením také jejich libovolná lineární kombinace. (Všimněte si, že se nabízí analogie s lineární algebrou.) Příklad 6.6 Najděte vzorec pro výpočet n—tého člene posloupnosti v závislosti pouze na n, znátel-li rekurentní vzorec an+2 = 7an+i — 12an a víte, že ai = 7, (i2 = 25 Charakteristická rovnice je (zde pouze intuitivně): A2 - 7A + 12 = 0, její kořeny Ai = 3, A2 = 4. Obecné řešení je tvaru an = ciAn + C2A2 • Dosazením n=l a n= 2 dostáváme soustavu 7 = ci • 3 + c2 • 4 12 = ci • 32 + c2 • 42 a jejím vyřešením a dosazením vypočtených hodnot c\ = 1 a c2 = do obecného vzorce pro n-tý člen dostáváme an = 3n + 4n. 24 Cvičení Cvičení 6.1 Určete vzorec pro výpočet n-tého členu posloupnosti, která je dána rekurentním vztahem an+2 = an+i + 6an, přičemž a± = 1 a 02 = 13. Cvičení 6.2 Určete vzorec pro výpočet n-tého členu posloupnosti, která je dána rekurentním vztahem an+2 = 7an+i — 12an, přičemž a± = 7 a (12 = 25. Cvičení 6.3 Určete vzorec pro výpočet n-tého členu posloupnosti, která je dána rekurentním vztahem an+2 = 7an+i — 10an, přičemž a± = 1 a 02 = 17. Cvičení 6.4 Určete vzorec pro výpočet n-tého členu posloupnosti, která je dána rekurentním vztahem an+2 = 7an+i — 10an, přičemž a± = 3 a 02 = 21. Cvičení 6.5 Určete vzorec pro výpočet n-tého členu posloupnosti, která je dána rekurentním vztahem an+2 = 3an+i — 2an, přičemž a± = 1 a 02 = 3. Cvičení 6.6 Určete vzorec pro výpočet n-tého členu posloupnosti, která je dána rekurentním vztahem an+2 = «n+i + 6an, přičemž a± = 1 a 02 = 13. Cvičení 6.7 Určete vzorec pro výpočet n-tého členu posloupnosti dané rekurentně: an+3 = 9an+2 + 26an+i — 24an, přičemž ai = 1,02 = —3a a3 = -29. Cvičení 6.8 Určete vzorec pro výpočet n-tého členu posloupnosti, která je dána rekurentním vztahem an+2 = an+i + 6an, přičemž a± = 1 a 02 = 13. 25 Kapitola 7 Magické a latinské čtverce Magické čtverce Definice 7.1 (jen naše) Polomagickým čtvercem označujeme čtvercové schéma (tabulku) vytvořené z navzájem různých čísel tak, že součet čísel ve všech řádcích a sloupcích je stejný (na úhlopříčkách mohou být součty jiné). Definice 7.2 (jen naše) Magickým čtvercem označujeme polomagický čtverec takový, v němž jsou součty ve všech řádcích a sloupcích i v úhlopříčkách stejné. Grupy a tělesa — stručné opakování • grupoid: množina uzavřená vzhledem k operaci • asociativní zákon • pologrupa: platí asociativní zákon • neutrální prvek: a*e = a = e*a, a + e = a = e + a • komutativní zákon • grupa: pologrupa, neutrální prvek, opačné/inverzní prvky • množiny se dvěma operacemi: aditivní, multiplikativní • okruh: (R, +, •) — (R, +) je komutativní grupa, (R, •) je pologrupa, platí distributivní zákony • distributivní zákony: a ■ (b + c) = a ■ b + a ■ c, (b + c)-a = b- a + c- a • těleso: (T, +, •) — (T, +) i (T, •) jsou komutativní grupy, platí distributivní zákony 26 Příklady okruhů a těles • (N, + , •) - není okruh • (Z, +, •) - je okruh, není těleso • (Qi +1 •) - Je těleso • (R, +, •) - je těleso Konečné okruhy a tělesa • zbytkové třídy modulo m • prvočíselné modulo • modulo je číslo složené Latinské čtverce Definice 7.3 emphLatinský čtverec je čtvercové schéma n x n čísel mezi 1 a n takové, že každý řádek a každý sloupec obsahuje všechna čísla od 1 do ?i. (Tedy čísla v libovolném řádku/sloupci jsou navzájem různá.) Příklad 7.4 Latinský čtverec je například následující schéma: 12 3 4 2 14 3 3 4 12 4 3 2 1 27 Kapitola 8 Konečné roviny Konečné afinní roviny Definice 8.1 (Konečná afinní rovina) Nechť A je neprázdná množina a 1Z C V (A) a nechť platí: (AI) Pro každé x,y G A, x 7^ y, existuje právě jedna podmnožina P 6 K raková, že x, y C P. (A2) Pro každou množinu P G 1Z a pro každý prvek x G A, x ^ P existuje právě jedna množina Q G 1Z taková, žexeQaPflQ = í). (A3) Existují tři navzájem různé prvky x, y, z G A takové, že x, y, z není podmnožinou žádné množiny P G 1Z. Pak dvojice (A, 1Z) se nazývá konečná afinní rovina. Prvky množiny A se nazývají body a prvky množiny 1Z 'přímky této roviny. Položky (AI), (A2), (A3) z předchozí definice nazýváme axiomy. Tyto axiomy lze pro geometrickou představu konečné afinní roviny přeformulovat takto: (AI) Každými dvěma body lze vést právě jednu přímku. (A2) Každým bodem lze s danou přímkou vést právě jednu rovnoběžku. (A3) Existují tři body, které neleží na jedné přímce. Podobně budeme nazývat dvě přímky konečné afinní roviny rovnoběžkami, pokud dané dvě přímky (pomnožiny ze systému 1Z) nemají žádný průnik (tj. jsou disjunktní). Směrem v afinní rovině nazveme systém všech rovnoběžek s danou přímkou (podmnožin ze systému 1Z, které s danou podmnožinou nemají žádný průnik). Podobným způsobem lze přenést i v geometrii používané označení. I pro konečné afinní roviny platí, že rovnoběžnost přímek je tranzitivní relace: 28 Věta 8.2 Nechť P, Q, R jsou přímky v konečné afinní rovině. Nechť přímky P a Q jsou rovnoběžné a současně přímky Q a R jsou rovnoběžné. Pak jsou rovnoběžné i přímky P a R. Dále platí následující věta: Věta 8.3 V konečné afinné rovině mají všechny přímky stejný počet bodů. Důkaz viz např. [2, str. 87-88]. Vzhledem k tomu, že všechny přímky dané konečné afinní roviny mají stejný počet bodů, má smysl pojmenovat tuto charakteristiku konečné afinní roviny: Definice 8.4 (Rád konečné afinní roviny) Řádem konečné afinní roviny nazveme počet bodů ležících na přímkách v této rovině. Rád konečné afinní roviny určuje počet jejích bodů a přímek: Věta 8.5 Konečná afinní rovina řádu n má n2 bodů a n2 + n přímek, na každé přímce leží n bodů a každým bodem prochází n + 1 přímek. Všechny přímky lze rozdělit do n + 1 směrů, z nichž každý obsahuje n rovnoběžek. Příklad 8.6 Konečná afinní rovina 3. řádu má 9 = 32 bodů a 12 = 32 + 3 přímek. Přímky lze rozdělit do čtyř různých směrů a dle předchozí věty obsahuje tato rovina tři přímky každého z těchto směrů. Očíslujme body čísly 1 až 9. Pak dostáváme následujících dvanáct přímek čtyř směrů: 1. směr {1,2,3} {4,5,6} {7,8,9} 2. směr {1,4,7} {2,5,8} {3,6,9} 3. směr {1,5,9} {2,6,7} {3,4,8} 4. směr {1,6,8} {2,4,9} {3,5,7} Konečné afinní roviny a latinské čtverce Zkusme ve čtverci 1 2 3 4 5 6 7 8 9 nahradit čísly 1,2, 3 čísla bodů na přímkách 3. a 4. směru, a to takto: body přímky obsahující bod 1 nahradíme číslem 1, atd., čímž dostáváme následující čtverce: 12 3 12 3 3 12 a 2 3 1 2 3 1 3 12 Tyto čtverce jsou latinské a jsou navzájem ortogonální, jak je vidět z následujícího schématu: 29 11 22 33 32 13 21 23 31 12 Postup, kterým jsme přímky převedli na latinské čtverce, obrátit. Obráceným postupem lze ze 2 ortogonálních latinských čtverců řádu 3 získat afinní rovinu řádu 3, obecně pak z (n — 1) ortogonálních latinských čtverců řádu n získat afinní rovinu řádu n. Platí věta: Věta 8.7 (Souvislost existence afinní roviny a ortogonálních latinských čtverců) Konečná afinní rovina řádu n > 3 existuje právě tehdy, když existuje (n — 1) latinských čtverců řádu n, z nichž každé dva jsou ortogonální. Vraťme se k existenci ortogonálních latinských čtverců. Víme, že neexistují ortogonální latinské čtverce řádu 2 a ve výše uvedeném příkladu jsme našli dva ortogonální čtverce řádu 3. Existují také tři navzájem ortogonální latinské čtverce řádu 4: 1234 1234 1234 2143 3412 4321 3412 ' 4321 ' 2143 4321 2143 3412 Pro další případy odkážeme na platnost následující věty (zde bez důkazu): Věta 8.8 Pro každé přirozené n > 2 kromě n = 6 existují ortogonální latinské čtverce řádu n. Případ n=6 studoval Euler, více viz [2, str. 85]. Konečné projektivní roviny Definice 8.9 (Konečná projektivní rovina) Nechť A je neprázdná množina a 1Z C V (A) a nechť platí: (Pl) Pro každé x,y £ A, x ^ y, existuje právě jedna podmnožina P 6 K taková, že x, y C P. (P2) Každé dvě různé přímky se protínají v jediném bodě. (P3) Existují čtyři navzájem různé prvky, z nichž žádné tři neleží na téže přímce. Pak dvojice (A, 1Z) se nazývá konečná projektivní rovina. Prvky množiny A se nazývají body a prvky množiny 1Z přímky této roviny. 30 Literatura [1] Biggs, Norman L., „The Roots of Combinatorics", História Mathematica 6 (1979): 109-136. [2] Fuchs, Eduard, Diskrétní matematika pro učitele (skriptum), Brno: Přírodovědecká fakulta Masarykovy univerzity, 2001. [3] Nešetřil, Jaroslav a Matoušek, Jiří, Kapitoly z diskrétní matematiky, MATFYZPRESS 1996. [4] Jiří Herman, Radan Kučera, Jaromír Simša, Metody řešení matematických úloh II. (skriptum), Masarykova univerzita v Brně — Fakulta přírodovědecká, Brno, 1991. 31