Kombinatorické počítání NDMI015

Místo a čas přednášky: S7 v pondělí v 9-10:30. Začínáme 28. 2.

Plán přednášky pro LS 2011. Přednáška bude věnována kombinatorické enumeraci, použití generujících funkcí při odvozování přesných a asymptotických enumerativních výsledků (=počítání různých diskrétních struktur, např. grafů, stromů, slov, permutací, rozkladů množin, obarvení, ...). Budeme postupovat podle klasické monografie P. Flajoleta a R. Sedgewika. V LS 2011 plánuju probrat toto aktuální téma: jak nedávno dokázali pánové Duminil-Copin a Smirnov, počet sebeneprotínajících procházek s n kroky a pevným výchozím vrcholem v šestiúhelníkové mřížce (tj. včelí plástvi) je asymptoticky c^{n + o(n)}, kde c = (2 + 2^{1/2})^{1/2} = 2cos(pi/8) = 1.84775... .

Literatura. P. Flajolet and R. Sedgewick, Analytic Combinatorics, CUP, 2009.

Zkušební otázky. 1. Popište vlastnosti okruhu mocniných řad C[[x]] a základní operace s nimi (jednotky, formální konvergence, skládání moc. řad, kompoziční inverz).  2. Základní vlastnosti racionálních generujících funkcí (hlavní věta o rac. generujících funkcích; případy, kdy je koeficient a_n polynom či kvazipolynom v n). 3. Uveďte a odvoďte vzorec pro metodu přechodové matice. 4. Dokažte, že počet mřížových bodů v n-tém nafouknutí mřížového (racionálního) mnohostěnu v R^d je polynom (kvazipolynom) v n. 5. Popište-přehledově, bez detailů- důkaz Duminil-Copinovy a Smirnovovy věty o asymptotice počtů cest (sebeneprotínajících procházek) v šestiúhelníkové mřížce.

přednáška 28. 2. 2011. Literatura k přednášce. O počtu sebeneprotínajících procházek v šestiúhelníkové mřížce. Příklady použití generujících funkcí: počty kompozic čísel a číselných rozkladů, Fibonacciova čísla, počet neoznačených grafů na n vrcholech, nemožnost rozkladu množiny přirozených čísel {1, 2, ...} na aritmetické posloupnosti se vzájemně různými diferencemi. 
přednáška 7. 3. 2011. Algebraická teorie mocninných řad. Okruh formálních mocninných řad C[[x]] v jedné neurčité a s komplexními koeficienty. Řád f(x), C[[x]] je obor integrity, f(x) = a_0 + a_1x + ... je jednotka (tj. má multiplikativní inverz), právě když a_0 není 0. Formální konvergence posloupnosti mocninných řad F_1(x), F_2(x), ... a nekonečná řada F_1(x) + F_2(x) + ...  mocninných řad: formálně konverguje, právě když sčítanec F_n(x) jde k 0 (tj. řád F_n(x) jde do nekonečna)! Podobně pro nekonečný součin (1 + F_1(x))(1 + F_2(x)) ... Skládání mocninných řad: f(g(x)) formálně konverguje, pokud g(0) = 0. Dokažte si jako cvičení, že skládání je asociativní. Multiplikativní inverz 1/f(x) pomocí složeniny s geometrickou řadou. 
přednáška 14. 3. 2011. Ještě příklad na formální konvergenci nekonečných součinů mocninných řad: počet rozkladů čísla n na různé části = počet rozkladů čísla n na liché části, což je ekvivalentní rovnosti formálních limit (1 + x)(1 + x^2)(1 + x^3)... =  (1 - x)^{-1}(1 - x^3)^{-1}(1 - x^5)^{-1}... Zpět ke skládání moc. řad. Kompoziční inverz f^{(-1)} moc. řady f (s ord(f) = 1), jeho existence a jednoznačnost. Vnitřní inverz je roven vnějšímu - v tomto případě je skládání moc. řad komutativní, ale jinak typicky ne. Příklad s Catalanovými čísly - jejich gf je komp. inverz k x - x ^2 - a s jednoduchými permutacemi čísel 1, 2, ..., n - gf jejich počtů je víceméně komp. inverz k x + 2!x^2 + 3!x^3 + ... . Skládání moc. řad v širším smyslu: f(g(x)) je definováno, právě když g(0) = 0 nebo f(x) je polynom, pak ale nemáme asociativitu (f = x + x^2 +2x^3 + 5x^4 + ..., g = x- x^2 a h = 1, potom fo(goh) = f(0) = 0, ale (fog)oh = xoh = 1). Lagrangeova inverzní formule, bez důkazu: [x^n] f^{(-1)} = (1/n)[x^{n-1}](x / f(x))^n.
přednáška 21. 3. 2011. Racionální mocninné řady. Podílové těleso okruhu mocninných řad jsou Laurentovy řady, tj. mocninné řady s konečně mnoha sčítanci se zápornými exponenty. Ty přirozeně obsahují racionální funkce p(x) / q(x), podíly dvou polynomů, a průnik s C[[x]] dává racionální mocninné řady. Tři příklady rac. moc. řad. 1. Fibonacciova čísla. 2. Mřížové sebeneprotínající procházky s kroky W, N a E. 3. Asymptotika denumerantů, tj. počtů rozkladů n na části z dané konečné množiny. Hlavní věta o rac. moc. řadách: F(x) = a_0 + a_1x + a_2x^2 + ... = p(x) / q(x), kde q(0) není 0 a deg(p) < deg(q) <=> (a_n) splňuje lineární rekurenci s konstantními koeficienty <=> a_n = lineární kombinace exponenciál c^n s polynomiálními koeficienty p(n). Zajímavé tvrzení: Když F(x) = a_0 + a_1x + a_2x^2 + ... = p(x) / q(x), kde a_n jsou z podtělesa K (tělesa komplexních čísel) a komplexní polynomy p a q jsou nesoudělné a monické, potom i koeficienty těchto polynomů leží v K. Důkazy pomocí lineární algebry příště. 
přednáška 28. 3. 2011. Důkazy obou tvrzení o racionálních mocninných řadách z minulé prednášky. Počítání cest v šestiúhelníkové mřížce.  Budeme dokazovat větu Duminila-Copina a Smirnova z loňského roku, že s_n, počet cest v 6-úhelníkové mřížce  (3-regulární rovinný graf s 6-úhelníkovými stěnami) s pevným počátečním vrcholem a n hranami, má asymptotiku s_n = (2cos(pi/8) )^{n + o(n)}. Zatím jen důkaz, že lim s_n^{1/n} existuje a je vlastní.
přednáška 4. 4. 2011. Základní pojmy: šestiúhelníkový graf H = (V, E), orientace hran, jejich směr l(e), cesty w v H, směr cesty l(w), navíjecí číslo cesty r(w) a jeho vlastnosti. Připomenutí Jordanovy věty o kružnici, bez důkazu. Úplné navíjecí číslo uzavřené cesty je  +6 nebo -6, podle orientace, bez důkazu. Oblasti  a jednoduché oblasti, hraniční hrany oblastí, množiny cest X(a, e), kde X je oblast a a a e jsou dvě hraniční hrany. Generující funkce F_{a, e}(x) počítající cesty v X(a, e) podle délky. Základní identita: Je-li H = (V, E) šestiúhelníkový graf, X jednoduchá oblast jeho vrcholů a a její hraniční hrana, potom sum_e l(e)y^{r(e)}F_{a, e}(x) = (1 + xz^{-2}y + xz^2y^{-1})sum_{w in S}l(w)y^{r(w)}x^{|w|} +  (z^4y^4 + z^{-4}y^{-4})sum__{w in S, C in C(w)}l(w)y^{r(w)}x^{|w| + |C|}, kde nalevo sčítáme přes všechny hraniční hrany e oblasti  X, orientované od X, r(e) = r(w) pro libovolnou cestu w z X(a, e) a napravo z označuje primitivní šestou odmocninu z 1, S je množina všech cest v X začínajících v a a C(w) je množina všech kružnic C v X protínajících w právě v posledním vrcholu w.  Důkaz identity a pokračování v důkazu věty příště.
přednáška 11. 4. 2011. Důkaz základní identity. Vyřešení rovnice z^4y^4 + z^{-4}y^{-4} = 0. Začátek důkazu dolního odhadu.
přednáška 18. 4. 2011. Dokončení důkazu dolního odhadu. Začátek důkazu horního odhadu.
přednáška 2. 5. 2011 (25. 4. 2011 přednáška nebyla, bylo Velikonoční pondělí). Důkaz horního odhadu.
přednáška 9. 5. 2011. Metoda přechodové matice. Metoda přechodové matice. Tvrzení: Je-li M čtvercová k krát k matice s komplexními položkami (popř. položkami z nějakého komut. okruhu R s 1) a pro pevné indexy 1 <= i, j<= k označuje a(n) položku na místě i, j v M^n, potom je mocninná řada a(0) + a(1)x + a(2)x^2 + ... racionální, totiž podíl dvou determinantů.  Je-li D vážený or. graf a A jeho přechodová (incidenční) matice, potom na místě i, j v A^n je celková váha všech tahů délky n z vrcholu i do vrcholu j. Takže odpovídající GF je racionální.  Kombinatorické úlohy řešitelné touto teorií, např. počty slov se zakázanými (souvislými) podslovy.
přednáška 16. 5. 2011. Počítání mřížových bodů v mnohostěnech. Tvrzení: Je-li P mřížový (resp. racionální, přičemž mP je mřížový) mnohostěn v R^d a f_P(n) označuje počet mřížových bodů v nafouknutí nP, potom je mocninná řada F_P(x) = f_P(0) + f_P(1)x + f_P(2)x^2 + ... racionální, dokonce je f_P(n) polynom (resp. kvazipolynom s periodou m) v n. Důkaz. Zvedneme to do vyšší dimenze tak, že F_P(x) = F_K(1, 1, ..., 1, x), kde F_K je generující funkce mř. bodů ležících v jistém kuželi K v R^{d+1} s vrcholem v počátku. Ukážeme, že pro každý kužel K v R^d je F_K tvaru polynom(z_1, ..., z_d) / (1 - m_1)(1 - m_2)...(1 - m_k), kde každý m_i je monom (tj. součin mocnin proměnných z_1, ..., z_d). Zatím jsme to dokázali ve speciálním případu, kdy vektory generující kužel K jsou LN.
přednáška 23. 5. 2011.

květen 2011