Vyuka - Martin Klazar

Místo a čas přednášky: přednáška se konala v úterý v 17:20-18:50 v S6.

Plán přednášky pro LS 2013. Přednáška bude věnována kombinatorické enumeraci, použití generujících funkcí při odvozování přesných enumerativních výsledků (=počítání různých diskrétních struktur, např. grafů, stromů, slov, permutací, rozkladů množin, obarvení, ...). Asymptotice se budeme věnovat jen málo. Před rokem jsem přednášel toto. Chci mimo jiné vyložit tyto dva zajímavé výsledky z kombinatorické enumerace. Pro pevné k nechť a(n) je počet těch permutací čísel 1, 2, ..., n, které neobsahují rostoucí podposloupnost délky k, a podobně pro pevnou konečnou množinu přirozených čísel S nechť b(n) je počet všech těch označených (tj. izomorfismus nebereme v úvahu) grafů na množině vrcholů {1, 2, ..., n}, které mají všechny stupně vrcholů v S. Potom obě posloupnosti a(n) i b(n) jsou P-rekurzivní, což znamená, že splňují lineární rekurenci s polynomiálními koeficienty: p_0(n).a(n) + p_1(n).a(n - 1) + ... + p_r(n).a(n - r) = 0 pro každé n pro nějaké celočíselné polynomy p_i(x), a podobně pro b(n).

Zkušební otázky. 1. Dokažte, že (i) přirozená čísla {1, 2, ...} nelze rozložit na dvě či více aritmetických posloupností se vzájemně různými diferencemi a že (ii) sčítací funkce r_A(n) nemůže být eventuálně konstantní. 2. Uveďte vlastnosti operací pro počítání s formálními mocninnými řadami, dokažte tvrzení o existenci multiplikativního a kompozičního inverzu. 3. Dokažte součinovou a kompoziční formuli pro exponenciální generující funkce a uveďte aplikace. 4. Dokažte Lagrangeovu inverzní formuli a uveďte aplikace. 5. Odvoďte Cayleyho formuli n^{n-2} pro počet stromů pomocí generujících funkcí. 6. Odvoďte rekurence pro počty souvislých grafů a pro počty 2-regulárních grafů.

1. přednáška 26. 2. 2013. Tři motivační příklady: 1. Odvození Cayleyho formule n^{n-2} pro počet stromů na množině vrcholů {1, 2, ..., n} pomocí generujících funkcí, některé kroky jsme museli přeskočit. 2. Přirozená čísla 1, 2,... nelze rozložit na aritmetické posloupnosti se vzájemně různými diferencemi. 3. Je-li A nekonečná množina přir. čísel, pak sčítací funkce r_A(n) = (počet vyjádření n = a_1 + a_2, kde a_i je v A a a_1 <= a_2) nemůže být eventuálně konstantní.

2. přednáška 5. 3. 2013. Zmínka o pokrývajících kongruencích (každé celé číslo splňuje alespoň jednu z kongruencí = 0 (mod 2), = 0 (mod 3), = 1 (mod 4), = 3 (mod 8), = 7 (mod 12) a = 23 (mod 24)). Počítání zakořeněných rovinných stromů a Catalanova čísla c_n. Odvozování rekurencí, zejména (4n-2)c_{n+1} - (n+1)c_n = 0 pro Catalanova čísla (z explicitního vzorce c_n = (1/n)binom(2n-2, n-1), z řešení kvadratické rovnice pro gen. funkci C = C(x) a konečně z té rovnice C^2 - C + x = 0 samotné). Chování c_n modulo 2. Jak se c_n chovají modulo 3?

3. přednáška 12. 3. 2013. Lineárně rekurentní posloupnosti. Příklad: Fibonacciova čísla. P(olynomiáně)-rekurentní (či rekurzivní) posloupnosti. Příklad: Catalanova čísla. Proč Catalanova čísla nejsou lineárně rekurentní. Připomenutí dvou Gesselových vět o dvou enumerativních problémech vedoucích k P-rekurentním posloupnostem. (Gesselův) vzorec s_n(1234) = (n + 1)^{-2}(n + 2)sum_{k=0}^n B(2k, k)B(n + 1, k + 1)B(n + 1, k + 2), kontrola pro n = 4, kdy dává 4! - 1 = 23.

4. přednáška 19. 3. 2013. Obecně o moc. řadách: C[[x]] je okruh, dokonce obor integrity, pojem řádu ord(f), 2^{-ord(f)} je (nearchimedovská) norma na C[[x]]. Podílové těleso k C[[x]] jsou Laurentovy řady C((x)). Jednotky v C[[x]] jsou f s f(0) =! 0. Formální konvergence moc. řad, nekonečné součty a součiny moc. řad. Příklady: 1/f lze vyjádřit jako součet geom. řady, nekonečné součiny v teorii číselných rozkladů. Skládání moc. řad: složenina f(g) je definována, pokud g(0) = 0. Skládání je asociativní. Příklad, že maximalistické skládání moc. řad (f(g) je navíc definováno, pokud je f polynom) asociativní není: ((x + x^2 + 2x^3 + 5x^4 + 14x^5 + ...) o (x - x^2)) o 1 = 1 =! 0 = (x + x^2 + 2x^3 + 5x^4 + 14x^5 + ...) o ((x - x^2) o 1). Příště si povíme o kompozičním inverzu moc. řad.

5. přednáška 26. 3. 2013. Tvrzení: f(x) má levý kompoziční inverz iff ord(f) = 1, totéž pro pravý inverz, oba inverzy se rovnají (díky asociativitě), což pro GF Catalanových čísel C(x), jež je (x - x^2)^{(-1)}, dá identitu ... . Formální derivování a jeho vlastnosti (linearita, Leibnizova formule, řetízkové pravidlo ...). Formální exponenciála a logaritmus pro moc. řady (zprostředkují izomorfismus aditivní grupy moc. řad f(x) s f(0) = 0 a multiplikativní grupy moc. řad f(x) s f(0) = 1) - jejich vlastnosti se snadno dokážou pomocí derivace. Lagrangeova inverzní formule (LIF): [x^n] g(f(x)^{(-1)}) = (1/n) [x^{n - 1}] g(x)' (x / f(x))^n, důkaz pomocí rezidua, tj. koeficientu u x^{-1}.

7. přednáška 9. 4. 2013. Rekurence pro počet souvislých grafů na množině vrcholů [n]. Další použití součinové a kompoziční formule pro EGF: rovnice pro EGF stromů s kořenem, explicitní vyjádření EGF dvouregulárních grafů. Rekurence pro počty těchto grafů, zejména P-rekurence a_n = (n - 1)a_{n - 1} + ((n - 1)(n - 2) / 2)a_{n - 3}, a_0 = 1, a_1 = a_2 = 0. Podobně lze počítat třeba 012-regulární grafy. P-rekurentní posloupnosti a D-konečné mocninné řady. Ekvivalentní definice (P-rek. <=> lin. dif. rov. s poly. koef. <=> homog. lin. dif. rov. s poly. koef <=> derivace mají konečnou lin. dimenzi nad rac. funkcemi) a implikace f je algebraická => f je D-konečná, oba důkazy příště.

Kombinatorické počítání NDMI015