MASARYKOVA UNIVERZITA • PRÍRODOVEDECKÁ FAKULTA Eduard Fuchs DISKRÉTNÍ MATEMATIKA PRO UČITELE Brno 2011 Z-fý -r í í - \J C ť ,ľ * J. Í ľ © 2001, 2011, Eduard Fuchs © 2001, 2011, Masarykova univerzita ISBN 978-80-210-5459-2 2610490608 předmluva Prvotní impulzy, které posléze lidstvo přivedly k vybudování matematiky, byly bezpochyby dvojího druhu: početní a geometrické. Tyto impulzy také předznamenaly jeden z centrálních protikladů, které lze vypozorovat v celé dosavadní historii matematiky - vztah diskrétního a spojitého. Typickými reprezentanty matematických objektů nacházejících se na straně diskrétního proudu jsou přirozená, respektive celá čísla, konečné množiny, konečné geometrie apod., spojitý směr reprezentují objekty jako množina všech reálných čísel, přímka, eukleidovská rovina, spojitá funkce apod. Jak již název napovídá, zabývá se diskrétní matematika první z výše uvedených stránek našich modelů reality. Je svým způsobem paradoxní, že poté, co matematika na sklonku 19. století zvládla v Cantorově teorii množin problematiku matematického nekonečna (více viz v [4] nebo na CD [3], patří mezi matematické disciplíny, které se ve 20. století rozvíjejí nejdynamičtěji, právě diskrétní matematika, jejíž značná část se zabývá studiem konečných množin. To, že zejména v poslední třetině 20. století prodělala diskrétní matematika přímo bouřlivý rozvoj, bylo způsobeno řadou faktorů. Mezi klíčové patří: • neustále se rozšiřující škála aplikací nejen v matematice samotné, především však mimo ni, a to nejen v „tradičních" přírodovědných oblastech, ale zejména v nových a mnohdy nečekaných souvislostech; • intenzívní rozvoj výpočetní techniky, která umožňuje provádět výpočty a analýzy, které se ještě před několika desetiletími zdály nemožné a nadlouho přesahující hranice lidských možností. V předloženém textu jsou vyloženy úvodní partie centrálních disciplín moderní diskrétní matematiky - kombinatoriky a teorie grafů v rozsahu, který by měli ovládat středoškolští učitelé matematiky. K základnímu textu jsou připojeny dva dodatky. V prvním jsou uvedeny základní biografické údaje osobností, které jsou v textu zmiňovány, ve druhém jsou tabulky některých studovaných funkcí. 3 Za pomoc při přípravě sazby tohoto textu děkuji Mgr. M. Anderovi a Mgr. D. Kottovi, který navíc celý text pečlivě pročetl a přispěl k jeho závěrečným úpravám. Za veškeré chyby a nedostatky však samozřejmě plně odpovídá autor. Čtenářům budu vděčný, když případné chyby a nedostatky, které v textu zjistí, zašlou na mou mailovou adresu: f uchs@math .muni . cz. Za jejich připomínky jim předem děkuji. Obsah předmluva 3 Obsah 5 1 Kombinatorika 7 1 Co to je kombinatorika a kdy vznikla.............. 7 2 Základní kombinatorické funkce................ 11 3 Základní kombinatorické pojmy................ 19 4 Rozklady konečných množin.................. 32 5 Princip inkluze a exkluze.................... 40 6 Rozklady přirozených čísel na sčítance............. 48 7 Rozdělování do přihrádek.................... 55 8 Řešení rekurentních formulí .................. 59 9 Vytvořující funkce ....................... 71 10 Bloková schémata, latinské čtverce a konečné roviny..... 81 2 Teorie grafů 97 1 Co to je teorie grafů a kdy vznikla............... 97 2 Základní pojmy......................... 101 3 Souvislé grafy.......................... 108 4 Stromy.............................. 112 5 Mosty, artikulace a některé grafové charakteristiky ...... 125 6 Eulerovské a hamiltonovské grafy............... 131 7 Rovinné grafy.......................... 139 8 Barvení grafů.......................... 149 9 Zobecnění pojmu graf...................... 159 Dodatek 1: Biografie 162 Dodatek 2: Tabulky 167 Rejstřík 173 Literatura 177 5 DISKRÉTNÍ MATEMATIKA PRO UČITELE doc. RNDr. Eduard Fuchs, CSc Vydala Masarykova univerzita roku 2011 Druhé vydání, 2011 Náklad: 300 výtisků Tisk: Tiskárna Blansko Těchov Těchov 152 678 01 Blansko ISBN 978-80-210-5459- 2 muni PRESS ISBN 978-80-210-5*159-2 -- -------i. 9 *ř08O£1 "U>J7<. 2610490608 2610490608 Kapitola 1 Kombinatorika 1 Co to je kombinatorika a kdy vznikla Jak uvidíme, neexistuje na otázky v nadpise jednoduchá odpověď. Částečnou odpovědí na první část otázky je - v jistém smyslu - celá první kapitola. Tak jak je obtížné sdělit, co to je vůbec matematika, je nesnadné charakterizovat i její jednotlivé části. Pokusme se alespoň stručně naznačit, co je předmětem kombinatoriky (nazývané též kombinatorická analýza, kombinatorická teorie apod.) a jakými metodami se v kombinatorice pracuje. Často se podle autora jedné z prvních učebnic kombinatoriky E. Netta (kniha Lehrbuch der Combinatorik vyšla v roce 1901) říká, že „kombinatorika je část matematiky zabývající se rozdělováním, uspořádáváním, nebo výběrem prvků nějaké množiny". Z modernějšího hlediska je centrálním pojmem kombinatoriky tzv. konfigurace, což je pojem, který bychom mohli charakterizovat jako „zobrazení nějaké množiny objektů do konečné abstraktní množiny se zadanou strukturou" (viz Bergeovu knihu [1]). Uvedená formulace sice pěkně zní, čtenář z ní však patrně těžko pochopí, co to konfigurace vlastně je. Objasnění tohoto pojmu vyplyne z dalšího textu, neboť v něm budeme studovat řadu nejrozmanitějších konfigurací. Kromě těch nejelementárnějších, tj. variací, permutací a kombinací (čtenáři dobře známých již se střední školy), to budou např. rozklady konečných množin, rozklady přirozených čísel na sčítance, rozdělování předmětů do přihrádek, latinské čtverce, bloková schémata, konečné afinní roviny a další. Jaký je hlavní okruh otázek s těmito konfiguracemi spojený? Konfigurace jsou nejčastěji studovány z následujících aspektů: (1) Existuje jistá konfigurace nebo nikoliv? (Budeme například řešit, zda existují ortogonální latinské čtverce daného řádu, zda existuje jistá afinní 7 8 /. KOMBINATORIKA rovina a podobně.) (2) Kolik existuje předepsaných konfigurací? (Středoškolská kombinatorika v podstatě spočívá v určení počtu variací, permutací a kombinací daného typu. My se však budeme zabývat i podstatně komplikovanějšími problémy.) (3) Lze najít metodu, jak vypsat všechny konfigurace daného typu? (Je zřejmé, že jde o kvalitativně odlišnou úlohu než je problém popsaný v bodě (2).) (4) Jaké je „asymptotické" chování počtu daných konfigurací? (Vzhledem k tomu, že budeme téměř neustále pracovat s konečnými množinami, bude počet konfigurací daného typu téměř vždy konečný. Proto by se mohlo zdát, že nejjednodušší určení počtu všech konfigurací spočívá prostě ve vypsání všech možností. To je však ve většině případů prakticky vyloučeno, neboť počet daných konfigurací je tak obrovský, že vypočítat všechny možnosti nelze - stačí si například jen uvědomit, jak rychle roste funkce n\. I když často známe např. rekurentní formuli pro počet k(n) konfigurací daného typu (pro všechna n e N), roste funkce k(n) tak rychle, že již pro poměrně malá n nelze k(n) přesně vyčíslit ani pomocí počítačů. Pak se alespoň snažíme najít nějakou „jednoduchou" funkci, která popisuje, „jak rychle" k{n) roste.) (5) Jak najít z konfigurací daného typu tu, která optimálně vyhovuje zadaným předpokladům? (Úlohy tohoto typu mají řadu konkrétních aplikací v matematice i mimo ni. Uvedeným problémem se zabývá intenzivně rozvíjená část kombinatoriky - tzv. teorie „kombinatorických algoritmů".) O většině uvedených aspektů se v dalším alespoň stručně zmíníme. Přesto zůstává řada závažných částí kombinatoriky, o nichž nemůžeme pojednat ani ve zkratce. Jmenujme za jiné alespoň kombinatorickou teorii uspořádaných množin, Pólyovu teorii enumerace či teorii kódování. K popsání uvedených teorií nemáme k dispozici dostatečný matematický aparát, ani nám to neumožňuje rozsah tohoto textu. Metody v kombinatorice užívané můžeme rovněž popsat jen částečně. Jak alespoň naznačíme, užívá se v kombinatorice výrazně i těch nejkomplikova-nějších metod algebry, reálné i komplexní analýzy i geometrie. Kromě toho si kombinatorika vytvořila i své specifické metody, z nichž se později zmíníme například o metodě inkluze a exkluze a o teorii vytvořujících funkcí. Jak uvidíme, řadu kombinatorických problémů lze velmi snadno zformulovat, avšak jejich řešení je velmi často obtížné. 1. Co to je kombinatorika a kdy vznikla? v Prozatím jsme se pokusili alespoň naznačit, co to kombinatorika je. Nyní stručně k její historii. První „kombinatorické" výsledky či alespoň náznaky jsou až překvapivě staré. Pravděpodobně nejstarší „konfiguraci" lze nalézt v jednom z nejstarších dochovaných textů v historii lidstva. V posvátné knize taoismu I-tíng, (tj. Kniha proměn) z roku přibližně 2200 př. Kr. jsou dvě konfigurace, nazývané Lo-šu a Riční mapa. Na obrázku 1.1 je konfigurace Lo-šu. Obr. 1.1: Konfigurace „Lo-šu" ve středověkém textu Nahradíme-li znázorněné skupiny bodů čísly, obdržíme známý magický čtverec (nazývaný též Saturn): 4 9 2 3 5 7 8 1 6 V tomto čtverci je součet čísel v každém řádku, sloupci i úhlopříčce roven číslu 15. Drahá konfigurace, kterou podle pověsti měla na svém krunýři znázorněnu posvátná želva vylézající z řeky Ho, je znázorněna na obr. 1.2. Znázorníme-li toto schéma čísly, obdržíme 7 2 10 10 8 3 5 4 9 10 10 1 6 10 7. kombinatorika o o o é • o o o o • • ♦ o o o o o • • é o • • • o o o o o o o o o Obr. 1.2: Konfigurace „Říční mapa" Toto schéma je pozoruhodné svou „středovou symetrií". Platí například 5 + 3 = 8, 5 + 1= 6 atd., 3 + 10 + 2 = 8 + 7, 3 + 10 + 1 = 8 + 6 atd. Rada kombinatorických pojmů je doložena například ve staré indické matematice. Kombinatorika jakožto matematická disciplína se však začíná konstituovat až cca v 16. až 17. století, prakticky - vcelku evidentně - současně se vznikem teorie pravděpodobnosti. Kombinatorické úvahy lze vysledovat v díle B. Pascala, P. Fermata a dalších. První publikovanou prací z kombinatoriky je Leibnizovo dílo Disertatio de Arte Combinatoria z roku 1666. V 18. století k rozvoji kombinatoriky zvlášť významně přispěl L. Euler. Opravdu bouřlivý rozvoj však kombinatorika prodělává až ve 20. století, zejména pak v posledních třiceti letech, kdy se v souvislosti s rozvojem výpočetní techniky rozvíjí celá tzv. diskrétní matematika, jejíž významnou součástí je právě kombinatorika. 2. Základní kombinatorické funkce íl 2 Základní kombinatorické funkce 2.1. Definice. Funkci n\ (čti n faktoriál) definujeme pro všechna n e No takto: n\ = ■ 1 pro n = 0 1 • 2 • ... ■ n pro « > 0. 2.2. Poznámka. Podle výše uvedené definice tedy pro všechna n e No platí: (n + 1)! = (n + l) -n\ 2.3. Příklad. Pro funkci n! lze dokázat řadu vztahů, od elementárních po velmi komplikované. Například v matematické analýze se dokazuje, že 111 1 — =--í---1----H--+ •••=£. . n\ 0! 1! n! n=0 oo (Připomeňme, že součtem nekonečné řady ]T a„ rozumíme následující limitu (pokud existuje): lim s„, kde sn = ao + a\ + ■ ■ ■ + a„.) «—►00 Odtud například plyne 00 1 00 - 00 , 00 1 yl^l = y_J--rl = rl_(e_2) = (,_i)_(e_2) = i. ^ n\ ^ in - 1)! n\ n\ n-2 n=2 v ' n=2 /(=] 2.4. Poznámka. Zobecněním funkce n\ na všechna kladná reálná čísla je tzv. Eulerova funkce gama definovaná takto: co 0 Lze dokázat, že pro každé přirozené číslo n platí: T(n) = (n — 1)!. Funkce F(x) je přitom spojitá v celém definičním oboru. 12 I. KOMBINATORIKA Hodnoty n\ rostou s rostoucím n „velmi rychle". Pro alespoň částečnou představu uvádíme v tabulce na straně 168 hodnoty n \ pro n € {1, ..., 25}. K přibližnému výpočtu hodnot n! pro velká n se nejčastěji užívá tzv. Stir-lingovy formule n\ ~ \llnn ■ e~" ■ n", kde symbol ~ značí, že podíl výrazů na obou stranách pro n —> oo konverguje k 1. 2.5. Definice. Buď k € N libovolné. Funkci (x)k definujeme pro všechna reálná x takto: (x)k = x (x-l).(x- -2)-...-(x -k + 1). Dále klademe (x)o = 1. 2.6. Definice. Buď k e N libovolné. Funkci (x)^ definujeme pro všechna reálná x takto: (x)(k) = x ■ (x + 1) • (x + 2) •... • (x + k - 1). Dále klademe (x)(0) = 1. 2.7. Definice. Buď ŕ e No libovolné. Pro každé reálné číslo x definujeme x\ (x)t x • (x — 1) • (x — 2) •... • (x — k + 1) k J k\ k\ Pro celé záporné číslo k pokládáme 0. 2.8. Poznámka. Symbol y^J (čti „x nad k") se obvykle nazývá binomický koeficient. (Toto pojmenování je spojeno se jménem významného algebraika 16. století Michaela Stifela.) Pro n, k € Nq se í J nazývá také kombináciu' 2. Základní kombinatorické funkce 13 číslo. O kombinatorickém významu funkcí ni, (x)k, (x)^k) a budeme hovořit v následujících paragrafech. 2.9. Příklad. (a) Pro každé x e M platí y^j = 1, zejména = 1. /-4\ (-4) • (-5) • (-6) (b) í J = 6 = -20- (c) ik\ _ (i) • H) ■ (-1) ■ (-1) _ 5 4/- 24 128 (d) Pro «, e No, n < £ platí j " I = 0, neboť {n)k = 0. (e) Pro n, k e N0, n > k platí n\ {n)k n\ KkJ k\ (n-k)l-kl (f) Pro každé n € N0 platí j\ _(-!)" /2/i\ (-1)" (2n - 1 22'1 V" 7 22""1 \« - 1 Vskutku, pro n = 0 je tvrzení evidentní. Nechť je tedy n > 0. Pak lx 1 / 1\ / 3\ / 2n-3\ / 2n-í 2 n\ \ 2J \ 2/ V 2 / V 2 1 (-1)" (2n)! _ (-1)" (2n)! n! ' 2« ' 2 • 4 • ... • (2n - 2) ■ 2n ~ 22'1 ' (n!)2 (-i)" /2«\ (-i)" /2/i - r 22" V n J 22""1 V n - 1 (g) Pro každé n G No platí I\ _ (2n - 2 vn/ n • 22"-1 V n — 1 Vskutku, podle definice platí 1 (1 \ / 1 \ / 2/; - 3 1 2 n) n\ V 2 / V 2 Dosadíme-íi za součin 1 (Jí \ (' 2" ~ 3 n\ ' \2) ' 2 14 /. KOMBINATORIKA výraz z príkladu (f), dostáváme nn - 1\ 1 22""1 ' V« - 1 J ' 2« - 1 ~ (_iy-i (2n-l)! _J_ (-l)""1 (2« - 2)! 22""1 ' - 1)! ' 2n- 1 ~ n -22"-1 ' (n - l)!2 (-I)""1 /2n-2\ n -22"-1 ' V n - 1 )' Dosadíme-li do posledního vztahu n+\ místo n, obdržíme „symetričtější" vzorec (platný pro každé n e No): 2.10. Definice. Podle definice je (x)„ = x ■ (x — 1) • (x — 2) •... ■ (x — n + + 1) polynom n-tého stupně. Označíme-li koeficient u xk symbolem s(n, k), dostáváme (x)n = s(n, 0) +s(n, \)x +s(n, 2)x2 + ■ ■ ■ + s(n, n)x". Koeficienty s(n, k) se nazývají Stirlingova čísla L druhu. 2.11. Věta. Pro Stirlingova čísla 1. druhu platí následující rekurentní formule: Důkaz. Tvrzení s (n, 0) = 0aj(n,n) = 1 jsou zřejmá. Dokažme tedy první vztah. Podle definice platí (*)„+! = (x)n ■ (x -«), takže, opět podle definice, • • • + s(n + \,k)xk + ..• = (••• +s(n, k — l)xk~l +s(n, k)xk + ...)(x — n). Porovnáním koeficientů u xk na levé a pravé straně poslední rovnosti obdržíme dokazovanou formuli. • s(n + 1, k) = s(n, k — 1) — n • s(n, k), s(n, 0) = 0, s{n, n) = 1. 2. Základní kombinatorické funkce 15 2.12. Poznámka. Rekurentní formule z věty 2.11 nám umožňuje, jak se čtenář může snadno přesvědčit, postupně počítat čísla s(n,k). Některé hodnoty uvádíme v tabulce na straně 170. 2.13. Věta. Pro každé celé číslo k a každé reálné číslo x platí: x\ í x \ íx + 1 k) + \k+ \) ~\k + \ Důkaz. Pro k < 0 je tvrzení splněno triviálně. Nechť tedy je k > 1. Pak x\ í x \ _ {xh (x)k+] (k + l)(x)k + (x)k+l k J \k + lj k\ (k + \)\ (k + l)l (k + 1) -x(x - !)•• ■ (x -k + l)+x(x - 1) ■ (x -k) (k + iy. x(x — 1) • • • (x — k + 1) • (k + 1 +x — k) = (* + D! = (x + l)k+l (x + \ {k + \)\ \k + \ Tím je důkaz hotov. e 2.14. Poznámka. Z definice binomických koeficientů a z věty 2.13 plyne platnost následující rekurentní formule: Pron, k e N, n > k platí n + l\ fn\ŕ n \ ("\ = (< = h k ) \k) \k-\) VO/ \n Tato formule nám umožňuje postupně počítat hodnoty . Tabulce hodnot I j se obvykle říká Pascalův trojúhelník. (Viz tabulku v příloze na straně 169.) Jak si čtenář jistě již při nejrůznějších příležitostech uvědomil, je většina pojmů nazvaných po dřívějších osobnostech, po nich pojmenována neoprávněně. Nejinak tomu je i v tomto případě, byťjde o název v evropské tradici obvyklý. Blaise Pascal (1623-1662) toto schéma popsal ve své slavné knize Traité du triangle arithmétique (tj. Pojednání o aritmetickém trojúhelníku), avšak prokazatelně dříve je znali například arabský astronom al-Tusi (1265), čínský matematik Chu Ši-Chie (1303) či indický matematik Narajána Pandita (1365). Dokonce i v evropské literatuře se toto schéma vyskytlo před Pascalem - v knize Petra Apiana (1495-1552). To však nic nemění na skutečnosti, že je toto schéma mnohdy užitečné, jak si ostatně čtenář jistě uvědomil již na střední škole. 16 /. KOMBINATORIKA Pro kombinační čísla lze dokázat řadu rovností, tzv. kombinatorických identit, které se v matematice uplatňují v nejneočekávanějších souvislostech. Důkazy některých těchto identit vyžadují důmyslných metod - viz např. knihu [8]. V následující větě shrneme jen několik nejelementárnějších. 2.15. Věta. Buďte n > k nezáporná celá čísla. Pak platí: (b) t 4=0 n n — k 2", (c)5t-(É)=-ř"' £=0 (d) XX-1) \ )=® pro každé přirozené číslo n. Důkaz, (a) Tvrzení plyne přímo z definice. (Řádky Pascalova trojúhelníka jsou tedy „symetrické".) (b) Indukcí. Pro n = 0 je tvrzení triviální. Nechť tedy formule platí pro dané n > 0. Pak n+l E 4=0 n + l n + 1 0 E 4=1 n k - 1 + —e :)♦£"' + (c) Protože „:,)=ě0+ě(;H 7 4=0 v 7 4=0 v 7 G) ~ (n - /t)' 4=0 v 7 4=1 + 2" =2' platí £ • + (n - k) n — k = n n\ n k) = 2 n n — k Odtud n\ n k 2 \k 4=0 E* 4=0 (d) Přímým výpočtem dostáváme n \ n 2n=n-2n~\ k=0 4=1 n-l\ /n-í k - 1J + V /t 2. Základní kombinatorické funkce 17 ("0)+g<-»iv)+g<- 0. Pak E! (x + k\ -A* (x + &\ /* + n + 1 ( * J = E( * J + ( B+1 ;c + n + l\ /x + n + l\ /jc+n + 2 n / V n+1 / lrt+1 Dosadíme-li ve větě 2,16 n — k místo k a x místo x+rc, dostaneme okamžitě tvrzení následujícího důsledku. 2.17. Důsledek. fe=0 .r — A \ /jc\ fx — 1\ (x — 1\ t x — ri\ í x + 1 n — kl \n J Vři — 1 / \n — 2 J VO/ V n Poznámky a cvičení 1. Dokažte, že 5^(Jfc • Jfc!) = (n + 1)! - 1. brno 18 /. KOMBINATORIKA 2. Dokažte, že pro Stirlingova čísla 1. druhu platí vztah ^s(n,k) = 0. H > 1. 3. Dokažte identitu 4. Tzv. Catalanovu posloupnost 1, 2, 5, 14, 42, 132, 429. 1 430, 4 862, ... definovanou vztahem C") n + 1 studoval již Euler. Dokažte, že platí: a) ci = 2c, b) c3 = 3í"2 - Cl c) c4 = 4c3 - 3c2 d) c5 = 5C4 — 6C3 + C2 e) c6 = 6c5 - 10c4 + 4c3 f) c7 = 7c6 — 15C5 + 10C4 — C3 g) c, ) ( '2/i ) í n - 1 2n ) h) c, 71+1 — (n + 2) • (n + 1) ■ c, n 3. Základní kombinatorické pojmy 19 3 Základní kombinatorické pojmy Nejprve zavedeme označení, které budeme v dalším textu dodržovat. 3.1. Označení. Počet prvků konečné množiny X značíme |X|. Symbolem P (X) označíme, jak je obvyklé, množinu všech podmnožin množiny X. Pro k e No označme Pk(X) = {A; ACX, \A\ = k}. Mnoho kombinatorických úvah je založeno na následujícím zřejmém faktu. 3.2. Věta. Buďte A, B konečné množiny. Pak \A x B\ = \A\ - \B\. 3.3. Poznámka. Jinými slovy je věta 3.2 často formulována jako tzv. pravidlo součinu následovně: Lze-li objekt X vybrat r způsoby a po každém takovém výberu lze objekt Y vybrat s způsoby, pak lze uspořádanou dvojici [X, Y] vybrat r ■ s způsoby. Jako aplikaci věty 3.2 uveďme tvrzení, které v roce 1935 odvodili maďarští matematikové P. Erdôs a G. Szekeres. 3.4. Věta. Každá posloupnost a\, a%,,.., amn+\, která obsahuje mn + 1 navzájem různých celých čísel nutně obsahuje klesající vybranou podposloupnost o více než m prvcích nebo rostoucí vybranou podposloupnost o více než n prvcích. Důkaz. Pro každé i = 1,2,..., mn + 1 označme /c, počet čísel v nejdelší klesající podposloupnosti s prvním prvkem [&;,r;] je zobrazením množiny {a\ ,02, ■ ■■, amn+i) &° kartézského součinu {1, 2,.,., m} x {1, 2,..., n}. Ukážeme, že toto zobrazení je prosté. Nechť je i < j. Pak platí at < a j nebo a, > a j (neboť čísla a,, a j jsou podle předpokladu různá). Je-li ax < aj, pak platí zřejmě r i > rj, je-li a,- > aj, platí zase > kj. V obou případech je [&,,r,] ^ [kj, rj]. To je však spor, neboť nemůže existovat injekce množiny o mn + 1 prvcích do množiny o mn prvcích. 3.5. Definice. Buď n e N, \X\ = n. Pro k e N, k < n nazveme variací k-té třídy v X každý řetězec (A, <), kde A e Pk(X). 20 /. KOMBINATORIKA 3.6. Věta. Buďte k < n přirozená čísla. Nechť \X\ = n. Počet variaci k-té třídy v X je roven číslu Důkaz. Tvrzení plyne z pravidla součinu. První prvek lze vybrat n způsoby, 3.7. Poznámka. Počet uspořádaných k-úc bez opakování z n prvků je tedy roven číslu (n)* pro libovolná n, k e N (neboť pro k > n je (n)k = 0 podle definice). 3.8. Důsledek. Buďte X, Y konečné množiny, \X\ = n, \Y\ = k. Pak pro množinu inj (X¥) všech injekcí Y do X platí 3.9. Definice. Variace n-té třídy z n prvkové množiny se nazývají permutace této množiny. Z věty 3.6 okamžitě plyne. 3.10. Veta. Počet permutací n prvkové množiny je roven číslu (n)n = nl. 3.11. Poznámka. Je-liX = {1,2,..., n},je podle definice 3.9 permutací množiny X každý řetězec {a\ < a-i < ••• < an}, kde a, e X pro každé i. Zapíšeme-li tento řetězec jako uspořádanou n-tici \a\,a^, ..., a„], můžeme danou permutaci ztotožnit se zobrazením i —> a,. Toto zobrazení je obvyklé zapisovat ve tvaru Jinými slovy, za permutace množiny X můžeme považovat bijekce množiny X na sebe. Odtud a z věty 3.10 okamžitě plyne 3.12. Důsledek. Buďte X, Y konečné množiny. Pak pro množinubij (Yx) všech bijekcí X na Y platí (n)k = n ■ (n — 1) •...« (n — k + í). druhý n — 1 způsoby atd. mj(XY)\ = (n)k. |bij (Yx) 0 je-li \X\J\Y\, |ľ|! je-li \X\ = \Y\. 3. Základní kombinatorické pojmy 21 3.13. Definice. Buď X konečná množina, k e nq buď libovolné. Kombinací k-té třídy z X rozumíme každou k prvkovou podmnožinu množiny X. (Množina Pk(X) je tedy množinou všech kombinací k-té třídy z X.) Z vět 3.6 a 3.10 bezprostředně plyne 3.14. Věta. Buď X konečná množina, \X\ = n. Pak pro každé k e No platí 3.15. Příklad. Kolika způsoby můžeme na šachovnici (o 64 polích) rozestavit 8 věží tak, aby se žádné dvě z nich vzájemně neohrožovalyl Tomu, kdo ví, jak se v šachu tahá věží, je zřejmé, že hledáme právě všechna taková rozestavění věží, kdy v každé řadě a v každém sloupci stojí právě jedna věž. Očíslujeme-li pevně řady a sloupce čísly 1.....8, je poloha každé figury na šachovnici jednoznačně určena dvojicí [i, j], kde i je číslo řady a j číslo sloupce. Odtud je zřejmé, že hledaných rozestavení je 8! = 40 320. 3.16. Příklad, (a) Kolika způsoby můžeme rozestavit 6 dětí do kruhu! Do řady lze rozestavit 6 dětí 6! = 720 způsoby. Protože z každé řady utvoříme evidentním způsobem kruh, je počet takto vzniklých kruhů rovněž 720. Vzhledem k tomu, že však nerozlíšime dva kruhy lišící se jen pootočením, je hledaný počet ^ = 120. (b) Kolik náhrdelníků lze utvořit ze 6 korálků 6 různých barev! Mohlo by se zdát, že podle (a) 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 l-f = 60. 3.17. Příklad. Buď/V množina všech možných pořadí 16 oddílů v 1. fotbalové lize. Pro x, y e A položme x ~ y <=> v x, y je stejné pořadí na prvních třech místech a stejné dva oddíly sestupují. Určete |A/~|. Ze zadání plyne, že \A\ = 16!. Relace ~ je zřejmě ekvivalence na A, takže má smysl se ptát po počtu prvků faktormnožiny A/~. Protože pořadí mužstev na prvních třech místech je možno určit (16)3 /13\ . způsoby a ze zbývajících mužstev můžeme dvě sestupující určit I 1 způsoby, 2 platí |A/~| = (16)3 • ( 13 2 = 16 - 15 ■ 14 - 13 • 12 2 = 262080. 22 /. KOMBINATORIKA Prozatím jsme hovořili o variacích, permutací a kombinacích bez opakování. Nyní budeme uvažovat případy, kdy se prvky dané množiny mohou v uvedených výběrech opakovat. 3.18. Definice. Buď X 4 0 konečná množina, |X| = n. Nechť k e N0 je libovolné. Uspořádanou k-úci prvků z množiny X, v níž se prvky mohou opakovat, nazýváme k-variace s opakováním z prvků množiny X. Počet všech k-variací s opakováním označme V(n. k). 3.19. Poznámka. V této souvislosti je nutno důrazně upozornit na některé nesprávné (a časté) představy, které si řada studentů přináší již ze střední školy. Tyto omyly se týkají jak opakování tak určování pořadí prvků v dané variaci. V řadě příkladů, ať již uměle vykonstruovaných či vzniklých při řešení faktických problémů, opakování prvků ve variaci může a nemusí znamenat skutečné opakování konkrétních objektů. Když je například v osudí deset cifer 0, 1, ... , 9 a tvoříme několikamístné číslo tak, že vytáhneme číslo z osudí a opět je do osudí vrátíme, může být samozřejmě vytaženo znovu. Ve vzniklé variaci se tedy opravdu opakuje týž objekt. Častěji však užíváme variace s opakováním v případě, že se sice neopakuje stejný objekt, nás však zajímají jen některé vlastnosti objektů tvořících „základní" množinu, z níž variace tvoříme. Prvky, které mají stejnou vlastnost, pak nerozlišujeme, ač samozřejmě, „rozlišitelné" jsou. Vybereme-li například ve třídě (v níž je například 20 hochů a 10 dívek) 6 dětí a uspořádáme je do zástupu, obdržíme šestiprvkovou variaci, v níž se samozřejmě žádný prvek -žák neopakuje. Když se však například rozhodneme, že pro nás za jistých okolností bude podstatné pouze to, zda daný žák je hoch nebo dívka, avšak hochy, resp. dívky navzájem nebudeme rozlišovat, je možno tutéž šestici žáků považovat za variaci s opakováním, kde ovšem opakování neznačí opakování žáka, ale opakování vlastnosti „hoch" nebo „dívka". Jinak řečeno, variace s opakováním lze chápat jsko uspořádané fc-tice prvků několika druhů, přičemž navzájem nerozlišujeme předměty téhož druhu, ačkoliv tyto předměty jinak mohou být rozlišitelné. Druhý častý omyl u variací (ať již s opakováním či bez opakování) souvisí s „pořadím" prvků ve variacích. Toto pořadí může a nemusí souviset s jejich vybíráním z dané množiny objektů. Vytahujeme-li čísla z osudí a postupně je zapisujeme, je samozřejmě jejich pořadí určeno pořadím jejich vybrání z osudí. Když však vybereme ze třídy několik dětí a pak je seřadíme například podle výšky, nesouvisí obecně jejich pořadí v dané variaci vůbec s tím, v jakém pořadí jsme je ve třídě vybírali. 3. Základní kombinatorické pojmy 23 Proto je zcela nesmyslné tvrdit, že variace je skupina objektů, u nichž záleží na pořadí, v jakém jsme je vybírali. 3.20. Věta. Pro každé n, k € No platí V(n,k) = nk. Důkaz. Indukcí vzhledem k číslu k. Tvrzení V(n, 0) = n° = 1 je zřejmé. Nechť tedy V(n, k) = nk. Buď [a\, ... , ak] libovolná A>variace s opakováním. Je zřejmé, že počet (k + 1)-variací tvaru [a\, ..., ak, x] je roven číslu n. Odtud plyne, že V(n, k + 1) = n ■ V (n, k) = n ■ nk = nk+1. • 3.21. Příklad. Buďte X. Y konečné množiny. Nechť X = {«[,..., ak}. Přiřadí-me-li každému zobrazení /: X -> Y uspořádanou k-úci [f(a\), ..., f(ak)], vidíme okamžitě, že \YX\ = V(\X\ , \Y\) = \Y\m . 3.22. Definice. Buď k e N libovolné. Buď dáno n předmětů k druhů. Nechť n j značí počet předmětů i-tého druhu, i = 1, ... , k. (Tj. n \ + ■ ■ ■ + nk = n.) Symbolem P(n\, ... ,nk) označme počet prvků množiny všech uspořádaných «-tie těchto předmětů. Tyto n-tice nazýváme permutace s opakováním. Z věty 3.10 okamžitě plyne 3.23. Věta. Pro každá čísla n \,..., nk € Nq platí («i + • • • +nk)\ P(nu .... nk ) = «i! • n2l ■ ■.. ■ nk\ 3.24. Příklad, (a) Kolik různých čísel lze utvořit z čísla 3 855 835 přeskupením cifer? Protože dané číslo obsahuje dvě cifry 3, tri cifry 5 a dvě cifry 8, je hledaný počet 7! P(2, 3, 2) =-= 210. 2! • 3! • 2! (b) Když Christian Huygens objevil Saturnův prstenec, zašifroval svůj objev, jak bylo v té době časté, do následujícího tzv. anagramu: aaaaaaa ccccc d eeeee g h iiiiiii 1111 mm nnnnnnnnn oooo pp q rr s ttttt uuuuu 24 /. KOMBINATORIKA 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číme, za jak dlouho by počítač, který by vypsal milión permutací Huy-gensova anagramu za sekundu, vypsal všechny permutace. Spočtěme, kolik je všech permutací daného anagramu. Z počtu jednotlivých písmen v anagramu plyne, že všech permutací je PO, 5, 1,5, 1, 1,7,4,2,9,4,2, 1,2, 1,5, 5) = 9! • (7!)2 • (5!)4 • (4!)2 • (2!)3' Toto číslo je přibližně rovno číslu 3,573 • 1060. Počítač by tedy 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ě nez 1017 sekund. 3.25. Poznámka. Zajímavé aplikace čísel P(n\,.,., nk) lze najít například v úvahách o tzv. svazu k-tic. Buď k přirozené číslo. Symbolem Nq označme množinu všech uspořádaných k-úc [a\.....ak] nezáporných celých čísel. Definujeme-li na Nq relaci < takto: [ai, ..., ak] < [bi, ..., bk] a,- < b\ pro všechna i = 1, ..., k, je zřejmé, že relace < je uspořádání na množině Nq . Přitom je evidentní, že (Nq , <) je svaz, v němž sup {a,b} = [max (aj, b\), ..., max (ak, bk)], inf {a, b) = [min {a\, b\),..., mm (ak, bk)]. Svaz Nq můžeme reprezentovat následujícím způsobem. Bod [«],..., ak] e e Nq znázorníme jako bod eukleidovského prostoru E* a dva body a = = ak], b = [b\,..., bk] spojíme šipkou směřující z a do b právě tehdy, když existuje index i takový, že pro j 4 i, pro j = i. (Tzn., že z a do b vede šipka právě tehdy, když a pokrývá b ve svazu (Nq . < ).) Nyní se pokusme určit počet „cest" z bodu a do bodu b pro každé dva prvky a, b € Nq, a < b. (Cestou rozumějme posloupnost na sebe napojených šipek.) 3. Základní kombinatorické pojmy 25 032 032 032 032 032 032 032 032 032 032 022 022 022 022 022 022 031 031 031 031 012 012 012 021 021 021 021 021 021 030 002 011 011 011 011 020 011 011 020 020 —> 001 001 010 001 010 010 001 010 010 010 000 000 000 000 000 000 000 000 000 000 Tab. 3.1: Cesty z bodu 032 do bodu 000 Tak napríklad v Ng existuje 10 cest z bodu 032 do bodu 000 znázorněných v tabulce 3.1. Buďte nyní a = [a\, ... , ak], b = [b\,..., bk] libovolné dva prvky v Nq , takové, že a < b. Označme a, — b, = n,-, i = 1, ..., k. Definujme pro i = = 1,____k zobrazení a,-: Nq -> Nq takto: Cti [X],----Xk] - [XU----Xi-i, X[ 1, xM,----xk]. Nyní priraďme každé cestě z a do b odpovídající posloupnost zobrazení a,-. (Tak např. cestě z bodu 032 do bodu 000 uvedené na prvním řádku v tabulce 3.1 odpovídá posloupnost «2. a2. #2. a3< ^3> poslední cestě pak posloupnost «3, cř3, «2, «2-) Je zřejmé, že popsané přiřazení je bijekcí množiny cest z a do b na množinu všech posloupností utvořených z a, tak, že se v nich a, vyskytuje n,-krát. Odtud plyne, že hledaných cest je ^ (^(a, - h,)\. P{>i\, ... ,nk) =-. (ay -bi)\ ■... ■ (ak - bk)\ 3.26. Definice. Mějme dostatečný počet prvků n druhů. Skupinu k objektů, v níž nezáleží na pořadí a v níž navzájem nerozlišujeme předměty téhož druhu, nazýváme k-kombinace s opakováním. Počet těchto fc-kombinací s opakováním označme C{n,k). 3.27. Věta. Pro každé n, k € No platí C(n,k) = 26 /. KOMBINATORIKA Důkaz. Pro n = 0 nebo k = 0 je tvrzení triviální. Nechť tedy n ý 0 ¥ i-k. Každou -kombinaci s opakováním lze velmi jednoduše (a jednoznačně) popsat pomocí posloupnosti nul a jedniček takto: nechť je dána posloupnost «1, «2. • • • i Gk+n-i i v níž je k jedniček a n — 1 nul. Přiřaďme této posloupnosti /:-kombinaci s opakováním, v níž je tolik předmětů 1. druhu, kolik je v dané posloupnosti jedniček před první nulou, tolik předmětů druhého druhu, kolik je v dané posloupnosti jedniček mezi první a druhou nulou atd. Zřejmě nyní platí: (n+ifc-1)! ín + k-\\ ín + k-\\ c(M).j.(t.11-i)-lií-n5r.( k ) = ( n] ). 3.28. Poznámka. Pro pojem kombinace s opakováním bychom mohli zopakovat téměř vše, co jsme již uvedli v poznámce 3.19. I u kombinací s opakováním může a nemusí uvedené „opakování" značit, že se opakuje týž předmět. Když se dohodneme, že objekty s jistou vlastností budeme považovat za nerozlišitelné, může opakování značit opakování objektů stejné vlastnosti, přestože jinak tyto objekty mohou samozřejmě být rozlišitelné. Z důvodů uvedených v poznámce 3.19 je navíc nesmyslné tvrdit, že u kombinací nezáleží na pořadí, v němž byly prvky vybírány. Jak jsme viděli, nemusí na tomto pořadí záviset ani u variací. Upozorňujeme ještě, že v definici 3.26 nelze slovo „skupina" nahradit termínem „množina". Skupina tří prvků (například písmen a.a.b) není totéž jako množina {a, a, b}, neboť ta má jen dva prvky; je to jen nešikovně napsaná množina, neboť v množině se žádný prvek opakovat nemůže, (Pro úplnost dodejme, že i množina {a, b} je dvouprvková pouze tehdy, když a, b neznamenají týž objekt.) 3.29. Příklad. Buďte X, Y konečné řetězce. Zjistíme, kolik existuje izotonních zobrazení XdoY. Nechť X = {x\ < x2 < - ■ ■ < xk], Y = {yi < yh < ■ ■ ■ < y,,}. Buď /: X -> Y izotonní zobrazení. Pak platí f(xi) < f{Xt) < ... < f(xk), takže izotonních zobrazení X do Y je tolik jako všech neklesajících fc-tic prvků z Y. To, že fc-ticím (v nichž se prvky mohou opakovat) předepíšeme pevně pořadí, je totéž, jako když pořadí prvků v A:-ticích nerozlišujeme. Podle věty 3.27 je tedy izotonních zobrazení X do Y can.ixD-C™1;1-1). 3. Základní kombinatorické pojmy 27 3.30. Příklad, (a) Kolika způsoby můžeme mezi 4 chlapce rozdělit 50 stejných kuliček? Postupujeme jako v důkazu věty 3.27. Přidejme k 50 kuličkám 3 kamínky. Poskládáme-li kuličky s kamínky do řady, rozdělí 3 kamínky posloupnost na 4 úseky. Označíme-li chlapce A, B, C, D & chlapci A dáme všechny kuličky z prvního úseku, chlapci B všechny kuličky z druhého úseku atd., je ihned zřejmé, že všech rozdělení je /53\ 53-52-51 P(50,3)= ) =-= 23 426. \3 J 3-2 (b) Pozměňme příklad (a) tak, že budeme požadovat, aby každý chlapec dostal alespoň jednu kuličku. Podle (a) tedy chceme zjistit, v kolika posloupnostech 50 kuliček a 3 kamínků nejsou žádné dva kamínky vedle sebe a rovněž není kamínek ani na prvním ani naposledmm místě posloupnosti. Tento počet zjistíme jednoduchým obratem. Dáme-li každému chlapci předem jednu kuličku, zůstane jich 46, které pak již můžeme rozdělit libovolně. Hledaných rozdělení je tak /49\ 49 • 48 ■ 47 p(46, 3)= =-= 18424. \3 J 3-2 Následující úloha je velmi jednoduchá, v dalším se však na ni budeme několikrát odvolávat. 3.31. Příklad. Mějme p prvků 1. druhu a q prvků 2. druhu. Kolik existuje permutací s opakováním těchto prvků takových, že žádné dva prvky 1. druhu nestojí vedle sebe? Hledaných permutací je zřejmě tolik, kolika způsoby lze rozmístit p prvků 1. druhu do q — 1 mezer mezi prvky 2. druhu a před první a za poslední z nich, tj. celkem mq + 1 míst. Tzn., že hledaný počet je \ + J pokud je p < q + \ a je roven 0, pokud p > q + 1. P 3.32. Příklad. Buď dán (c + m)-úhelník A] A2 ■ ■ ■ Ac+m, kde c,m € N, c + m > > 3. Kolika způsoby lze obarvit jeho vrcholy tak, aby jich bylo c červených, m modrých a žádné dva sousední vrcholy nebyly červené? Označme hledaný počet obarvení t{c,m). Je zřejmé, že pro c > m je t(c, m) = 0. Nechť tedy c < m. Úlohu lehce vyřešíme pomocí úlohy 3.31. Označíme-li výsledek příkladu 3.31 symbolem r(p, q), je zřejmě takových „přípustných" obarvení vrcholů, při nichž je vrchol A\ červený, celkem 28 7. KOMBINATORIKA r (c — 1, m — 2). Prípustných obarvení, při nichž je A\ modrý, je r (c, m — 1). Odtud (m — 1\ fm\ c + mím\ I + I J =-1 I. 3.33. Příklad. Muž prodávající Večerník (za 5 korun) u sebe nemá na začátku prodeje žádné peníze. Ihned se před ním utvořila fronta m + k lidí, přičemž m lidí má u sebe pouze desetikorunovou minci a k lidí pouze pětikorunu. Kolika způsoby se tito lidé mohou postavit do fronty tak, aby měl prodávající vždy nazpět na desetikorunu1? (Rozlišujeme rozestavení „pětikorun" a „desetikorun" a nikoliv jednotlivé lidi se stejnou mincí.) Počet všech možných rozestavení „pětikorun" a „desetikorun" do fronty je počet příslušných permutací s opakováním, tj. P(m t) = C«lii)j - (m + k\ m\k\ \ k ) Dále je zřejmé, že úloha má alespoň jedno řešení právě tehdy, když m < k; jinak se totiž prodej nutně zastaví. V dalším tedy předpokládáme, že platí 0 < m < k. Každé rozestavení lidí ve frontě můžeme evidentně zapsat jako posloupnost m jedniček (označujících lidi s desetikorunou) a k pětek (označujících lidi s pětikorunou). Podle zadání hledáme počet „příznivých" permutací, tj. takových permutací {a\, ..., ak+m) m jedniček a k pětek, které mají následující vlastnost: pro každé d takové, že 1 < d < m + k je mezi prvky a\,..., a.4 alespoň tolik pětek jako jedniček. Nejprve dokážeme, že počet nepříznivých případů je roven číslu (m + k\ \k + lj Nechť tedy a\, ..., ak+m je nějaká nepříznivá permutace. Nechť do je nejmenší index takový, že mezi prvky a\,..., aj0 je více jedniček než pětek. Pak zřejmě do = 2s +1, přičemž mezi prvky ai,...,a^jcs jedniček a s pětek. Připíšeme-li před zadanou permutaci jednu pětku, dostaneme tak permutaci m jedniček a k +1 pětek. V této permutaci stojí na prvním místě pětka a mezi prvními 2s + 2 členy je nyní s + \ jedniček a s + 1 pětek. Nyní v permutaci 5, a], ..., ak+m zaměňme na prvních 2s + 2 místech vzájemně pětky a jedničky. Původní nepříznivé permutaci a\,ak+m tak popsaným způsobem přiřadíme permutaci m jedniček a k + 1 pětek, v níž na prvním místě stojí cifra 1. Přitom je zřejmé, že různým nepříznivým permutacím jsou přiřazeny různé permutace uvedeného typu. 3. Základní kombinatorické pojmy 29 Nyní ukážeme, že každá posloupnost m jedniček a k + 1 pětek s jedničkou na začátku je přiřazena některé nepříznivé permutaci. Buď tedy bo,b\,..., bk+m libovolná permutace m jedniček a k + 1 pětek, lh) = 1. Protože platí m < k (podle předpokladu), existuje nej menší index do takový, že mezi členy bo,b\,..., bd0 je stejný počet jedniček jako pětek. Zaměníme-li v posloupnosti bo,b\,..., b^ vzájemně jedničky a pětky a pak vynecháme první cifru (tj. pětku), dostaneme zřejmě onu nepříznivou permutaci, jíž je přiřazena daná permuatce bo,b\,..., <&*+»,. Zjistili jsme tak, že počet všech nepříznivých rozestavení fronty kupujících je roven počtu všech permutací, v nichž je m jedniček a k + 1 pětek a v nichž na prvním místě stojí jednička. Vynecháme-li tuto první jedničku, dostaneme právě všechny permutace m — 1 jedniček a k + 1 pětek, jichž 6n + k^ je P(m — l, k + l) = ( ^ I. Protože všech permutací je, jak jsme již / m + k\ (m + k\ uvedli, P(m, k) = 1 = , je počet všech příznivých permutací \ k J \ m J m +k\ í m + k\ k — m + 1 í m + k^ m J \m — 1 / k + 1 V m Je-li zejména m = k, tj. ve frontě je stejný počet lidí s desetikorunou jako s pětikorunou, může stát fronta bez zdržování celkem 1 /2/tN k + l\k způsoby. Poznámky a cvičení 1. Kolika způsoby můžeme na šachovnici vybrat (a) dvě pole (2016) (b) dvě pole různých barev (1024) (c) dvě pole neležící ve stejné řadě ani ve stejném sloupci (1 568) (d) dvě pole různé barvy splňující podmínku (c) (768) 2. Nechť pi, ..., pn jsou navzájem různá prvočísla, k\, ..., kn buďte libovolná přirozená čísla. Určete součet všech dělitelů čísla a = tf.....p*». 30 /. KOMBINATORIKA (Mezi dělitele počítáme i čísla 1 af) - 1 3. Kolik existuje šesticiferných čísel, v nichž se vyskytují tři liché a tři sudé 4. Stěny každé ze tří hracích kostek jsou očíslovány čísly 1, 4, 13, 40, 121 a 364. Kolik různých součtů lze získat při hodu těmito kostkami? (56) 5. 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? (2 000 376) 6. Havajská abeceda má 12 písmen: samohlásky a, e, i, o, w, souhlásky h,k,l,m,n,p,w. a) Dokažte, kolik lze utvořit slov o čtyřech písmenech. b) Kolik z uvedených slov má na druhém a čtvrtém místě samohlásku a na zbývajících místech souhlásku? c) Kolik slov má na druhém a čtvrtém místě samohlásku? 7. Každý člověk má dva (biologické) rodiče, 4 prarodiče atd. Kolik předků má každý z nás ve 20 předešlých generacích (cca v posledním půl tisíci- 8. Palindrom je posloupnost symbolů, která je stejná, čteme-li je zepředu i zezadu (například „tabat"). Určete počet sedmiciferných a osmiciferných palindromů (v dekadickém zápisu), nesmí-li se žádná číslice užít více než dvakrát. 9. Dokažte, že každé palindromické číslo sudé délky je dělitelné číslem 11. 10. Určete celkový počet přirozených čísel, v jejichž dekadickém zápisu se neopakuje žádná cifra. 11. 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 cifry? (281 250) letí)? 3. Základní kombinatorické pojmy 31 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. 32 I. KOMBINATORIKA 4 Rozklady konečných množin Víme, že rozkladem na množině A rozumíme systém A neprázdných po dvou disjunktních množin, jejichž sjednocením je množina A. Prvky systému A nazýváme třídy rozkladu A. Systém JC(A) všech rozkladů na množině A uspořádáme relací < definovanou pomocí zjemnění, tj. pro X, ľ e X(A) platí X < Y (U e X, V e Y, U n V 4 0 =>■ U c V). Snadno lze dokázat, že (JC(A), < ) je úplný svaz izomorfní s úplným svazem (S(A), C) všech ekvivalencí na množině A. V tomto paragrafu určíme | JC(A) \ pro konečnou množinu A a určíme počet rozkladů na třídy o jistých předepsaných vlastnostech. 4.1. Dennice. Označme Bn počet všech rozkladů na n prvkové množině, n e N. Čísla B„ se nazývají Bellova čísla. Bellova čísla se často vyskytují v řadě aplikací. Nejprve odvodíme rekurentní formuli pro jejich výpočet. Důkaz. Předpokládejme, že známe čísla B\,..., B„ a chceme určit číslo Bn+\. Buď X libovolná množina o n prvcích. Buďa ^ X libovolný prvek. Položíme-li X, =XU{a},je \Xi\ =n + l. Buď X] libovolný rozklad množiny X[. Prvek a leží v některé třídě rozkladu Xi. Tato třída může mít 1, 2,...,« + 1 prvků. Spočtěme, kolik je na X\ rozkladů takových, že prvek a leží ve třídě o k prvcích. Zbývajících k — 1 prvků v této třídě můžeme z množiny X\ vybrat způsoby. Máme-li utvořenu třídu obsahující prvek a, můžeme na zbývajících n — k + 1 prvcích zvolit libovolný rozklad. Podle předpokladu je těchto rozkladů J5„_í+[. Podle pravidla součinu odtud plyne, že prvek a leží v ^-prvkové třídě (k = 1,.... n + 1) v 4.2. Věta. 4. Rozklady konečných množin 33 rozkladech. BQ pritom značí počet rozkladů, kdy a leží ve třídě o mohutnosti n + 1, tj. B0 = 1. Počet všech rozkladů na X] je roven součtu všech výše uvedených možností. To je však právě dokazovaná formule. c 4.3. Příklad. Z rekurentní formule 4.2 okamžitě plyne: BQ = 1, Bi = 1, B2 = 2, B3 = 5, B4 = 15, B5 = 52, B6 = 203, ... 4.4. Poznámka. Podle příkladu 4.3 existuje na 4-prvkové množině {a, h, c, d} celkem 15 rozkladů. S uspořádáním popsaným v úvodu paragrafu tvoří tyto rozklady úplný svaz, jehož hasseovský diagram je na obr. 4.3. Obr. 4.3: Svaz rozkladů čtyřprvkové množiny Podle počtu prvků v jednotlivých třídách výše uvedeného rozkladu je nej-větší prvek prvkem ..typu" 4, nej menší prvek je prvkem typu 1+1+1+1, pod nej větším prvkem leží rozklady typu 1+3, respektive 2+2 a konečně nej menší prvek pokrývají prvky typu 1+1+2. Tento intuitivně zcela zřejmý popis nyní precizujeme. 4.5. Definice, Buď A konečná množina. Nechť rozklad A obsahuje A., tříd mohutnosti ;',(/ = 1, ...,/<) a neobsahuje třídu o mohutnosti větší než k. Pak říkáme, že A je rozklad typu 1 + 1 + • • • + 1 + 2 + 2 + • • • + 2 + • • • + A: + /: + • • • + A- --„-' '-„-'--v-< nebo též typu lkí2l2 ...kkk. 34 /. KOMBINATORIKA 4.6. Příklad. Rozklad množiny {1, 2, 3, 4, 5, 6} na třídy {1}, {2, 4}, {3, 6}, a {5} je rozklad typu 1+1+2+2 nebo též typu 1222. 4.7. Věta. Počet rozkladů typu lXl2Ä2 ... kXk na n-prvkové množine je roven číslu _nl_ (1!)*' ■(2!)x2...(Jfc!)**-Ai!-A.2!...A.*! pokud X i + 2x2 + • • • + kXk = n. Je-li k[ + 2X2 + • • • + kXk ý n, je počet rozkladu uvedeného typu roven nule. Důkaz. Je zřejmé, že rozklad typu l1' 2Xl ... kkk na n-prvkové množině existuje právě tehdy, když X \ + 2X2 + ■ - • + kXk = n, neboť počet prvků jednotlivých tříd je roven počtu prvků celé množiny (třídy rozkladu jsou po dvou disjunktní). Určeme tedy počet rozkladů daného typu za předpokladu A i+2^2H—+kXk = n. Každý rozklad typu lXl2Ä2... kXk vznikne tak, že v následujícím schématu * k {x}.....{x}, {x, x}, ..., {x, x}, ..., {x, x,... , x}, ..., {x, x, ... , x) místo x vepíšeme postupně nějakou permutaci prvků dané «-prvkové množiny. Těchto permutací je n!. Různé permutace však neudávají nutně různé rozklady. Především udávají týž rozklad permutace, lišící se jen pořadím tříd o stejné mohutnosti. Protože tříd o mohutnosti i je A,, můžeme z těchto tříd utvořit A,! různých permutací. Celkový počet n\ všech permutací je proto nutno vydělit číslem X\\ ■ X2l ■ .. ■ ■ Xk\. Pořadí prvků v každé třídě rozkladu, která má i prvků, lze zapsat i! možnostmi. Protože těchto tříd je A,, můžeme pořadí prvků ve všech těchto třídách zapsat celkem ;!■/!■ ...■;'! = (i\)k' způsoby, aniž se a; změní množiny, tvořící jednotlivé třídy. Celkový počet permutací je tak nutno vydělit ještě číslem (1!)X| ■ (2\)Xl ■ ... ■ (kl)Xk. Odtud již plyne dokazované tvrzení. • 4.8. Příklad. Na čtyřprvkové množině má podle věty 4.7 existovat 4! (I!)2 • (2!)1 -2! • 1! ~ rozkladů typu 122'. Na obrázku 4.3 vidíme, že tomu tak opravdu je. 4.9. Definice. Bud'ten > m přirozená čísla. Označme S(n, ni) počet rozkladů n-prvkové množiny na m tříd. Čísla S(n,m) se nazývají Stirlingova čísla 2. druhu. Dále definitoricky klademe 5(0, 0) = 1, 5(0, n) = 0 pro n e N. 4. Rozklady konečných množin 3 .ť 4.10. Príklad. Z obrázku 4.3 je vidět, že například ,S'(4. 2) = 7. 4.11. Věta. Buďte X, Y neprázdné konečné množiny, \X\ = n, |F| = k, n > k. Pak pro množinu surj (Fx) vŕecA surjekcí X na Y platí |surj (Fx)| = fc! • S(n.k). Důkaz. Buď /: .Y —- Y surjekce. Tato surjekce určuje rozklad množiny X na k tříd; jednotlivé třídy jsou úplné vzory prvků množiny Y. Každý rozklad množiny Ä' na k tříd přitom určuje k\ surjekcí A' na ľ. Odtud plyne tvrzení. • 4.12. Věta. S (n + 1, k) = S(n, k — 1) + k ■ S(n, k) pro 1 < k < n, S(n,n) = S(n, 1) = 1. Důkaz. Představme si všechny rozklady (n+1)-prvkové množiny {a\, ..., a„+\} na k tříd. V některých rozkladech tvoří prvek an+\ jednoprvkovou třídu. Těchto rozkladů je S(n, k — 1). Ve všech ostatních rozkladech je prvek an+\ prvkem některé třídy o více prvcích. Prvek an+\ je tedy v těchto rozkladech přidán k některé třídě rozkladu množiny {a\, ..., an} na k tříd. Těchto rozkladů je S(n, k) a prvek an+\ můžeme přidat ke kterékoliv z uvedených k tříd. Odtud plyne dokazovaná formule. « 4.13. Poznámka. Rekurentní formule z věty 4.12 nám umožňuje postupně počítat hodnoty čísel S(n, k). V tabulce na straně 171 uvádíme některé hodnoty Stirlingových čísel druhého druhu. Této tabulce se také říká Stirlingův trojúhelník. Z Pascalova a Stirlingova trojúhelníka lze snadno odvodit tabulku 4.2, shrnující výsledky tvrzení 3.8, 3.12 a 4.11 o zobrazeních «-prvkové množiny do množiny k-prvkové. V diagonále následující tabulky je tučně vytištěn počet nl bijekcí mezi n-prvkovými množinami. Nad diagonálou (n < k) je uveden počet injekcí (k)„ = n\( ) a pod diagonálou (n > k) je počet surjekcí k \ ■ S(n, k). 36 /. KOMBINATORIKA k = 1 2 3 4 5 6 ... n = 1 1 2 3 4 5 6 ... 2 1 2 6 12 20 30 ... 3 1 6 6 24 60 120 ... 4 1 14 36 24 120 360 ... 5 1 30 150 240 120 720 ... 6 1 62 540 1560 1800 720 ... Tab. 4.2: Tabulka počtu injekcí, surjekcí a bijekcí 4.14. Věta. Pro všechna reálná x a každé přirozené n platí n x" = Y^S(n,k)(x)k. Důkaz. Nechť \A\ = m < \X\ = n. Počet zobrazení X do A je podle příkladu 3.21 roven číslu m". Buď nyní f: X —> A libovolné zobrazení. Pak je / surjekce X na množinu f (X) = A\. Je-li = k, existuje podle věty 4.11 celkem kl ■ S(n, k) surjekcí množiny X na množinu A\. Avšak ^-prvkových (m\ (m\ I. Odtud plyne, že existuje 11 • k\ ■ S(n, k) surjekcí X na ^-prvkovou podmnožinu v A. Dokázali jsme tak, že - / \ " n Polynomy w-tého stupně x" a Yl S(n, k(x)k se tedy shodují v n + 1 hodnotí tách 0,1.....n. Jak z matematické analýzy víme, plyne odtud rovnost těchto polynomů. • 4.15. Věta. S(n + l,k) = J2Ín^jS(i,k- 1). i=0 Důkaz. Představme si rozklady (n + l)-prvkové množiny {«],..., a„+i} na k tříd. Když v každém z těchto rozkladů vyškrtneme třídu obsahující prvek a„+i, zůstanou nám právě všechny rozklady všech množin K C {a\.....a„] nafc — 1 tříd. Odtud plyne dokazovaná formule. • 4. Rozklady konečných množin 37 4.16. Poznámka. z definice je zřejmá souvislost Bellových čísel se Stirlingo-vými čísly 2. druhu; platí n Bn = S{n, 1) + S(n, 2) + • • • + S(n, n) = S(fl, k). k=l Odtud a z věty 4.15 lze snadno odvodit rekurentní formuli z věty 4.2. Když pro jednoduchost položíme S(n, k) = 0 pro k > n (jak je to ostatně vyznačeno již v tabulce ma straně 171), platí OO OO II / \ Bn+l = J2s^n + l^) = EE • ■5(/-* - n = k=\ k=l i=0 ^ ' i=0 x 7 \k=l / i=0 v 7 Pro Bellova čísla je známa řada důležitých vztahů. Na ukázku si odvoďme alespoň dva z nejběžnějších. 4.17. Věta. Pro každé reálné číslo t platí ca E ;i=0 n\ ť'=eie'-l). Důkaz. Uvedený vztah odvodil E. T. Bell již v roce 1934. My však uvedeme elegantní důkaz, který v roce 1964 uveřejnil americký matematik G. C. Rota. Označme F množinu všech reálných funkcí > kde ]c < °°- Definujeme-li sčítání funkcí z F a násobení těchto funkcí reálnými čísly obvyklým způsobem, utvoříme zřejmě z F vektorový prostor. Připomeňme si, že když V je nějaký vektorový prostor a / : V —> K je zobrazení (takovým zobrazením se říká funkcionál), nazývá se / lineární funkcionál, jestliže pro každé vektory u, v a každá reálná čísla a. platí f(au + py) = af(u) + 0f(v), OO Nyní ukážeme, že zobrazení L: F -» R definované vztahem L(n - * (ě n=0 \n=0 v 7 / \n=0 / oc „ ^-f n! 4.18. Poznámka. V uvedeném důkazu jsme využili zobecněné binomické věty. Podrobněji o ní budeme, současně s dalšími podrobnostmi o mocninných řadách, hovořit v paragrafu 9. V následující větě ukážeme rozvoj Bellových čísel v nekonečnou řadu. 4.19. Věta. (G. Dobinski) 1 „ 2" 3" 4" 1 ^ kn bn+l = -(1" + — + — + — + ...) = -> -. e 1! 2! 3! e ^ (k -1)! Důkaz. Platí fc! ~ (k-n)\ ~ 2-j tf. ~ ^ k\ ' k=Q k=n k=n k=0 (neboť pro k = 0,..., n — 1 je (&)„ = 0). Pro funkcionál l definovaný v důkazu věty 4.17 platí: oc í[Wn] = i = - > «tí kl 4. Rozklady konečných množin 39 oo Pro funkci ků). Před jeho formulací si ukážeme, v čem spočívá jeho podstata. Buďte Mi, Mi libovolné konečné množiny. Pak zřejmě platí |M] UM,| = \Mi\ + \M2\ - |Mj nM2|. Pro tři množiny je zřejmé, že mohutnost jejich sjednocení obecně neobdržíme, když od součtu jejich mohutností odečteme mohutnosti průniků všech dvojic těchto množin. Některé prvky bychom totiž mohli odečíst dvakrát - a sice ty prvky, které leží v průniku všech tří těchto množin. Zřejmě tak platí |MiUM2UM3| = |Mi| + |M2| + |M3| - |Mi n M2\ - \Ml n M3| - -\M2 n M3| + |Mi n m2 n m3| . Zobecněním popsaného procesu obdržíme následující princip inkluze a exkluze. 5.1. Věta. Buď dána konečná množina M. Nechť prvky množiny M mohou mít vlastnosti a \, a2, ..., an. Symbolem M (at], aÍ2, ..., a,t, a'^, a'-2, ..., a j) označme počet všech prvků množiny M, které mají vlastnosti a,,, a,-2, ..., aik a nemají žádnou z vlastností a,-,, aj2,..., -= 1---1----+ ••• = lim pn. n=0 Odtud plyne, že lim qn = 1--(= 0,632 121 ...). Navíc posloupnost (q„)™=1 n—i-oo e konverguje „velmi rychle", neboť například qi = 1; q2 = 0,5; q3 = 0,6; q4 = 0,625; q5 = 0,63; ...; qs = 0,632 11... Odtud plyne překvapující zjištění, že pravděpodobnost qn se s rostoucím n prakticky nemění. 5.7. Příklad. Metodou inkluze a exkluze lze vyřešit i jiný známý kombinatorický problém, tzv. úlohu o hostech (v literatuře běžně nazývanou Probléme des Ménages). Formulace tohoto problému je jednoduchá: Kolika způsoby můžeme rozsa-dit kolem kulatého stolu n manželských párů tak, aby se muži a ženy pravidelně střídali a žádní dva manželé přitom neseděli vedle sebe? Nejprve se dohodněme, která rozesazení budeme považovat za různá. Úlohu vyřešíme nejprve tak, ža dvě rozesazení budeme považovat za různá, existuje-li alespoň jedna židle, která je v těchto rozesazeních obsazena různými osobami. Když tento výsledek vydělíme číslem 2n, nerozlišujeme rozesazení, z nichž jedno vzniklo „pootočením" druhého. Všechna rozesazení rozdělme do 2 • n \ disjunktních skupin podle toho, jak se rozesadí ženy. Nyní určíme počet rozesazení v těchto skupinách. Nechť jsou tedy ženy již jistým způsobem rozesazeny. Hledáme počet r(n) všech rozesazení mužů, při nichž žádný muž nesedí vedle své ženy. Všech možných rozesazení mužů je n\. Označme ar následující vlastnost těchto rozesazení: í-tý muž sedí vedle své ženy. Pak platí: n r (n) = n\ - ^M(a,-) + ^M(aŕ,o?j) - ^ M(a;, ajt ak) + ... i=l i 1 označme n je tento počet roven nule, pro k = 1 nebo k = n je pak roven jedné. Pro 2 < k < n — 1 je těchto možností více. Musíme se však dohodnout, která rozložení čísla n budeme považovat za různá. Konkrétně jde o to, zda nám záleží nebo nezáleží na pořadí sčítanců. Nejprve vyřešíme jednodušší případ, kdy pořadí sčítanců rozlišujeme. 6.1. Definice. Kompozicí čísla n na k sčítanců rozumíme každou uspořádanou k-úci [*!,..., xk] přirozených čísel takovou, že X\ + %2 + ■ ■ • + xk = n. Počet všech kompozicí čísla n na k sčítanců označme K(n,k). (Termín kompozice zavedl Percy A. MacMahon.) 6.2. Věta. Pro každá přirozená čísla n, k platí X2 > ... > xk. Předpokládejme nyní, že n = x\ + X2 + • ■ ■ + xk je rozklad čísla n na k sčítanců. Pak n - k = (xi - 1) + (x2 — 1) + • • ■ + (xk — 1) je rozklad čísla n — k na k nebo méně sčítanců (neboť některá x, se mohla rovnat jedné). Přitom uvedené přiřazení (x\, ..., xk) -> (x\ — l, ..., xk — 1) je evidentně bijekcí množiny všech rozkladů čísla n na k sčítanců na množinu všech rozkladů čísla n — k na nejvýše k sčítanců. Dokázali jsme tak, že platí následující věta. n +k — 1 k - 1 3 + 2 + 2 3 + 3+1 2+3+2 3+1+3 2+2+3 1+3+3 50 /. KOMBINATORIKA 6.7. Věta. k p(n,k) = )/p(n - k, i); p(n, 1) = p(n,n) = 1. i=i 6.8. Poznámka. Uvedená rekurentní formule nám umožňuje postupně počítat všechny hodnoty p(n, k). Tyto hodnoty pro čísla n, k = 1,..., 10 uvádíme v tabulce na straně 169. k 6.9. Poznámka. Číslo q (n, k) = ^p(n,i) udává počet rozkladů čísla n na i=i nejvýše k sčítanců. Přitom lze číslo q(n, k) najít přímo mezi čísly p(x, y). Podle věty 6.7 totiž zřejmě platí q(n, k) = p(n + k, k), takže například q(6, 3) = p(9, 3) = 7. V roce 1942 dokázal F. C. Auluck, že pro velká n je q{n,k) přibližně 1 (n - 1\ rovno číslu — .To potvrzuje vcelku očekávanou skutečnost, že počet k\ \k — 1/ kompozicí čísla n na k sčítanců je přibližně k\ krát větší než počet rozkladů čísla n na nejvýše k sčítanců. Číslo p(n) := q(n, n) ^= VJ p(n, k)^j udává počet všech rozkladů čísla n. Podle výše uvedeného platí p(n) = p(2n, n), takže i čísla p(n) lze zjistit z tabulky čísel p(n,k). (Kromě toho je p{n) samozřejmě rovno součtu všech čísel v ra-tém sloupci této tabulky.) Tabulka čísel p(n) je uvedena v příloze na straně 170. Ztabulky čísel p(n) je zřejmé, že již pro poměrně maléhodnoty je výpočet hodnot p(n) pomocí rekurentní formule pro p(n,k) zdlouhavý a komplikovaný. (O výhodnějším způsobu výpočtu hodnot p(n) se zmíníme v paragrafu 9 - viz větu 9.6.) Vzhledem k tomu, že není znám jednoduchý explicitní vzorec pro přímý výpočet čísel p(n, k), respektive p(n), byly odvozeny alespoň vztahy popisující asymptotické chování těchto čísel. Tak například Hardy aRamanujan odvodili, že FŽň 4n lgp(n) ~ ti J — -lg-7=. V 3 V3 6. Rozklady přirozených čísel na sčítance 51 V roce 1937 odvodil H. Rademacher, že p(n) lze vyjádřit jako součet jisté konvergentní nekonečné řady. Pro ukázku jeho výsledek uveďme: cc P(n) = ^2,lq(n) ■ ýq(n), q=\ kde r— , sinh Iq a : }2 JER 3 q 2 dn ľ i 'n~24 kde it)p 9 je 24. odmocnina z jedné a /? probíhá všechna celá čísla nesoudělná s q menší nebo rovna číslu q. 6.10. Poznámka. V řadě úvah o rozkladech přirozených čísel na sčítance jsou velmi užitečné tzv. Ferrersovy diagramy, v nichž každému sčítanci odpovídá řádek bodů v rovině. I bez přesné definice je jistě vše zřejmé z následujícího příkladu: o o o o o o o o 5 + 4+1 + 1 —> o o Je-li a rozklad čísla n, pak tzv. adjungovaný rozklad a* k rozkladu a obdržíme tak, že Ferrersův diagram rozkladu a přečteme, jednoduše řečeno, po sloupcích. Tak například adjungovaný rozklad k výše uvedenému rozkladu 5 + 4+1 + 1 je rozklad 4 + 2 + 2 + 2+1. Platí-li a = a*, nazývá se rozklad a samoadjungovaný. Pokusme se nyní zjistit, kolik má číslo n samoadjungovaných rozkladů. Nejprve uvažme následující jednoduchý příklad. Samoadjungovaným rozkladem čísla 13 je například rozklad 5+3+3+1+1. Ferrersův diagram tohoto rozkladu je následující: o—o—o—o—o 0 o—o 1 ! 0 o o 1 ! o 52 I. KOMBINATORIKA Když sečteme v uvedeném diagramu navzájem propojené body, obdržíme rozklad 9+3+1. Zamyslíme-li se nad tím, jak rozklad 9+3+1 vznikl, uvědomíme si jistě okamžitě, že jde zákonitě o rozklad s navzájem různými lichými sčítanci (pokud byl samozřejmě původní rozklad samoadjungovaný). Když si nyní navíc uvědomíme, že obrácením uvedeného postupu zase naopak každému rozkladu čísla n na navzájem různé liché sčítance přiřadíme evidentně samoadjungovaný rozklad čísla n, přičemž popsané zobrazení je zřejmě bijektivní, je jasné, že jsme dokázali následující tvrzení. 6.11. Věta. Počet samoadjungovaných rozkladů čísla n je roven počtu rozkladů čísla n na navzájem různé liché sčítance. Pomocí Ferrersových diagramů lze okamžitě - pouhou záměnou řádků a sloupců - odvodit i další tvrzení. 6.12. Věta. Počet rozkladů čísla n na sčítance nepřevyšující číslo k je stejný jako počet rozkladů čísla n na nejvýše k sčítanců. Na množině F všech rozkladů (všech přirozených čísel) je obvyklé definovat vhodné uspořádání následujícím způsobem. (Pro formální jednoduchost nyní ztotožníme rozklad a\ > a2> ... > a^s posloupností (aj,..., at, 0,..., 0,...).) 6.13. Definice. Buď Y množina všech nerostoucích posloupností nezáporných celých čísel, jejichž součtem je přirozené číslo (tj. všechny členy každé posloupnosti jsou od jistého indexu i > 2 rovny nule). Definujeme relaci < na Y tak, že pro libovolná a = (a,,)^, = (A,)~, platí: a < at < bi pro každé i e N. Okamžitě z definice je zřejmé, že platí následující věta. 6.14. Věta. Relace < definovaná v 6.13 je uspořádání na množině Y a (F, <) je svaz, v němž aVyS = (max{aub]},max{a2,b2},...) oe A /3 = (min {ax, b\), min {a2, b2}, ...). 6.15. Poznámka. Svaz (F, < ) je obvykle nazýván Youngův svaz. Část tohoto svazu je na obr. 6.4. Počet prvků „výšky" n v (F, <) je zřejmě p(n). Snadná je též odpověď na otázku, kolik prvků prvek a e F pokrývá a kolika prvky je pokryt. Je zřejmé, že když rozklad a obsahuje k různých sčítanců, pak a pokrývá k prvků a je pokryt k + 1 prvky. 6. Rozklady přirozených čísel na sčítance 53 n= 1 Obr. 6.4: Youngův svaz Poznámky a cvičení 1. Srinivasa Ramanujan dokázal řadu vlastností čísel p(n, k) a p(n), například skutečnost, že pro každé n e No je p(5n + 4) násobkem 5. Ověřte tuto skutečnost pro n = 0,1, 2. 2. Označme / (n) počet rozkladů čísla n, jejichž každý sčítanec je mocninou čísla 2 (včetně 2° = 1). (a) Vypočtěte t(n) pro 1 < n < 6. (b) Dokažte, že t(2n + 1) = ř(2n). (c) Dokažte, že ř(«) je sudé pro všechna n > 1. 3. Již Galileo Galilei řešil problém, proč při házení kostkami nepadá stejně často součet 9 a 10. a) Ukažte, že čísla 9 a 10 mají stejný počet rozkladů na tři sčítance, které jsou nejvýše rovny 6. b) Zdůvodněte, proč přesto nepadá součet 9 stejně často jako součet 10. 4. Dokažte, že p(2r + k, r + k) = p(2s + k, s + k) pro každé r, í e N. 5. Dokažte, že číslo p(r + k, k) je rovno: 54 /. KOMBINATORIKA a) počtu rozkladu čísla r + I j na & navzájem razných sčítanců; b) počtu rozkladu čísla r na sčítance nejvýše rovné Ä. 6. Pomoci Ferrersových diagramu dokažte rovnost p(n) = p(2n, n). 7. Hardy aRamanujan vr. 1919 dokázali, že Porovnejte hodnotu p (70) podle tohoto tvaru s přesnou hodnotou (viz tabulku na straně 170). 7. Rozdělování do přihrádek 55 7 Rozdělování do přihrádek V tomto paragrafu v podstatě jen shrneme některé výsledky odvozené již dříve, přeformulujeme je však do jazyka tzv. „přihrádkové" kombinatoriky. Mnohé úlohy lze totiž převést na následující problém: kolika způsoby lze n předmětů rozdělit do k přihrádek? Vzhledem k tomu, že jak předměty, tak přihrádky mohou být vzájemně rozlišitelné, respektive nerozlišitelné, a na rozmístění mohou být kladeny další omezující podmínky (např. aby všechny přihrádky byly neprázdné, aby počet prvků v různých přihrádkách byl různý apod.), lze úloh tohoto typu zformulovat celou řadu. Řešení některých z nich může být velmi komplikované. Četné aplikace těchto výsledků lze najít i mimo matematiku, např. ve statistické fyzice. Ještě před řešením úloh uvedeného typu si zformulujeme následující evidentní tvrzení, známé jako Dirichletův princip. 7.1. Věta. 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. Jakkoliv je Dirichletův princip jednoduchý, umožňuje řešení řady úloh. Řadu zajímavých příkladů lze najít například v [7]. 7.2. Příklad. Dokažte, že když v obdélníku o rozměrech 6 cm x 4 cm vybereme libovolně 25 bodů, pak mezi nimi existují alespoň dva, které mají vzdálenost menší než 1,5 cm. Leží-li dva body v jednotkovém čtverci, je jejich vzdálenost rovna nejvýše což je méně než 1,5. Kdybychom tedy chtěli 25 bodů rozmístit tak, aby každé dva měly vzdálenost alespoň 1,5 cm, mohli bychom do každého čtverce o straně 1 cm ležícího v daném obdélníku umístit nejvýše jeden bod. Obdélník však lze pokrýt nejvýše 24 takovými čtverci. Podle věty 7.1 tedy mezi libovolnými 25 body jsou alespoň dva ze stejného čtverce. 7.3. Věta. Buďte k, n libovolná přirozená čísla. Pak lze n rozlišitelných předmětů rozmístit do k rozlišitelných přihrádek právě k" způsoby. Důkaz. Je-li X = {xy, ..., x,,} množina n předmětů a Y = {y y,..., yk} množina k přihrádek, pak je evidentní, že rozdělení předmětů do přihrádek je totéž jako zobrazení množiny X do množiny Y. (Prvek x, se zobrazí na tu přihrádku, do které je umístěn.) Odtud a z věty 3.21 okamžitě plyne tvrzení. • 56 /. KOMBINATORIKA Při popsaných rozmístěních předmětů do přihrádek existují samozřejmě přihrádky, které mohou zůstat prázdné. Chceme-li předměty X rozmístit do přihrádek Y tak, aby žádná přihrádka nezůstala prázdná, je to zřejmě totéž, jako sestrojit surjekci X na Y. Odtud, z věty 4.11 a z příkladu 5.9 plyne následující tvrzení. 7.4. Věta. Buď dáno n rozlišitelných předmětů a k rozlišitelných přihrádek, n > k. Počet rozdělení těchto předmětů do přihrádek, při nichž žádná přihrádka nezůstane prázdná, je roven číslu k\S(n,k)=J^(-l)i(k\k-i)n. i=0 ^ř ' Podobně z důsledku 3.8 plyne 7.5. Věta. Bud' dáno n rozlišitelných předmětů a k rozlišitelných přihrádek, k > n. Počet rozdělení předmětů do přihrádek, při nichž každá přihrádka obsahuje nejvýše jeden prvek, je roven číslu (*)„=*• (ifc-1) •....(*-n+ 1). Nyní uvažujme případ, kdy máme opět k rozlišitelných přihrádek avšak n vzájemně nerozlišitelných předmětů. Uvědomíme-li si, že za předměty můžeme vzít například cifry 1 (v počtu n) a přihrádky můžeme označit x\,..., xk, je okamžitě zřejmé, že tato úloha je ekvivalentní s určením počtu kompozicí čísla n. Chceme-li přitom, aby v každé přihrádce bylo alespoň r předmětů, můžeme nejprve do každé přihrádky r předmětů vložit a zbývajících n — kr předmětů pak rozdělit libovolně. Odtud, z věty 6.2 a poznámky 6.3 okamžitě plyne následující tvrzení. 7.6. Věta. Buďte k,n libovolná přirozená čísla. Pak lze n nerozlišitelných předmětů rozmístit do k rozlišitelných přihrádek právě V k-í ) způsoby. Chceme-li, aby v každé přihrádce bylo alespoň r předmětů, je těchto možností ín-kr +k-\\ \ k-í J' Mají-li zejména být všechny přihrádky neprázdné, je možností celkem 7. Rozdělování do přihrádek 57 Nyní uvažme případ, kdy jsou přihrádky nerozlišitelné. Nechťtedy je dáno k nerozlišitelných přihrádek a n rozlišitelných předmětů. Rozdělit tyto předměty do přihrádek tak, aby právě p těchto přihrádek bylo neprázdných, evidentně značí utvořit rozklad na množině předmětů na právě p tříd. Podle definice 4.9 udává počet těchto rozkladů Stirlingovo číslo 2. druhu S(n, p). Odtud okamžitě plyne 7.7. Věta. Počet rozmístění n rozlišitelných předmětů do k nerozlišitelných přihrádek je roven číslu k S(n, 1) + S(n, !) + ■■■ + S(n, k) = J^ s(n> 0- 1=1 Chceme-li zejména, aby všechny přihrádky byly neprázdné, je těchto možností právě S(n, k). Zbývá nám poslední možný případ, kdy jsou nerozlišitelné i předměty i přihrádky. Protože za předměty můžeme vzít cifry 1 a za přihrádky sčítance, jejichž pořadí nerozlišujeme, je tento případ evidentně popsán pomocí rozkladů přirozených čísel. Odtud a z věty 6.9 okamžitě plyne následující tvrzení. 7.8. Věta. Je-li dáno n nerozlišitelných předmětů, lze je do k nerozlišitelných přihrádek rozdělit k p(n, 1) + p(n, 2) + • • • + p(n, k) = p(n, i) = p(n + k, k) 1=1 způsoby. Chceme-li, aby všechny přihrádky byly neprázdné, je těchto možností právě p(n, k). 7.9. Poznámka. Uvedené výsledky můžeme shrnout do tabulky 7.3, v níž je uveden počet všech rozdělení (bez jakýchkoliv omezujících předpokladů). 7.10. Příklad. Ilustrujme si rozdíly mezi počty možností v jednotlivých případech například pro 10 předmětů a 4 přihrádky. (a) k" = 410 = 1 048 576, ín + k-\\ /13\ <»( t_, hůř286- 58 /. KOMBINATORIKA Počet všech n předmětů rozmístění rozlišitelných nerozlišitelných k přihrádek rozlišitelných k" /n+k-l\ \ k-l ) nerozlišitelných k i=i Tab. 7.3: Umísťování předmětů do přihrádek k (c) £ 5(n, i) = 5(10. 1) + 5(10, 2) + 5(10, 3) + 5(10, 4) = i=i = 1 + 511 + 9 330 + 34 105 = 43 947, (d) £ p(n, i) = p(lQ, 1) + p(l0, 2) + p(ÍO, 3) + p(l0, 4) =23. i=l Poznámky a cvičení 1. Do 15 přihrádek je rozmístěno 100 míčků. Dokažte, že alespoň dvě přihrádky obsahují stejný počet míčků. 2. Dokažte, že v každé skupině (alespoň dvou) lidí existují alespoň dva lidé, kteří znají stejný počet členů skupiny. (Návod: Uvažujte množinu lidí, kteří neznají nikoho). 3. Ukažte, že mezi sedmi různými přirozenými čísly vždy existují čísla x, y taková, že x + y nebo x — y je dělitelné deseti. 4. 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? (2 000 376) 8. Řešení rekurentních formulí 59 8 Řešení rekurentních formulí S rekurentními formulemi jsme se setkali již několikrát. Tak například ve větě 4.2 jsme odvodili rekurentní formuli pro výpočet Bellových čísel Bn, ve větě 6.7 pak rekurentní formuli pro výpočet počtu p(n,k) rozkladů čísla n tiel k sčítanců. Mezi právě uvedenými formulemi je - kromě jiného - jeden zásadní rozdíl. Čísla B„ závisejí na jediné hodnotě (tj. n), čísla p(n, k) na dvou hodnotách (tj. n, k). V tomto paragrafu se budeme zabývat formulemi prvního z uvedených typů, tj. formulemi pro výpočet členů posloupnosti pomocí předcházejících členů. Předpokládejme, že je tedy dána rekurentní formule pro výpočet hodnot /(«). Obecně nám taková formule umožňuje výpočet členu f(n +1), známe-li hodnoty /(l), ... , f(n) (respektive /(O), ..., f{n) apod). Jednotlivé formule se však mohou lišit tím, kolik předcházejících členů fakticky potřebujeme k výpočtu členu následujícího. Tak například ve formuli 4.2 pro výpočet čísel B„ potřebujeme k určení B„ všechny členy předcházející. Ve formuli f(n + 2) = f(n + 1) + /(«) potřebujeme jen předcházející dva členy. Má tedy smysl následující definice. 8.1. Definice. Řekneme, že rekurentní formule pro výpočet hodnot / (n) je řádu k e N, jestliže pro každé n e N lze /(n +k) určit pomocí /(n). /(yi + 1), ..., f(n+k — 1), přičemž k je nejmenší přirozené číslo s uvedenou vlastností. 8.2. Příklad. (a) f(n + 3) = f(n + 2) - log /(«) je formule 3. řádu, (b) f(n + 2) = f(n + 1) + f(n) je formule 2. řádu, (c) Tn+i = J2 Tk není formule konečného řádu. k=0 8.3. Definice. Buď dána rekurentní formule A-tého řádu pro výpočet čísel /(«), n e N. Řekneme, že posloupnost (a,,),^ je řešením této rekurentní formule, jestliže pro každé / e N dostaneme po dosazení čísel za f(n+j), j = 0, ..., k, identitu. 60 I. KOMBINATORIKA 8.4. Příklad. Posloupnost (2")^j je řešením rekurentní formule 2. řádu f(n + 2) = 3- f(n + l)-2- f(n), neboť pro všechna n e N platí 2«+2 _ 3 , 2"+l -2-2". 8.5. Poznámka. Rekurentní formule k-tého řádu zřejmě může obecně mít nekonečně mnoho řešení, neboť prvních k členů posloupnosti, která je řešením, můžeme volit zcela libovolně. Stejně tak se ovšem může stát, že rekurentní formule nemá řešení žádné. Nyní se bude zabývat otázkou, zda lze alespoň v některých případech pro danou rekurentní formuli určit člen f(n), aniž bychom museli počítat postupně všechny členy předcházející. Uvidíme, že se nám to podaří pro speciální typ formulí - pro tzv. lineární rekurentní formule s konstantními koeficienty. 8.6. Definice. Rekurentní formule tvaru f(n +k) =a\ ■ f(n + k — 1) + a2 ■ f(n + k — 2) + ---+ak- f(n), (8.1) kde a\,... ,ak jsou reálná čísla, ak 4 0> se nazývá lineární rekurentní formule k-tého rádu s konstantními koeficienty. 8.7. Věta. Jsou-li posloupnosti (fi(n))™=i , {f2(n))^ , .. •, (/í(n))~, řešením formule 8.1, je také jejich libovolná lineární kombinace (ci/i(rt) + c2f2(n) + ■■■ +csfs(n))™=l řešením formule 8.1. Důkaz. Je zřejmé, že stačí dokázat, že každá lineární kombinace libovolných dvou řešení formule 8.1 je opět řešením formule 8.1. Nechť tedy (gin))^, jsou řešení formule 8.1, tj. platí g(n+k) = atg(n+k-l) + a2g(n + k-2) + ---+akg(n) h(n + k) = a\hin + k — 1) + a2h(n + k — 2) + • • • + akh(n) pro všechna n e N. Potřebujeme dokázat, že pro libovolná čísla c\,c2 e R je (r(n))™=l, kde r{n) = c\g(n) + c2h(n), také řešením formule 8.1. 8. Řešení rekurentních formulí 61 Pro každé n € N platí: r (n + k) = C[g(n + k) + c2h(n + k) = c\[aig(n +k — 1) + • ■ - +aiig(n)\ + +c2[aih(n + k — 1) + • • • + akh(n)] = = a\[c\g{n + k — 1) + C2«(n + /c — 1)] + ■ • ■ + ajt[cig(n) + c2h(n)] = = a\r(n + k — 1) + • • • + fljtr(n), což znamená, že (/"(n))^ je řešením formule 8.1. • 8.8. Poznámka. Zdůrazněme, že větu 8.7 jsme dokázali pro speciální typ rekurentních formulí. Snadno lze ukázat, že když formule není lineární, pak lineární kombinace daných řešení vůbec nemusí být řešením dané formule. 8.9. Příklad. Mějme dánu rekurentní formuli 2. řádu /(« + 2) = 5./(n + l)-6-/(«). Pouhým dosazením lze snadno ověřit, že posloupnosti (2")^j a (3")^ jsou lineárně nezávislá řešení dané formule. Nyní ukážeme, že každé řešení (§(n))T=i zadané formule je vhodnou lineární kombinací uvedených dvou řešení, tj. existují konstanty c\, c2 e R takové, že pro každé n € N platí: g(n) = (Cl.2" + c2-3Ä)~i- Jak tyto konstanty nalezneme? Protože řád dané formule je 2, je řešení {g{n))%i jednoznačně určeno volbou hodnot g{\) ag(2). Nechť tedy g{\) = a, g(2) = h. Potřebujeme dokázat, že existují konstanty c\, c2 takové, že 2ci -f 3c2 = a 4c i + 9c2 = b Tento systém rovnic má však právě jedno řešení 3a — b b — 2a Ct =-, c2 =-. 2 3 8.10. Poznámka. Je zřejmé, že množina všech posloupností reálných čísel se sčítáním definovaným po složkách a s obvyklým násobením reálnými čísly tvoří vektorový prostor nekonečné dimenze na R Z věty 8.7 plyne, že všechna řešení lineární rekurentní formule daného řádu tvoří podprostor tohoto prostoru. V příkladu 8.9 jsme ukázali, že dimenze vektorového prostoru všech řešení zadané rekurentní formule druhého řádu je 2; posloupnosti (2")^j a (3")^j tvoří bázi tohoto vektorového prostoru. 62 7. KOMBINATORIKA Postup uvedený v příkladu 8.9 lze snadno zobecnit na případ lineární rekurentní formule s konstantními koeficienty libovolného řádu k e N. Libovolné řešení takové rekurentní formule je totiž jednoznačně určeno hodno- tami g{\), g(2), ... , g(k). Existují-li lineárně nezávislá řešení pak jistě existují konstanty a, c%.....Ck 6 M takové, že pro každé n e N platí: g(n) = c1f1(n) + --- + ckfk(n). K tomu totiž stačí ukázat, že systém rovnic ci/i(l) + c2/2(l) + ...+ctA(l) = g(l) c1/,(2) + c2/2(2) + ---+Q/r(2) = g(2) c\Mk)+c2f2(k) + --- + ckfk(k) = g(k) má řešení. Z lineární nezávislosti posloupností (/i(n))~i,(/2(n))^i,...,(/t(n))~, však snadno plyne, že daný systém rovnic má právě jedno řešení c\, c2,..., c*. V dalším (viz důsledek 8.19) ukážeme, že takový systém lineárně nezávislých řešení vskutku existuje. Celkem se takto snadno odvodí následující tvrzení. 8.11. Věta. Dimenze podprostoru všech řešení lineární rekurentní formule s konstantními koeficienty je rovna řádu této formule. 8.12. Poznámka. Je-li dána nějaká rekurentní formule, může a nemusí se stát, že existuje posloupnost (g (n, C\, c2,..., Cjt))~j obsahující parametry c\, ci,..., Ck tak, že platí: (a) Dosadíme-li za parametry c\ ,cj,... ,ck libovolná reálná čísla, je vzniklá posloupnost řešením dané rovnice. (b) Každé řešení dané rekurentní formule lze získat vhodnou volbou parametrů ci, c2,..., Ck ve výše uvedené rekurentní posloupnosti. Pokud posloupnost (g (n, c\, c2,..., ck))™=x s uvedenými vlastnostmi existuje, nazývá se obecné řešení dané rekurentní formule. Z výše uvedeného tedy plyne, že platí: 8. Řešení rekurentních formulí 8.13. Věta. Nechť je dána lineární rekurentní formule f(n + k) = a\ • f(n + k — l) + a2 ■ f(n + k — 2) + • • • + ak ■ f(n) řádu k s konstantními koeficienty. Nechť (Mn))Z^ ■ ■ ■, (Mn))Zi jsou lineárně nezávislá řešení dané formule. Pak je posloupnost (g(n))^, kde pro každé n e N platí g (n) = cifi(n) + • • - + ckfk(n), obecným řešením dané rekurentní formule. Otázkou nyní zůstává, zda alespoň v některých případech obecné řešení najdeme. Buď nyní dána lineární rekurentní formule k-íého řádu s konstantními koeficienty f(n + k) = a\f(n + k — !) + ■•• +akf{n). Zjišťujeme, zda pro některé r € M je posloupnost (r")^1 řešením této formule. Pokud je posloupnost (r")^=l řešením, musí pro každé n G N platit r — a\r -!->"•+ akr . Pokud je r = 0, je tato rovnost splněna triviálně. Je-li r ^ 0, musí tedy platit k ŕ—1 r = a\ŕ + • • • + ak. Odtud a z věty 8.7 plyne 8.14. Věta. Je-li reálné číslo r řešením rovnice xk = a\xk~l + ■ ■ ■ +ak, je každá posloupnost (crn)™=v c G E libovolné, řešením- rekurentní formule 8.1. 8.15. Poznámka. Rovnice xk = a\xk~l + ■ ■ ■ + ak se nazývá charakteristická rovnice formule f(n+k) = aif(n + k- 1) + • ■ • +akf(n). Charakteristickou rovnicí rekurentní formule &-tého řádu je tedy algebraická rovnice k-tého řádu. Tato algebraická rovnice má tedy k kořenů (počítáme-li každý kořen tolikrát, jaká je jeho násobnost). Uvědomme si přitom, že když je formule 8.1 k-tého řádu, je koeficient ak nenulový, takže také všechny kořeny charakteristické rovnice jsou nenulové. 64 7. KOMBINATORIKA Odtud plyne následující věta 8.16. Věta. Buď f(n+k) = a\f{n+k — \) + - ■ ■+akf{n), ak ýO, lineární rekurentní formule k-tého řádu s konstantními koeficienty. Nechť charakteristická rovnice k k—] x = a\x + ■■■ + ak má jednoduché navzájem různé reálné kořeny r\, ..., rk. Pak obecné řešení dané rekurentní formule je tvaru {cxr1+c2rn1+--- + ckrl)^={. Důkaz. Posloupnost (cjr" + c2r2 +----i-c*fi)H_j je řešením dané formule podle vět 8.14 a 8.7. Podle poznámky 8.15 jsou všechna čísla r,, i = 1,..., k různá od nuly. Posloupnosti (r") =1, /' = 1,_____,k jsou evidentně lineárně nezávislé. Zbývá tak pouze dokázat, že každé řešení dané rekurentní formule lze získat vhodnou volbou konstant c(. To dokážeme analogicky jako v poznámce 8.10. Buď (gin))^ libovolné řešení zadané rekurentní formule. Toto řešení je jednoznačně určeno hodnotami g(l), ..., g(k). Zvolme tedy tyto hodnoty libovolně, ale pevně. Je potřeba dokázat, že systém k rovnic o k neznámých Cl, .... c* c\n + c2r2 + • • • + ckrk = g(l) c\r\ + c2r\ + ■■■ + ckr\ = g(2) cxr\ + c2rk2 + ■ ■ ■ + ckr\ = g(k) má řešení. Protože však jsou všechna čísla r, nenulová, je determinant ri ■ ■ n A 2 r2- . r\ rk r2 . • ň rovněž nenulový, takže daný systém rovnic má právě jedno řešení. • 8.17. Příklad. Vyřešme rekurentní formuli z příkladu 8.2(b): /(« + 2) = /(/i + l) + /(«). Charakteristická rovnice je tvaru 8. Řešení rekurentních formulí 65 Její kořeny jsou i ± Vš takže obecné řešení je tvaru n=\ Hledejme takové řešení {g(n))^=l zadané formule, že g(\) = 1, g(2) -- 1. Pak musí platit l+y/5 l-VŠ C\--t-C2- = 1 Tento systém rovnic má právě jedno řešení C\ = — cn = Odtud plyne, že :M = Ts 1+V5\ / 1 - V5N Toto řešení (g(n))^, je tzv. Fibonacciova posloupnost 1,1.2,3,5,8,13,21,34,...; členy této posloupnosti jsou tzv. Fibonacciova čísla, která hrají důležitou roli v různých částech matematiky i v řadě pozoruhodných aplikací. Poznamenejme pouze, že posloupnost Fibonacciových čísel je obvyklé značit symbolem (í«)n=0' Ve větě 8.16 jsme popsali, jak lze nalézt obecné řešení v případě, že charakteristická rovnice má pouze jednoduché reálné kořeny. Dobře však víme, že algebraická rovnice může mít i kořeny imaginární a násobnost kořenů může být větší než jedna. V dalším popíšeme obecně alespoň ten případ, kdy všechny kořeny charakteristické rovnice jsou reálné. 8.18. Věta. Nechť charakteristická rovnice formule 8.1 má reálný nenulový p-násobný kořen r. Pak jsou posloupnosti lineárně nezávislá řešení formule 8.1. 66 /. KOMBINATORIKA Důkaz. Je zřejmé, že pro r 0 jsou posloupnosti (rn)™=l,..., (np~l ■ r") j lineárně nezávislé. Zbývá, tak dokázat, že všechny tyto posloupnosti jsou řešením formule 8.1. Nechť tedy r je p-násobný kořen charakteristické rovnice. Potřebujeme dokázat, že pro s - 1, ..., p — 1 je (n-5 ■ řešením formule 8.1, tj. že platí (n + Jfc) 5r"+k =ax{n+k- \)srn+k-1 +a2(n + k- 2)5r"+k-2 + ■■■+ aknsr". Vydělíme-li tuto rovnici r", obdržíme (n + k)srk = a{(n+k- \)srk~l + a2(n+k- 2frk~2 + ■ ■ - + akns. Dokažme pro jednoduchost tento vztah pouze pro s = 1. Předpokládejme tedy, že číslo r 4 0 je alespoň dvojnásobným kořenem rovnice x = aix +a2x +---+ak. Z algebry víme, že dvojnásobný kořen polynomu je nutně kořenem derivace tohoto polynomu, takže r je kořenem rovnice kxk~x = a\(k — l)xk~2 +a2(k — 2)xk~3 + • • • +ak-i. Odtud plyne, že platí krk~] =ai(k- l)rk'2 + a2(k - 2)rk~3 + ---+ak-i. Za těchto předpokladů potřebujeme dokázat správnost následující rovnosti: {n + k)rk = ay(n+k — \)rk~x +a2(n + k - 2)rk~2 + ■ ■ ■ + ak(n + k — k). Upravme tuto rovnost následovně: nrk + krk = n ■ [axrk~l + a2rk~2 + • • • +ak] + ai(k — l)rk~l + +a2(k - 2)rk~2 + ■■■+ ak(k - k). Rovnost výrazů stojících u n na obou stranách rovnosti nyní plyne z toho, že r je kořenem charakteristické rovnice, rovnost zbývajících členů plyne z toho, že kořen r je alespoň dvojnásobný. • Z věty 8.18 okamžitě plyne 8.19. Důsledek. Buď f(n + k) = axf{n+k - 1) +a2f(n + k - 2) + • ■ - + akf(n) 8. Řešení rekurentních formulí 67 lineární rekurentní formule k-tého rádu s konstantními koeficienty. Nechť jsou všechny kořeny r\,.., ,rj charakteristické rovnice této formule reálné. Nechť kořen r\ je p\ -násobný, r 2 je p2-násobný, ..., r j je p j-násobný (tj. p\ + ■ ■ ■ + + pj = k). Pak obecným řešením dané rekurentní formule je posloupnost, jejíž n-tý člen je roven výrazu r\ ■ (en +cnn + ■ ■ ■ +clpínPi~]) +r'{ ■ (cn + c22n + ■ ■ ■ + c2p2nP2~i) + ... ■ ■ ■ + r] ■ (Cji + cj2n + ■■■+ cjPjnpi-1). 8.20. Příklad. Najděte obecné řešení formule f{n + 4) = 3/(« + 3) + 3f(n + 2) - ll/(« 4-1) + 6f(n). Charakteristická rovnice této formule je x4 = 3x3 +3x2 - 11.v + 6. Snadno lze ověřit, že tato rovnice má dvojnásobný kořen 1 a jednoduché kořeny —2 a 3. Obecným řešením zadané formule je tedy posloupnost (gin))^, kde g(n) = ci • 1" + c2n ■ 1" + c3(-2)" + c43" = c{ + c2n + c3(-2)" + c43n. Poznámky a cvičení 1. Název „Fibonacciova čísla" pro členy posloupnost 1,1,2, 3, 5, 8,... zavedl francouzský matematik Eduard Lucas. Tzv. Lucasova posloupnost (Ln)^0 je definována stejnou rekurentní formulí Ln+2 = Ln+\ + Ln, avšak Lo = 1, L\ = 3. Vypočtěte L\q, L2q. 2. Známý hlavolam Hanojská věž uveřejnil v r. 1833 tajemný francouzský profesor „Claus". Až v r. 1884 publikoval H. de Parville článek v časopise La Nátur, v němž uvedl, že „Claus" je anagram, který užil výše zmiňovaný Eduard „Lucas". Hlavolam tvoří tři vertikální tyčky, na nichž je navlečeno n kruhových disků s otvory uprostřed. Tyto disky mají navzájem různé poloměry a jsou poskládány do věže tak, že poloměr každého disku je větší než poloměr kteréhokoliv disku nad ním (viz obrázek 8.5). Hlavolam spočívá v tom, přenést věž na jinou tyčku tak, že v každém kroku lze přenést pouze jeden disk z jedné tyčky na druhou a nikdy přitom nesmí být položen větší disk na menší. 68 /. KOMBINATORIKA Obr. 8.5: Hlavolam Hanojská věž Parville v uvedeném článku uvádí legendu, podle níž mniši v utajovaném tibetském klášteře pracují na přemístění věže tvořené 64 zlatými disky. Ve chvíli, kdy práci dokončí, nastane konec světa. Kdy tato skutečnost Označme Hn minimální počet kroků potřebných k přemístění věže. a) Dokažte, že (íř„)^0 je řešením rekurentní formule Hq = 0, Hn+\ = = 2H„ + 1. b) Najděte obecné řešení uvedené formule. c) Vypočtěte, kolik století by trvalo přemístění věže ze 64 di sků, kdyby se na úkolu pracovalo nepřetržitě a přemístění každého disku by trvalo jednu sekundu. 3. Dokažte, že pro členy Fibonacciovy posloupnosti (F„)~j platí: nastane? (a) F2 + F4 + ■ ■ ■ + F2n = F2n+1 - 1 (b) Fi + F3 + • • • + F2„-i = Fin (c) F,2 + Fl + • • • + Fl = F„ ■ F,!+1 4. Dokažte, že Fibonacciova posloupnost (F„)~0 splňuje: a) F4 = F2 + 2Fi + F0 b) F5 = F3 + 2F2 + F c) F6 = F3 +3F2 + 3Fi + F0 d) F7 = F4 + 3F3 + 3F2 + Fi 0 Fk+n = FtF, + Ffc_iF„_] g) Fk dělí čísla F2k+] a Fu+2 8. Řešení rekurentních formulí 69 5. Takzvaná (3n + \)-funkce g: N -> N je definována vztahem g(") = n 2' 3« + 1 pro n sudé pro n liché. (8.2) Zdá se pravděpodobné, že pro každé n e N dospěje posloupnost g (n), g2(n), g3(n), ... k číslu 1. (Zatím to j e prokázáno pro všechna n < 240.) Prověřte tuto vlastnost pro počáteční hodnoty 341, 96, 104, 336, 133. 6. Buď n e N pevné. Pro každé x e N0 položme Ukažte, že: a) g(0) = n - 1 b) g(D = W-- \n c) g(2) = \n2 + \n d) g(3) = x- W + \n e) g(4) = ln4 + ln3 _ J_ 7. &-té Bernoulliovo číslo b\ (pojmenované po Jacobu Bernoullim) je definováno jako koeficient u členu n ve funkci g(k) (viz cvičení 1). Jacob Bernoulli dokázal, že [=0 x 7 Pomocí této identity ověřte vyjádření čísla g(4) ve cvičení l(e). (Tabulka Bernoulliových čísel je uvedena v tabulce na straně 171.) 8. Bernoulliova čísla splňují vztah Efn + \\ /t=o v 7 Pomocí tohoto vztahu a Pascalova trojúhelníka (strana 169) ukažte, že hs = Q,b6 = i, ž>7 = 0, b% = -i &io = ^, i>i2 = - j^o- 70 I. KOMBINATORIKA 9. Nechť pro x e R značí [x] celou část čísla x, tj. největší celé číslo n takové, že n < x. Nechť S„ je množina všech permutací n-prvkové množiny {1,2,...,«}. Řekneme, že permutace p e Sn je fluktuační, když platí: p(2k - 1) < p(2k) pro 1 < k < /?(2& + 1) > f(2A) pro 1 < k < Tak například v 54 existují následující fluktuační permutace: (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1,4), (2, 4, 1, 3), (3, 4, 1, 2). Označme f„ počet fluktuačních permutací v S„, £o = 1- Tato čísla se nazývají Eulerova. Platí: (^0 = 1,1,1,2,5, 16,61,... a) Vypište 16 fluktuačních permutací v 55. b) Platí rekurentní formule: Ukažte, že §7 = 272. 9. Vytvořující funkce 71 9 Vytvořující funkce 9.1. Poznámka. (O nekonečných řadách funkcí.) Předpokládejme znalost nekonečných číselných řad. Shrneme zde některé elementární poznatky teorie nekonečných řad funkcí. Nechť (/„(j))™! je posloupnost funkcí definovaných na množině M Cl Nekonečnou řadou funkcí nazýváme symbol 00 x] Mx) = M*) + M*) + "• + fn(x) + -.. ■ Řekneme, že tato řada konverguje v bodě xq e M, jestliže konverguje číselná oo řada £ f„(x0). oo Řekneme, že řada funkcí ^2 fn(x) konverguje na množině K, jestliže kon- «=1 verguje v každém bodě x € K. oo Součtem řady J2 fn(x) na množině K nazýváme funkci f (x) definovanou n=l takto: oo pro každé xq e K platí f(x0) - ^ fn(xo)- n=l Mocninnou řadou nazýváme řadu funkcí tvaru oo anx" = ao + a\x + aix1 + ■ • • + anxn + ..., kde Oq, a\,a r. V matematické analýze se dokazuje, že například oo ., 2 n ex = — = 1 + — + — + ••• + — + ... pro každé x e R (tj. r = oo). z—' n! 1! 2! n\ n=0 72 /. KOMBINATORIKA Odtud například plyne, že 111 1 _, , 1 1 1 e = i + — + — + — + ..., - - e =1--+---+ ... 1! 2! 3! e 1! 2! 3! což jsou vztahy, které jsme použili již v příkladu 2.3. Zobecněním známé binomické věty je následující tvrzení: Pro každé reálné číslo a platí ,2 x"+ •■'+[ ]x" + ... , přičemž poloměr konvergence uvedené řady je r = 1 (tj. uvedená rovnost platí pro všechna x e (—1, 1)). Tak například VTT7 = (1 +*)* = í lJ + ( 2 \x + [ l )x2 + • • • + ( 2 +... . Podle příkladu 2.9 (c) tedy platí 00 / 1VJ+1 Vl +x = 1 " (-1)- ,2n-2\ n=l v ' Je-li <2«Jc" mocninná řada a r její poloměr konvergence, lze uvnitř in- n=0 tervalu (—r, r) tuto řadu derivovat a integrovat člen po členu, tj. pro každé x e (—r, r) platí (OO \ ' OO 00 n=0 / «=0 n=l přičemž zderivovaná řada má stejný poloměr konvergence jako řada původní. Dále pro každý interval [a, b] c (—r, r) platí OO 00 Mocninné řady a„x", Z>„x" podle definice považujeme za sobě rovné, n=0 n=0 jestliže pro každé n € N platí a„ = bn. 9. Vytvořující funkce 73 Konečně součet, součin a podíl mocninných řad definujeme následovně: od oo oo ^a„x" + Y^bnxn = ^(a„ + bn)x", n=0 n=0 n=0 ^^a„x'! • ^^£>„x" = ^^c„x", kde c„ = aobn +a,\bn_\ + • ■ • + an&o, «=0 n=0 n=0 oo yi íznx oo £ M" »=° «=0 00 kde ]T cř„x" je ta mocninná řada, pro kterou platí n=0 J2bnx" ■ Y^dnxn = ^Tanxn. n=0 ;i=0 «=0 9.2. Definice. Vytvořující funkcí posloupnosti (fln)^o nazýváme mocninnou oo řadu ]T a„x" (na množině, kde tato řada konverguje). n=0 9.3. Příklad, (a) Víme, že pro x e (—1, 1) platí . 1 1 + x + x + • ■ • + x" + • • • =- (geometrická řada). 1 — x To znamená, že —-— je vytvořující funkce posloupnosti 1,1,1,1,.... 1 — x (b) Najdeme vytvořující funkci posloupnosti 1, 2, 3, 4, .... Podle poznámky 9.1 víme, že pro x 6 (—1, 1) platí (l+x+x2 + --.+x'!+ ...)' = 1 +2x + 3x2 + • • • +«x"-' + • • • = i V i i-xy (i-x)2' | 00 Vytvořující funkcí posloupnosti (n)™=l je tak funkce-- = Y nx"~l. (1-x)2 „=I 74 /. KOMBINATORIKA (c) Víme, že pro každé řieNa každé x e R platí (1 + x)" = í " p* (binomická věta). To znamená, že funkce (1 + x)" je vytvořující funkcí konečné posloupnosti (tj. řádku Pascalova trojúhelníka). Vytvořující funkce jsou mocným nástrojem k řešení řady kombinatorických úloh, především těch, které vedou na rekurentní formule. K řešení komplikovanějších případů bychom však potřebovali hlubší znalosti o řadách funkcí. Proto se omezíme jen na několik jednodušších příkladů. 9.4. Příklad. Řezem v řetězci (tj. úplně uspořádané množině) A 4 0 rozumíme uspořádanou dvojici [X, ľ] neprázdných podmnožin množiny A takových, že X n ľ = 0, X U ľ = yl a pro každé dva prvky x € X, y e Y platí x < y (tj. x < y). Je zřejmé, že v konečném n-prvkovém řetězci A = {a\ < a2 < ■ ■ ■ < < an} existuje n — l řezů, protože „dolní třídou" X může být právě jen některá z množin {a\ < a2 < ■ ■ ■ < a,-}, kde i může nabýt hodnot 1, — 1. Dělením řetězce A = {a\ < a2 < ■ • • < a,,} nazveme každou posloupnost sestrojenou následovně: v prvním kroku utvořme nějaký řez [X, Y] v A. Ve druhém kroku utvořme řez ve třídě X i Y, pokud tyto třídy nejsou jednoprvkové. Ve třetím kroku utvoříme řez v každé z nově vzniklých tříd obsahujících alespoň dva prvky atd. Posloupnost ukončíme v okamžiku, kdy jsou všechny vzniklé třídy jednoprvkové. Je-li například A = {a\ < a2 < < a4 < as}, je dělením na A například posloupnost t\ = [{aua2}, {ai,a4,a5}] h = [{ai}, {a2}, {a^}, {a4, a5}] h = [{ai}, {a2}, {a3}, {a4}, {as}] Náš úkol nyní zní: Kolik existuje dělení na konečném řetězci! Označme Rn počet dělení (n + 1)-prvkového řetězce. Představme si první krok nějakého dělení tohoto řetězce. Jak jsme již uvedli, můžeme tento krok utvořit n způsoby (dolní třída může obsahovat 1,..., n prvků). Podle toho, kolik prvků dolní třída tohoto prvního řezu obsahuje, rozdělíme všechna dělení do n skupin. Do k-té skupiny patří dělení, v nichž dolní třída 1. řezu obsahuje k prvků. Spočtěme nyní počet dělení patřících do k-té skupiny. Protože dolní třída obsahuje k prvků, existuje na ní Rk_y řezů. Homí třída prvního řezu obsahuje 9. Vytvořující funkce 75 n +1 — k prvků, proto na ní existuje Rn_k řezů. Odtud zřejmě plyne rekurentní formule Rn = RoRn-\ + R\Rfí-2 + • • • + 7?„_ii?o. -Ko = 1- Vzhledem k tomu, že uvedená formule není konečného řádu, nemůžeme ji vyřešit pomocí metod odvozených v paragrafu 8. Ukážeme však, jak lze řešení nalézt pomocí vytvořující funkce posloupnosti (Rn)^ío- Vytvořující funkcí je v tomto případě funkce 00 F{x) = YjRnxn. Platí OO OO 00 F\x) = F(x) ■ F(x) = J2 RnX" ■ RnX" = J^Cnx", tt=0 n=0 n=0 kde c„ = RoRn + R\Rn~\ + ■ ■ ■ + R„Ro = Rn+i, tj. 00 F2(x) = J2R"^x"- n=0 Deťinujeme-li nyní funkci G(x) vztahem G(x) = x ■ F(x), platí 00 G2(x) = x2 ■ F2(x) = x2 ■ Rn+\xn. n=0 Platí tak OO G(x) = x -Y^RnX" = R0x + R^x2 + R2x3 + ... n=0 oo G2(x) = x2 ■ Rn+\x" = RlX2 + R2x3 +... . n=0 Odtud G2{x) = G(x) - R0x = G(x) - x (neboť R0 = 1). Z rovnice G2{x) - G(x) +x = 0 plyne G(x) =-. 2 76 /. KOMBINATORIKA Protože v bodě x = 0 řada Rnx" konverguje, existuje G(0). Z posledního vztahu plyne n=0 G(0) = l ± vT 1, o. přičemž podle definice musí být G(0) = 0. Tzn., že G(x) = 1 - VI -4x Funkci ví — 4jc však umíme rozvinout v mocninnou řadu. Podle poznámky 9.1 platí Vl -4x = (1 -4x)í = ^(-1)"( 2 )(4x)", G(JC) = - 00 /I\ i-£(-i)n(2)(4*r n=0 i-i + £(-D v2«-l /!=] 4" /2n - 2 n • 22"-1 l n - 1 n=l v ' n=0 N 7 Protože G(x) = x ■ F (x), plyne odtud «=ľl ,!=0 V 7 /?„ = 1 (2n n + 1 V n 9.5. Poznámka. Na příkladu 9.4 lze názorně demonstrovat, jak lze často úlohy na první pohled zcela odlišné převést na řešení téže rekurentní formule. V příkladu 3.33 jsme řešili problém, kolika způsoby se mohou lidé postavit do fronty na Večerník tak, aby měl prodávající vždy nazpět. Zjistili jsme, že když má k lidí desetikorunu a k lidí pětikorunu, je těchto možností 1 Jfc + 1V k 2k 9. Vytvořující funkce 77 Nyní všechny „příznivé" permutace k jedniček a k pětek (viz příklad 3.33) rozdělme do k tříd takto: permutace a\,,.., ajk patří do 5-té třídy právě tehdy, když s je nejmenší přirozené číslo takové, že mezi ciframi a\.....a2s je právě s jedniček a s pětek (například permutace 55151151 patří do 3. třídy). Je zřejmé, že když příznivá permutace patří do 5-té třídy a s < k, pak cifra na místě 2s + 1 musí být 5; jinak by daná permutace nebyla příznivá. Nyní zjistíme, kolik permutací je obsaženo v 5-té třídě. Buď tedy a\.....a%s,..., aik permutace 5-té třídy. Pak mezi členy a\,..., a2s je s jedniček a s pětek, přičemž pro každé r < s je mezi členy a\. ..., a2r více pětek než jedniček. Snadno však 1 (2s - 2\ lze dokázat, že takových permutací a\. ..., a2s je celkem - I . Mezi s \s-\ ) členy a2s+\, .... a2k je nyní k — s jedniček a k — s pětek. Přitom permutace a21+i,..., a2k musí být evidentně rovněž příznivá. Počet těchto příznivých permutací je podle příkladu 3.33 1 Í2k - 2s k — s + 1 \ k — s Odtud ovšem plyne, že v j-té třídě je celkem 1 /25-2\ 1 (2k-2s s \ s — 1 / k — s + 1 \ k — s permutací. Vzhledem k tomu, že počet všech příznivých permutací je, jak jsme již uvedli, plyne odtud identita k ^ k + \ (2s - 2\ Í2k - 2s\ _ Í2k s(k-s + \)\s-\ )\k-s ) ~\k Zavedeme-li nyní označení 1 Í2s 5 + 1 \í lze uvedenou identitu přepsat na tvar ToTk-i + T\Tk-2 + • • • + Tk-iTo = Tk, což je formule, kterou jsme ve zcela jiné souvislosti řešili v příkladu 9.4. Řešení příkladů 3.33 a 9.4 je proto zákonitě stejné. 78 /. KOMBINATORIKA Nyní ukážeme, jak vypadají vytvořující funkce posloupností, udávajících počty rozkladů přirozených čísel, o nichž jsme hovořili v paragrafu 6. 9.6. Věta. Pro vytvořující funkci posloupnosti {p{n))^L{ platí co CO ^ P(n)xn = f] —— {pro \x\ < 1), «=0 n=l položíme-li definitoricky p{0) = 1. Důkaz. Potřebujeme dokázat, že 1 + p(l)x + p{2)xl + ■■■ + p{n)x" + ■ x-1 1-x2 " ' 1 - x" Buďte flj e R libovolná čísla, i = 1,2,... . Víme, že když |a,x' | < 1, pak platí 1 - - 1 + Oíx' + afx + ■ ■ ■ + a"xm + ... (součet geometrické řady). 1 — a,x Odtud plyne 1 = (1 + a\x + a\x2 + a]x3 + ...)• (1 — a\x) • (1 — a2x2) • ... • (1 — akxk) ■ .. ■ (1 + a2x2 + a\xA + alx6 + ...)•...• (1 + akxk + alx2k + alx3k + ...)----= = 1 + a\x + {a\ + a2)x2 + ■■■ + (a[l a^ ... a[k + ... )x" + ... . V koeficientu u xn určuje každý sčítanec a^ a^ ... arkk právě jeden rozklad čísla n, totiž (1 + 1 + • • ■ + 1) + (2 + ! + ■■■+ 2) + • • ■ + (k + k + ■ ■ ■ + k) = n. (Například koeficient u x2 je roven součtu a\ + a\a\, jehož sčítanci určují po řadě rozklady 1 + 1 a 2 čísla 2.) Když nyní položíme a] = a2 = • • • = 1, obdržíme dokazované tvrzení. • 00 9.7. Poznámka, (a) Poloměr konvergence vytvořující funkce VJ p(n)x" je n=0 tedy roven 1. 00 (b) Inverzní funkcí k vytvořující funkci VJ p{n)xn je nekonečný součin n=0 oo co f[(l -*") = (!-x)-{\-x2)-...-{\ -*").■.. = £>„*". 9. Vytvořující funkce 79 Koeficienty c„ mají rovněž jednoduchou kombinatorickou interpretaci. Platí c„ = A{n) — B(n), kde A{n) je počet rozkladů čísla n na sudý počet navzájem různých sčítanců a B(n) je počet rozkladů čísla n na lichý počet navzájem různých sčítanců. (c) Již Euler, který první odvodil vytvořující funkci posloupnosti , dokázal, že „většina" koeficientů c„ je rovna nule. Přesněji řečeno, odvodil následující vztah, dnes běžně nazývaný Eulerova identita: nv—>v t. / 3k2-k ik^+k \ (1 - x") = 1 ■ ) . n=l k=\ ^ ' Důkaz této identity, který je nejvýhodnější provádět pomocí Ferrersových diagramů, zde uvádět nebudeme. (d) Eulerovu identitu lze zřejmě v řeči rozkladů přirozených čísel interpretovat - při označení uvedeném v (b) - takto: Nechť přirozené číslo n lze 3k2 ± k psát ve tvaru---, kde k je vhodné přirozené číslo. Pak A(n) = B(n). Je-li přirozené číslo n výše uvedeného tvaru, pak A(n) — B(n) = (—1)*. 9.8. Poznámka. Ideu použitou v důkazu věty 9.6 lze samozřejmě použít v řadě analogických případů. Chceme-li například zjistit počet rozkladů čísla n na sčítance, z nichž každý je roven některému z čísel si,..., s*, přičemž sčítanci jsou navzájem různí, utvoříme výraz (l+xS[)(l+xS2)...(l+xSk). Po roznásobení obdržíme evidentně výraz, v němž koeficient u x" udává počet hledaných rozkladů. 9.9. Poznámka. Vytvořující funkcí posloupnosti (p(n, je funkce G{x) =-%---. (1 -x)(l -x2)...{\ -xk) Vytvořující funkci posloupnosti udávají počty rozkladů čísla n na liché sčítance je funkce H(x) = (1 -x)(l -x3)(l -x5)... ' Konečně vytvořující funkcí posloupnosti udávající počet rozkladů čísla n na navzájem různé sčítance, je funkce 00 k(x) = (1 +jc)(1 +x2)(l+x3) ■■■ = ]~[(1 +xk). 80 /. KOMBINATORIKA Ukažme si, jak lze pomocí uvedených vytvořujících funkcí snadno odvozovat tvrzení o rozkladech přirozených čísel. Platí například H{X) = (1 -x)(l-x3)(l-x5)... = (1 - jc2)(1 - x4)(\ - x6)(l - x8) ... _ (1 -x)(l -x2)(l -x3)(l -x4)... ~ [(1 - x)(l + x)] ■ [(1 - x2)(l + x2)] ■ [(1 - x3)(l + x3)] ■ ... _ (1 -x)(l -x2)(l -x3)(l -x4)... = (1+x)(l+x2)(l+x3) ■■• = £(x). Dokázali jsme tak právě, že platí následující věta. 9.10. Věta. Počet rozkladů čísla n na navzájem různé sčítance je roven počtu rozkladů čísla n na liché sčítance. Poznámky a cvičení 1. Dokažte, že vytvořující funkce Fibonacciovy posloupnosti je 00 = ----j. ^—' 1 — x — xl n=0 2. Buď (Bn) posloupnost Bellových čísel. oo a) Dokažte, že řada £ Bnxn diverguje pro všechna x ^ 0. oo Bn b) Dokažte, že řada >J —xn absolutně konverguje na TSL n=o n\ 10. Bloková schémata, latinské čtverce a konečné roviny 81 10 Bloková schémata, latinské čtverce a konečné roviny Jedním z centrálních pojmů moderní kombinatoriky jsou tzv. bloková schémata, nazývaná též konfigurace, designy i jinak. Teorie blokových schémat je intenzívně rozvíjena a je velmi složitá. Proto se zmíníme jen o nej základnějších pojmech a zavedeme některé jednoduché typy. 10.1. Definice. Buďte v, b,k,r, X přirozená čísla, A konečná množina, \A\ = - v. Systém podmnožin X\, Xj, ..., Xh množiny A se nazývá blokové schéma typu (v, b, k, r, X) v množině A, jestliže \Xi\ = IX2I = ■ ■ ■ = \Xb\ = k, každý prvek a e A je prvkem právě r množin Xi a pro každé dva různé prvky a, b e A je {a, b} podmnožinou právě X množin Xj. Množiny X, se nazývají bloky daného blokového schématu. Je samozřejmé, že nemusí existovat blokové schéma libovolného předepsaného typu. Jak však ukážeme v příkladu 10.2, může blokové schéma existovat. 10.2: Příklad. Buď A = {1,2,3,4,5,6,7}. Blokovým schématem typu (7, 7, 3, 3, 1) je například systém množin Xi = {1,2,4} X4 = {4,5,7} X1 = {1,3,7} X2 = {2,3,5} . X5 = {1,5,6} X3 = {3,4,6} X6 = {2,6,7} 10.3. Věta. Existuje-li blokové schéma typu (v, b,k,r, X), platí bk = vr, r(k-\)=X(v-l). Důkaz. První rovnice je evidentní; levá i pravá strana zřejmě udává číslo + > • • + \Xb\. Ve druhé rovnici sečítáme počty dvojic obsahujících daný prvek a, 6 A. Prvek a,- je obsažen v r blocích a v každém z nich tvoří dvojice se zbývajícími k — 1 prvky. Současně však a, tvoří A dvojic s každým z v — 1 zbývajících prvků. • 10.4. Definice. Blokové schéma typu (u, b, 3, r, X) se nazývá systémem trojic. Pro X = 1 se systém trojic nazývá Steinerův. 82 I. KOMBINATORIKA 10.5. Poznámka. Steinerovým systémem trojic je například blokové schéma z příkladu 10.2. Je to tedy takový systém tříprvkových podmnožin dané konečné množiny, že každé dva prvky se současně vyskytují v právě jedné z podmnožin. J. Steiner v roce 1853 zformuloval tento problém následovně: Pro která přirozená čísla n lze rozdělit n písmen do trojic tak, aby se každá (neuspořádaná) dvojice písmen vyskytovala v právě jedné trojici? Protože se ve Steinerových trojicích každé písmeno vyskytuje s každým jiným písmenem právě jednou, musí být číslo n — 1 sudé, tj. n = 1 (mod 2). (Stačí si totiž uvědomit, že každé písmeno je ve trojici s dalšími dvěma písmeny.) Dále víme, že každá trojice obsahuje tři dvojice a každá dvojice se v trojicích vyskytne právě jednou. Odtud plyne, že celkový počet dvojic, což je číslo n\ n(n — 1) 2 J =-2-' mus1' "ľ* násobek tři. Celkově odtud plyne, že číslo n musí být tvaru 6k + 1, respektive 6k + 3, k e N (tj. n = 1, 3(mod 6)). V roce 1859 dokázal M. Riess, že tato nutná podmínka je současně postačující, tj. platí následující tvrzení, které uvedeme bez důkazu. 10.6. Věta. Blokové schéma typu (n,b,3,r, 1) existuje právě tehdy, když n = 6k + 1 nebo n = 6k + 3, k e N0, n > 3. v poznámce 10.5, je počet všech dvojic roven číslu "("2 ^, Každá trojice obsahuje tři dvojice, takže počet b všech bloků je roven číslu n^"7 K Podle věty 10.3 dále platí r ■ 2 = n - 1, tj. r = Sf1. Odtud a z věty 10.6 plyne 10.7. Věta. Na n-prvkové množině existuje systém Steinerových trojic právě tehdy, když n = 6k +1 nebo n = 6k + 3 (k 6 No,n > 3). V tom případě je těchto n(n — 1) n — 1 trojic---a každý prvek se vyskytuje v-trojicích. 6 2 10.8. Příklad. Uveďme Steinerovy systémy trojic pro nejmenší tři možné hodnoty n, tj. n = 3, n = 1 a n= 9. n = 3 : 12 3 n = 7 : 123 167 257 356 145 246 347 123 179 278 369 n = 9: 145 249 348 467 168 256 357 589 10. Bloková schémata, latinské čtverce a konečné roviny 83 10.9. Poznámka. Úlohu vedoucí na Steinerův systém trojic (s dalšími podmínkami) zformuloval ještě před Steinerem v roce 1847 anglický matematik R. T. Kirkman. Jde o známý Kirkmanův problém 15 dívek: 15 školaček chodí denně na procházku seřazeno do pěti trojic. Lze je řadit do trojic tak, aby každá s každou šla během 7 dnů ve trojici právě jednou? Kladná odpověď je vcelku jednoduchá. Rozpis procházek může být následující: 123 147 15 13 168 19 10 4 5 6 2 5 10 2 4 12 2 11 13 2 7 14 7 8 9 6 11 14 6 7 15 4 10 15 3 5 15 10 11 12 9 12 15 8 10 14 5 9 14 4 8 11 13 14 15 3 8 13 3 9 11 3 7 12 6 12 13 1 11 15 1 12 14 2 6 9 2 8 15 3 4 14 3 6 10 5 8 12 4 9 13 7 10 13 5 7 11 Jde o S teinerů v systém trojic s parametry v = \5,b = 35,k =3,r = 7,A = 1, přičemž musí být splněna ještě další podmínka: trojice musí být rozděleny na sedm tříd po pěti trojicích tak, aby byl každý prvek v každé třídě právě jednou. Dodnes není známo, pro která n má Kirkmanův problém, přesněji řečeno jeho příslušné přeformulování, řešení. Úzkou souvislost s teorií blokových schémat mají tzv. latinské čtverce. 10.10. Definice. Buď dána libovolná n-prvková množina A (n € N). Latinským čtvercem řádu n rozumíme čtvercovou tabulku o n řádcích a n sloupcích takovou, že v každém řádku a každém sloupci je permutace všech prvků množiny A. 10.11. Příklad. 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 12 3 5 12 3 4 1 2 3 4 5 2 14 5 3 3 4 5 1 2 4 5 2 3 1 5 3 12 4 jsou latinské čtverce řádu 5. 84 /. KOMBINATORIKA 10.12. Poznámka. Je zřejmé, že existují latinské čtverce každého řádu n e N. Z každého latinského čtverce řádu n > 1 můžeme snadno utvořit další latinské čtverce například tak, že změníme pořadí řádků, respektive sloupců, nebo provedeme nějakou permutaci prvků množiny A nebo eventuálně uvedené postupy zkombinujeme. Řekneme, že dva latinské čtverce jsou ekvivalentní, jestliže výše uvedeným způsobem lze jeden převést na druhý. Lehce lze dokázat, že každý latinský čtverec 5. řádu je ekvivalentní právě s jedním z latinských čtverců z příkladu 10.11. Latinské čtverce se vyskytují v nejrůznějších souvislostech. Utvoříme-li například obvyklou tabulku násobení v libovolné konečné grupě, obdržíme zřejmě latinský čtverec. Latinské čtverce mají rovněž jednoduchou geometrickou interpretaci. Považujme každé z n2 míst v latinském čtverci za „bod" a představme si následující „spojnice" bodů: (1) řádky latinského čtverce, (2) sloupce latinského čtverce, (3) body v nichž je vepsán stejný prvek. Tyto spojnice tvoří tzv. 3-síť s n2 uzly. Každá spojnice je tvořena n body, spojnice téhož „typu" se neprotí-nají a každým bodem prochází právě jedna spojnice každého ze tri uvedených typů. Naopak každou 3-síť lze interpretovat jako latinský čtverec. 10.13. Definice. Buďte dány dva latinské čtverce n-tého řádu utvořené z prvků množiny A. Označme ay, respektive fey, prvek ležící v průsečíku /-tého řádku a y-tého sloupce prvního, respektive druhého latinského čtverce. Protože |A2| = n2, lze všechny prvky množiny A2 vepsat do schématu utvořeného z n řádků a n sloupců. Řekneme, že dané dva čtverce (aty) a (bij) jsou ortogonální, když ve čtverci (aty, bjj) je každý prvek z A2 právě jednou. 10.14. Příklad. Čtverce jsou zřejmě ortogonální, neboť když z nich utvoříme popsaným způsobem čtverec 1 2 3 2 3 1 3 1 2 a 2 3 1 1 2 3 3 1 2 12 23 31 21 32 13 33 11 22 10. Bloková schémata, latinské čtverce a konečné roviny 85 jsou v tomto čtverci všechny prvky kartézského součinu {1, 2, 3} x {1, 2, 3} (přičemž prvek [i, j] jsme zapsali stručně jako ij). Je zřejmé, že neexistují ortogonální latinské čtverce 2. řádu. Jediné latinské čtverce 2. řádu jsou totiž čtverce 12 2 1 2 1 a 12 a ty nejsou ortogonální, neboť ve čtverci 12 21 21 12 nejsou všechny prvky součinu {1,2} x {1,2}. Problematiku existence ortogonálních latinských čtverců 6. řádu zpopularizoval Euler, když v roce 1782 zformuloval slavnou úlohu o 36 důstojnících: Sestavte 36 důstojníků 6 různých hodností ze 6 různých pluků do čtverce tak, aby v žádné řadě ani žádném zástupu nestáli dva důstojníci stejné hodnosti ani dva důstojníci ze stejného pluku. Je zřejmé, že tato Eulerova úloha vede na konstrukci dvou ortogonálních latinských čtverců 6. řádu. Protože se konstrukce těchto čtverců Eulerovi nedařila, vyslovil hypotézu, že neexistují dva ortogonální latinské čtverce řádu n = Ak + 2, k = 0,1, 2,... . (Podrobnosti viz ve cvičení 3 na konci této kapitoly.) Pravdivost této hypotézy pro k = 0 jsme ukázali výše. Samotný Euler se nedožil vyřešení tohoto problému pro k > 0. Teprve v roce 1900 dokázal francouzský matematik G. Tarry, že neexistují dva ortogonální latinské čtverce 6. řádu. Vzhledem k tomu, že latinských čtverců 6. řádu je téměř 25 000 000 a Tarry své tvrzení odvodil jistým systematickým výčtem, je jeho výkon opravdu pozoruhodný. (O počtu latinských čtverců řádu n viz kapitolu 2, poznámku 8.16). Eulerova hypotéza byla dlouho považována za správnou. Vyvrácena byla až v roce 1959, kdy R. C. Bose a S. Shrikhande sestrojili dva ortogonální latinské čtverce 22. řádu. Později Bose, Srikhande a E. T. Parker dokázali dokonce následující tvrzení: 10.15. Veta. Pro každé přirozené n > 2 kromě n = 6 existují ortogonální latinské čtverce n-tého řádu. 86 /. KOMBINATORIKA Důkaz. Důkaz nebudeme provádět, neboť přesahuje rámec tohoto textu. K jeho provedení je třeba řady tvrzení o blokových schématech. e 10.16. Příklad. Ukažme dva ortogonální latinské čtverce 10. řádu. 00 49 17 96 28 83 75 61 52 34 76 11 59 27 90 38 84 02 63 45 85 70 22 69 37 91 48 13 04 56 58 86 71 33 09 47 92 24 15 60 93 68 80 72 44 19 57 35 26 01 67 94 08 81 73 55 29 46 30 12 39 07 95 18 82 74 66 50 41 23 21 32 43 54 65 06 10 77 88 99 42 53 64 05 16 20 31 89 97 78 14 25 36 40 53 62 03 98 79 87 Z tohoto příkladu tedy plyne nesprávnost Eulerovy hypotézy již pro k = 2. Důležitou částí kombinatoriky, těsně propojenou s teorií blokových schémat, jsou tzv. konečné geometrie. Ukažme souvislost některých pojmů konečných geometrií s teorií latinských čtverců. 10.17. Definice. Buď A i- 0 konečná množina, 31 C P(A). Nechť platí: (1) Pro každé x, y € A, x ¥ y, existuje právě jedna množina P e 3i tak, že {x, y} C P. (2) Pro každou množinu P e Ji a pro každý prvek x e A, x g P, existuje právě jedna množina Q e SI taková, že x e Q a P n Q = 0. (3) Existují tri navzájem různé prvky x, y, z € A takové, že {x, y, z} není podmnožinou žádné množiny P e Ji. Pak se dvojice (A, IR) nazývá konečná afinní rovina. Prvky množiny A se nazývají body a prvky množiny JI přímky této roviny. Ve shodě s obvyklou geometrickou terminologií zavedeme následující definici. 10.18. Definice. Dvě disjunktní přímky nazveme rovnoběžkami. Směrem v afinní rovině nazveme systém všech rovnoběžek s danou přímkou. Skutečnost, že přímky P, Q jsou rovnoběžné, budeme značit symbolem P II Q. 10. Bloková schémata, latinské čtverce a konečné roviny 87 10.19. Věta. Nechť P, Q, R jsou přímky v konečné afinní rovině. Nechť P || Q, Q\\ R, P ÍR. Pak R \\ P. Důkaz. Připusťme, že existuje a e P H R. Pak by bodem a procházely dvě rovnoběžky s přímkou Q, což není možné. • 10.20. Věta. Všechny přímky v konečné afinní rovině mají stejný počet bodů. Důkaz. I. Nejprve dokážeme, že stejný počet bodů mají všechny přímky téhož směru. Nechť tedy v konečné afinní rovině (A, St) existuje přímka P tvořená n body a\, ...,a„. Buď b e A libovolný bod neležící na přímce P (existence takového bodu plyne z vlastnosti (3)). Podle (2) prochází tímto bodem právě jedna rovnoběžka Q s přímkou P. Nyní dokážeme, že\Q\ =n. Pro každý bod a, e P existuje podle (1) právě jedna přímka /?, taková, že [(k, t>} C Rt. Pro a, i- a j je zřejmě 7?, ý Rj. (Kdyby totiž 7?r = Rj, ležely by body a,-, aj, b na téže přímce, avšak a,, a j určují přímku P a b g P.) Zvolme a, e P libovolně. Podle (2) prochází každým bodem a j e P, a j 4 a;, právě jedna přímka disjunktní s R,. Označme tuto přímku Sj. Kdyby byly přímky S j a Q rovnoběžné, musela by se přímka S j rovnat přímce P, protože bodem a j prochází jediná rovnoběžka s Q. To by však znamenalo, že at € R j H S j, což je spor s předpokladem. Přímka S j proto protne přímku Q v jednom bodě Sj různém od b (neboť Sj n R j = {aj}). Pro j ý k přitom zřejmě platí Sj i- í*. Na přímce Q tak leží body b, s j, j ý i. Přitom je zřejmé, že na Q nemůže ležet žádný další bod. (Předpokládejme totiž, že existuje na Q další bod c. Podle (2) existuje přímka C tak, že c e C, C n Rt = 0, tj. C i- Q, neboť b e Q D Rj. Je-li c i- sh je C ý S j. Pak ale C protne přímku P v bodě různém od a, pro všechna i, což je spor.) Dokázali jsme tak, že \ Q\ — n. II. Nechť nyní A, B jsou dvě různé přímky, které nejsou rovnoběžné. Připusťme, že A je tvořena n body flj,..., a„ a na B leží navzájem různé body b\, ..., bn+\. Zvolme označení tak, že průsečík přímek A, B je a\ =b\. Podle definice bodem b„+\ prochází rovnoběžka C s přímkou A. Tato rovnoběžka má podle první části důkazu n bodů; označme je c\,..., c„ = bn+i. Označme S\ přímku procházející body bu c\ a zvolme na B libovolný bod b, i- b\. Tímto bodem prochází jediná rovnoběžka 5, s přímkou S\. Tato rovnoběžka nutně protne přímky A, B. Kdyby totiž byly například přímky A a Si rovnoběžné, procházely by bodem ai dvě rovnoběžky s přímkou 5,, a to přímky A a S{. 88 /. KOMBINATORIKA Označme S, D A = a*, S; fl fi = fe*. Pro i ^ 7 však podle tvrzení 10.19 platí a* ^ a* b* ý b* .To však není možné, neboť na přímce B je víc bodů než na přímkách A a C. Přímky A, B tedy musí obsahovat stejný počet bodů. • 10.21. Definice. Řádem konečné afinní roviny rozumíme počet bodů ležících na přímkách v této rovině. Snadno lze dokázat následující tvrzení. 10.22. Věta. 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 + \ směrů a každý směr obsahuje n rovnoběžek. Nyní je ovšem přirozená otázka, zda nějaká afinní konečná rovina vůbec existuje. I 1 2 3 4 První II 5 7 6 8 směr III 10 11 9 12 IV 15 14 16 13 V 13 1 5 9 Druhý VI 14 10 2 6 směr VII 11 15 7 3 VIII 4 8 12 16 IX 6 16 1 11 Třetí X 12 5 15 2 směr XI 8 9 3 14 XII 13 4 10 7 XIII 7 12 14 1 Čtvrtý XIV 2 13 8 11 směr XV 16 3 10 5 XVI 9 6 4 15 XVII 1 8 10 15 Pátý XVIH 2 7 9 16 směr XIX 3 6 12 13 XX 4 5 11 14 Tab. 10.4: Konečná afinní rovina 4. řádu 10. Bloková schémata, latinské čtverce a konečné roviny 89 10.23. Příklad. V tabulce 10.4 je popsána konečná afinní rovina 4. řádu. Podle věty 10.22 musí obsahovat 16 bodů (jsou označeny arabskými číslicemi) a 20 přímek (jsou označeny římskými číslicemi). Každý z pěti směrů obsahuje čtyři přímky. 10.24. Poznámka. Sportovně založený čtenář může postřehnout, že afinní rovina 4. řádu uvedená v tabulce 10.4 je rozpisem rozjížděk při klasické ploché dráze, kdy 16 jezdců absolvuje 20 rozjížděk tak, že každý jezdec jede s každým právě v jedné rozjížďce. Tabulka 10.4 je důkazem, že konečné afinní roviny vskutku existují. Tím však vůbec není zodpovězena otázka, zda existuje konečná afinní rovina libovolného řádu n € N. Alespoň částečnou odpověď na tuto otázku nám dává teorie latinských čtverců. Jak latinské čtverce souvisejí s afinními rovinami si ukážeme na rovině uvedené v tabulce 10.4. (Porovnej následující konstrukci s definicí 3—sítě v poznámce 10.12.) Seřaďme nejprve 16 bodů dané roviny do následující tabulky: 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Na první pohled je vidět, že řádky v této tabulce jsou přímky 1. směru a sloupce přímky 2. směru v dané rovině. Nyní si ukážeme, jak lze zapsat přímky dalších tří směrů. Uvažujme 3. směr, tj. přímky IX - XII. V uvedené čtvercové tabulce pak na místa bodů první z těchto přímek, tj. přímky číslo IX, vepišme číslo 1. (Tj. nahradíme jedničkou čísla 1,6,11,16.) Podobně cifrou 2 nahradíme body přímky číslo X (tj. vepíšeme dvojku místo čísel 2,5,12,15). Když tuto úpravu provedeme analogicky i pro přímky číslo XI a XII, obdržíme čtverec 12 3 4 2 14 3 3 4 12 4 3 2 1 Nyní si uvědomme, že jsme zákonitě obdrželi latinský čtverec 4. řádu. Vzhledem k tomu, že přímky 3. směru se neprotínají (jsou to rovnoběžky), nemůže se stát, aby jedno a totéž místo mělo být obsazeno různými ciframi. 90 I. KOMBINATORIKA Protože každá přímka 3. směru protne každou přímku 1. směru (zapsanou v některém řádku čtvercové tabulky) právě jednou a rovněž každou přímku 2. směru (zapsanou v některém sloupci) protne právě v jednom bodě, je v každém řádku a každém sloupci vzniklého čtverce opravdu permutace čísel 1, 2, 3, 4, takže vzniklý čtverec je nutně latinský. Když nyní provedeme analogickou úvahu i pro přímky 4. a 5. směru, obdržíme latinské čtverce 1 2 3 4 1 2 3 4 3 4 1 2 4 3 2 1 a 4 3 2 1 2 1 4 3 2 1 4 3 3 4 1 2 Popsaným způsobem jsme pomocí roviny 4. řádu sestrojili tři latinské čtverce 4. řádu. Jak se čtenář může snadno přesvědčit, jsou každé dva z těchto čtverců vzájemně ortogonální. Současně je snadné si uvědomit, že ortogonalita těchto čtverců je zákonitá. Popsanou konstrukci však nyní můžeme snadno obrátit. Budou-li dány libovolné tři vzájemně ortogonální latinské čtverce 4. řádu, sestrojíme z nich zpětně snadno afinní rovinu 4. řádu. Uvedenou úvahu můžeme zcela analogicky provést pro každé přirozené n a tak dokázat následující tvrzení. 10.25. Věta. Konečná afinní rovina řádu n > 3 existuje právě tehdy, když. existuje n — í latinských čtverců n-tého řádu, z nichžkaždé dva jsou ortogonální. Jak jsme již uvedli, neexistují ani dva ortogonální latinské čtverce 6. řádu. Proto z věty 10.25 okamžitě plyne 10.26. Důsledek. Neexistuje konečná afinní rovina 6. řádu. (Kdyby sportovní činovníci znali tento výsledek, pravděpodobně by nikdy nevznikla tzv. „dlouhá plochá dráha", při níž jezdí v jedné rozjížďce 6 jezdců. Pro tuto soutěž podle důsledku 10.26 nelze sestrojit analogický „spravedlivý" rozpis jako pro klasickou plochou dráhu.) 10.27. Poznámka. Dodnes není obecně známo, pro která n konečná afinní rovina n-tého řádu existuje. Jsou známy jen některé dílčí výsledky. Tak například metodami analytické geometrie lze odvodit tvrzení: Je-li n = pk, kde p je prvočíslo a k přirozené číslo, pak existuje konečná afinní rovina řádu n. Podstatně komplikovanější je důkaz následujícího tvrzení: 10. Bloková schémata, latinské čtverce a konečné roviny 91 Nechť číslo n není součtem čtverců dvou přirozených čísel a nechť n = = \{modA) nebo n = 2(mod4). Pak neexistuje afinní rovina řádu n. Podle uvedeného tvrzení neexistuje například afinní rovina 14. řádu. Je však řada případů, kdy pro dané n neumíme rozhodnout, zda afinní rovina řádu n existuje. Nejmenším takovým číslem je n = 10. Ke konstrukci afinní roviny 10. řádu bychom potřebovali mít k dispozici 9 vzájemně ortogonálních latinských čtverců 10. řádu. Podle příkladu 10.16 dva ortogonální latinské čtverce 10. řádu existují. Ani pomocí počítačů však dodnes nebyla nalezena ani jedna trojice vzájemně ortogonálních latinských čtverců 10. řádu. Existence afinní roviny 10. řádu tak dodnes nebyla ani dokázána ani vyvrácena. Pro velkou obtížnost tohoto problému se mu často říká matematický „problém století", i když mnohé jiné problémy jsou známější a populárnější. Kromě konečných afinních rovin jsou intenzivně studovány i konečné projektivní roviny, jejichž definice je v některých rysech obdobná. 10.28. Definice. Buď A jí 0 konečná množina (její prvky budeme opět nazývat body), a množina SI C