Vyuka - Martin Klazar

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. Uveďte a dokažte Lagrangeovu inverzní formuli a uveďte příklady na její použití. 3. Uveďte a dokažte součinovou a kompoziční formuli pro EGF a uveďte příklady na jejich použití. 4. Pentagonální identita pro počty rozkladů a horní odhad na velikost rozkladové funkce p(n) pomocí generujících funkcí. 5. 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). 6. Uveďte a odvoďte vzorec pro metodu přechodové matice. 7. 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.

1. přednáška, 2. 3. 2010. Analytická kombinatorika, tj. enumerace diskrétních struktur pomocí generujících funkcí, má tři tváře: kombinatorickou (kombinatorika počítaných struktur), analytickou (asymptotické odhady počtů daných struktur, generující funkce je opravdická funkce) a algebraickou (generující funkce je formální mocninná řada). Další obecné řeči. Úvodní ilustrativní příklad se střídavými permutacemi: koeficient t_n v Taylorově rozvoji funkce tangens, tan(z) = 1z/1! + 2t^3/3! + 16t^5/z^5 + ... + t_nz^n/n! + ... , je počet tzv. střídavých permutací a_1, a_2, ..., a_n čísel 1, 2, ..., n s lichým n, přičemž střídavost znamená, že a_1 < a_2 > a_3 < a_4 > .... . Otevřený problém součtových permutací.

2. přednáška, 9. 3. 2010. Přehled algebraických vlastností formálních mocninných řad. C[[x]] tvoří komutativní okruh s 1 a díky chování řádu ord(f) (= minimální n, že [x^n]f není 0 a = oo pro f = 0), ord(fg) = ord(f) + ord(g), to je i obor integrity. Tvrzení: moc. řada f je jednotka, právě když f(0) není 0. Příklad: 1 / (1 - x) = 1 + x +x^2 + ... . Formální konvergence v C[[x]], nekonečné součty a součiny moc. řad. Tvrzení: V C[[x]] nekonečná řada f_1 + f_2 + ..., popř. nekonečný součin (1 + f_1)(1 + f_2) ... , formálně konverguje, právě když f_n --> 0. Příklady nekonečných součinů. Skládání moc. řad. Tvrzení: když moc. řady f, g a h splňují g(0) = h(0) = 0, potom (f o g) o h = f o (g o h). Bez předpokladu nulovosti konstantních členů ale skládání moc. řad obecně asociativní není: [(x + x^2 + 2x^3 + 5x^4 + ...) o (x - x^2)] o 1 = x o 1 = 1, ale (x + x^2 + 2x^3 + 5x^4 + ...) o [(x - x^2) o 1] = (x + x^2 + 2x^3 + 5x^4 + ...) o 0 = 0 --- toto se nám s polynomy vskutku nemůže stát. O skládání a kompozičních inverzech si to dopovíme příště.

4. přednáška, 23. 3. 2010. Omezení počtu komponent v konstrukcích Seq, Mset, Set, Cyc. Iterativní a rekurzivní zadání kombin. tříd pomocí základních konstrukcí. Příklady na Catalanova čísla: zr stromy, binární stromy a triangulace (n+2)-úhelníka. Kompozice a rozklady, vzorce pro generující funkce. Rekurence p(n) = (1/n)sum_{j=1}^n sigma(j).p(n-j), kde sigma(j) je součet dělitelů čísla j.

5. přednáška, 30. 3. 2010. Lepší rekurence pro p(n) - pentagonální identita dává, že p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) - ..., kde 1, 2, 5, 7, 12, 15, ... jsou pětiúhelníková čísla. Důkaz p. identity pomocí involuce na Ferrersových diagramech. Důkaz horního odhadu p(n) < exp(pi.sqrt(2n/3)) pomocí Cauchyova odhadu (má-li f(x) = a_0 + a _1x + ... nezáporné koeficienty a 0<u<r, kde r je poloměr konvergence, pak a_n.u^n < f(u)).

6. přednáška, 6. 4. 2010. Racionální generující funkce. Hlavní věta o racionálních GF: 1) GF A(z) je racionální, tj. tvaru p(x) / q(x), kde p a q jsou polynomy a q(0) není 0 <--> 2) Posloupnost jejích koeficientů (a_n) splňuje lineární rekurenci s konstantními koeficienty <---> 3) koeficient a_n má explicitní vyjádření ve tvaru lineární kombinace exponenciál c_i^n s polynomiálními koeficienty p_i(n); důkaz. Speciální případy: i) a_n je polynom v n a ii) a_n je kvazipolynom v n.

7. přednáška, 13. 4. 2010. Přednáška byla zkrácena, takže jen přehled, co nás čeká příště. Dvě obecné metody v kombinatorické enumeraci vedoucí na racionální generující funkce: 1) metoda přechodové matice a 2) počítání mřížových bodů v mnohostěnech.

8. přednáška, 20. 4. 2010. 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.

9. přednáška, 27. 4. 2010. Počítání mřížových bodů v mnohostěnech. Motivační úloha: počet H_n(t) polomagických čtverců n krát n se součtem (v každém řádku i sloupci) t je polynom v t stupně (n - 1)^2, např. H_2(t) = t + 1, H_3(t) = t^4/8 + 3t^3/4 + 15t^2/8 + 9t/4 + 1, ... 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.

10. přednáška, 4. 5. 2010. Opakování. Vyjádření obecného kužele jako sjednocení elementárních kuželů s disjunktními vnitřky. Trik s perturbací: lze přičíst malý vektor tak, že se množina mřížových bodů obsažených v kuželi nezmění a na průnicích elementárních kuželů nebudou žádné mřížové body. Celková GF mřížových bodů v kuželi pak je prostě součtem GF mřížových bodů v elementárních kuželech a jsme hotovi. Reciprocita: Je-li P racionální mnohostěn v R^d a Q jeho relativní vnitřek, pak f_P(-t) = (-1)^{dim P}f_Q(t), bez důkazu. Odvození formule pro počet polomagických čtverců 3 x 3 se součtem t pomocí reciprocity.

11. přednáška, 11. 5. 2010. Cayleyho vzorec n^{n - 2} pomocí generujících funkcí. Tento známý vzorec pro počet všech stromů s množinou vrcholů {1, 2, ..., n} lze odvodit i pomocí generujících funkcí, ale je k tomu třeba znát dvě techniky, a) Lagrangeovu inverzní formuli (LIF) a b) práci s exponenciálními generujícími funkcemi. Obojí si vysvětlíme. Nejprve LIF: splňuje-li f(x) rovnici f(x) = x.F(f(x)), potom [x^n]f = (1/n)[x^{n-1}]F^n. Důkaz pomocí reziduí v tělese Laurentových mocninných řad C((x)). Příklady použití LIF.

12. přednáška, 18. 5. 2010. Nyní tedy exponenciální generující funkce (EGF). Součinová a kompoziční formule. Příklady na jejich použití: Bellova čísla, Stirlingova čísla, počty 2-regulárních grafů, počty souvislých grafů. A konečně odvození Cayleyho vzorce.

Kombinatorické počítání NDMI015