Diskrétní matematika 1 (Kombinatorika) Helena Durnová 9. prosince 2011 Obsah 1 Úvod do diskrétni matematiky 3 1.1 Staré kombinatorické úlohy................... 3 1.2 Základní pojmy a pravidla.................... 3 2 Opakování algebry 6 3 Rozklady konečných množin 7 3.1 Určení počtu rozkladů na množině............... 7 3.2 Bellova čísla............................ 7 4 Princip inkluze a exkluze 8 4.1 Princip inkluze a exkluze pro 2 a 3 množiny.......... 9 4.2 Cvičení .............................. 10 5 Rozklady a kompozice přirozených čísel 11 5.1 Kombinatorický pohled ..................... 11 5.2 Rozklad čísla na sčítance..................... 11 5.3 Kompozice čísla ze sčítanců................... 14 6 Rozdělování do přihrádek 15 6.1 Cvičení .............................. 17 7 Rekurentní formule 18 7.1 Řešení lineárních rekurentních formulí s konstatními koeficienty 19 8 Magické a latinské čtverce 20 8.1 Magické čtverce.......................... 20 8.2 Grupy a tělesa — stručné opakování.............. 20 8.3 Konečné okruhy a tělesa..................... 21 8.4 Latinské čtverce ......................... 21 9 Konečné roviny 22 9.1 Konečné afinní roviny ...................... 22 9.2 Konečné afinní roviny a latinské čtverce............ 23 1 9.3 Konečné projektivní roviny................... 24 10 Zajímavé úlohy 25 10.1 Úloha o frontě u pokladny.................... 25 2 Kapitola 1 Uvod do diskrétni matematiky Toto je pracovní verze studijního textu pro předmět Diskrétní matematika 1 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 1.1 Staré kombinatorické úlohy Ve Rhindově papyru (mateamtika ve starém Egyptě) Ve Fibonacciho Liber abaci 1.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. Látka bude procvičena na příkladech 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: \AUB\ = \A\ + \B\ Toto pravidlo používáme v kombinatorických výpočtech vždy, když dokážeme 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 se všechny podmnožiny podle počtu prvků na prázdnou podmnožinu a jedno- až čtyřprvkové podmnožiny). 3 Pravidlo součinu nabízí využití pravidla o počtu prvků kartézského součinu \AxB\ = \ A\---\B\ v kombinatorice: 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: n! = 1 • 2.....n Platí 1! = 1;2! = 2; 3! = 6,4! = 24;... ;n! = (n - 1)! • n. Definitoricky klademe 0! = 1. Kombinační číslo (^) je vlastně zkráceným zápisem zlomku n! k\(n-k)\ Permutace (bez opakování) z n prvků (tj. všechny možnosti pro 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: V(k, n) = n ■ (n — 1).....(n — k + 1) (n - k)\ Kombinace (bez opakování) fc-prvkové z n (různých) 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: k kl 4 Permutace (s opakováním) z ri\ prvků 1. druhu, ..., nk 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) (ri!.....nk)\ Variace (s opakováním) k-prvkové 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: 5 Kapitola 2 Opakování algebry Pro další výklad je doporučeno si zopakovat 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 6 Kapitola 3 Rozklady konečných množin 3.1 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}} 3.2 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: Přitom BQ = 1 Tedy: Bx = 1,B2 = 2, B3 =5,B4 = 15, atd. 7 Kapitola 4 Princip inkluze a exkluze Příklad 4.1 Ve třídě je 30 žáků. Z toho 18 chce navštěvovat kroužek košíkové, 20 kroužek atletiky, 5 žáků nechce navštěvovat ani jeden z krouž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í navštěvovat kroužek atletiky a K množinu žáků, kteří chtějí navštěvovat kroužek 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 \A n K\ \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 4.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 složených -1) -1) dělitelných 2: 50 (-1) dělitelných 3: 33 dělitelných 5: 20 (-1) 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 (tj. prvočísla neodečítáme). 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 Trošku jinak: počítáme, kolik čísel od 2 do 100 není dělitelné ani 2, ani 3, ani 5, ani 7, tj. 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. 4.1 Princip inkluze a exkluze pro 2 a 3 množiny Pro tyto případy se dá s výhodou využít Vennových diagramů. |MiUM2| = \Mi\ + |M2| - |Mi n M2| |MiUM2UM3| = \Mi\ + |M2| + |M3| - |Mi U M2 U M3| = |Mi| + |M2| + |M3| - -\Mi n M2| - |Mi n M3| - |M2 n M3| + |MX n M2 n M3| Obecný princip inkluze a exkluze. Nechť M{a'1,..., a'n) označuje množinu prvků množiny M, které nemají žádnou vlastnost M(a,i) označuje množinu prvků množiny M s vlastností en pro i = 1,... n, M(aj, a,j) označuje množinu prvků množiny M s vlastnostmi aj, aj pro i, j = 1,... n, i 7^ j a dále analogicky. Pak platí: n n IMK^.X)) = \M\-^2\M(ai)\+ \M(auaj)\- 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étní vlastnosti, ale pouze na jejich počtu, vypočteme počet prvků množiny M, které nemají žádnou z vlastností takto: 9 |MK,...X)I = |M|-Q|M(1)| + Q|M(2)|- -(g)l^(3)| + --- + (-l)nQ|M(n)| 4.2 Cvičení Cvičení 4.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 ně. Kolika způsoby můžeme vložit dopisy 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í 4.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í 4.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í 4.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í 4.5 Určete počet surjekcí (zobrazení "na") množiny A na množinu B, je-li \ A\ = 5,\B\ = 4. 10 Kapitola 5 Rozklady a kompozice přirozených čísel 5.1 Kombinatorický pohled Otázka: Kolik existuje rozkladů přirozeného čísla na přirozené sčítance (ne nulu)? 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 + H-----h 1 y__• v n 5.2 Rozklad čísla na sčítance Definice 5.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 5.2 Uveďme například rozklady čísla 10: • všechny rozklady čísla 10 na 2 sčítance (5): 10 = 5+5 = 4+6 = 3+7 = 2+8 = 1+9; • všechny rozklady čísla 10 na 3 sčítance (8): 10 = 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): 10 = 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; 11 • všechny rozklady čísla 10 na 5 sčítanců (7): 10 = 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): 10 = 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): 10 = 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): 10 = 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): 10 = 2+1+1+1+1+1+1+1+1; • všechny rozklady čísla 10 na 10 sčítanců (1): 10 = 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 5.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 dostáváme následující rozklady 11 na 4 sčítance: = 8+1+1 = > 11 = 8+1+1+1 = 7+2+1 = 7+2+1+1 = 6+3+1 = 6+3+1+1 = 6+2+2 = 6+2+2+1 = 5+4+1 = 5+4+1+1 = 5+3+2 = 5+3+2+1 = 4+4+2 = 4+4+2+1 = 4+3+3 = 4+3+3+1 12 Ve druhém případě však z rozkladů čísla 10 dostáváme toto (sčít, dsujeme od největšího po nejmenší): 10 = 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+i+i =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+l+l =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 13 Věta 5.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 5.5 Počet všech rozkladů čísla n na libovolný počet sčítanců vypočteme podle rekurentního vzorce n PÍ.n) = ^2v{n,i). i=i 5.3 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 5.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 5.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-i^-i Zajímavosti • Ferrersovy diagramy • Adjungovaný rozklad • Samoadjungovaný rozklad • Uspořádání rozkladů • Znázornění uspořádání rozkladů pomocí hasseovského diagramu 14 Kapitola 6 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 6.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 6.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). Rozdělování rozlišitelných předmětů do rozlišitelných přihrádek Věta 6.3 Nechť n, k jsou libovolná přirozená čísla. Pak lze n rozlišitelných předmětů rozdělit do k rozlišitelných přihrádek rozdělit právě kn způsoby. 15 Rozdělování rozlišitelných předmětů do rozlišitelných přihrádek, přičemž žádný přihrádka nezůstane prázdná Věta 6.4 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ě k!S(n,k) = Y,(-iy(k)(k-*)n i=0 ^ ' způsoby (princip inkluze a exkluze). Rozdělování nerozlišitelných předmětů do rozlišitelných přihrádek Věta 6.5 Nechť n, k jsou libovolná přirozená čísla,. Pak lze n nerozlišitelných předmětů do k rozlišitelných přihrádek rozdělit právě n + k — 1 k - 1 způsoby. Rozdělování nerozlišitelných předmětů do rozlišitelných přihrádek, přičemž žádná přihrádka nezůstane prázdná Věta 6.6 Nechť n, k jsou libovolná přirozená čísla,. Pak lze n nerozlišitelných předmětů do k rozlišitelných přihrádek tak, aby v každé přihrádce bylo aspoň r předmětů, rozdělit právě n — kr + k — 1 k - 1 způsoby. Pro r = 1 je tento počet zřejmě n — 1 k - 1 Rozdělování rozlišitelných předmětů do nerozlišitelných přihrádek Věta 6.7 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. Poznamenejme, že S(n, k) jsou Stirlingova čísla 2. druhu (viz dříve). 16 Rozdělování nerozlišitelných předmětů do nerozlišitelných přihrádek Věta 6.8 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). 6.1 Cvičení Cvičení 6.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í 6.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í 6.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. 17 Kapitola 7 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 7.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 7.2 • rekurentní formule 3. řádu: f {n + 3) = f {n + 2) — 5 f (n) • rekurentní formule 1. řádu: f (n + 1) = log f (n) 18 7.1 Řešení lineárních rekurentních formulí s kon-statní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 7.3 Lineární rekurentní formule s konstantními koeficienty je rekurentní formule tvaru f(n + k) = ai • f(n + k - 1) + a2 • f(n + k - 2) + • + ak ■ f(n) Poznámka 7.4 Řešením rekurentní formule je posloupnost. Věta 7.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 7.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. 19 Kapitola 8 Magické a latinské čtverce 8.1 Magické čtverce Definice 8.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 8.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é. 8.2 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 20 Příklady okruhů a těles • (N, + , •) - není okruh • (Z, +, •) - je okruh, není těleso • (Q< +1 •) - Je těleso • (M, + , •) - je těleso 8.3 Konečné okruhy a tělesa • zbytkové třídy modulo m • prvočíselné modulo • modulo je číslo složené 8.4 Latinské čtverce Definice 8.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 71. (Tedy čísla v libovolném řádku/sloupci jsou navzájem různá.) 12 3 4 Příklad 8.4 Latinský čtverec je například následující schéma: 34^2 4 3 2 1 21 Kapitola 9 Konečné roviny 9.1 Konečné afinní roviny Definice 9.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 ^ 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: 22 Věta 9.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 9.3 V konečné afinné rovině mají všechny přímky stejný počet bodů. Důkaz viz např. [1, 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 9.4 (Řá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 9.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 9.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} 9.2 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: 23 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 9.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 9.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 [1, str. 85]. 9.3 Konečné projektivní roviny Definice 9.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. 24 Kapitola 10 Zajímavé úlohy 10.1 Úloha o frontě u pokladny Cvičení 10.1 U pokladny stojí m + k lidí, přičemž m lidí má (pouze) dvou-setkorunu a k lidí má (pouze) stokorunu. Lístek do kina stojí 100 Kč. Kolika způsoby se mohou postavit do fronty tak, aby prodej lístků probíhal bez zastavení? 25 Literatura [1] Eduard Fuchs, Diskrétní matematika pro učitele (skriptum), Brno: Přírodovědecká fakulta Masarykovy univerzity, 2001. [2] Jaroslav Nešetřil, Jiří Matoušek, Kapitoly z diskrétní matematiky, MAT-FYZPRESS 1996. [3] 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. 26