Kombinatorické počítání DMI015

Plán přednášky pro LS 2008. Přednáška bude podobná loňské, ale doufám, že lépe uspořádaná. Ukážu na ní příklady použití metody vytvořujících funkcí (tj. mocninných řad) při počítání kombinatorických struktur. Začneme Fibonacciovými čísly a pak se podíváme obecněji na posloupnosti splňující lineární rekurence s konstantními koeficienty a jim  odpovídající racionální mocninné řady. S nimi úzce souvisí užitečná metoda přechodové matice, s níž se dá mnohe spočítat, a pěkná geometrická teorie počítání mřížových bodů v mnohostěnech. Řekneme si i něco o asymptotických metodách. Pak přejdeme ke Catalanovým číslům a k některým úlohám, v nichž se objevují, a obecněji k algebraickým mocninným řadám. Mnohé algebraické rovnice se v oboru mocninných řad elegantně vyřeší Lagrangeovou inverzní formulí, čímž se odvodí explicitní vzorečky pro hledané počty struktur. Dostaneme se i k enumerativním úlohám, v nichž se objevuje třída tzv. D-konečných mocninných řad a0 + a1x + a2x2 + ... s  koeficienty an splňujícími lineární rekurenci s polynomiálními koeficienty.
Otázky ke zkoušce: 1. Základní algebraické vlastnosti mocninných řad (aritm. operace, skládání, Lagrangeova inverzní formule).  2. Racionální generující funkce (hlavní věta, metoda přechodové matice). 3. Ehrhartova věta o mřížových bodech v nafouknutích mnohostěnů (důkaz, aplikace). 4. Exponenciální generující funkce (kompoziční a součinová formule, příklady). 5. P-rekurzivní posloupnosti  a D-konečné mocninné řady (uzávěrové vlastnosti, příklady).

Přednáška se konala ve středu 15:40 - 17:10 v S8.
1. přednáška 20.2.2008. Tři příklady použití vytvořujících (neboli generujících) funkcí: počet nekřížících se párování (Catalanova čísla), počet výstupů do schodů (Fibonacciova čísla) a rekurence pro počet souvislých grafů (použití  exponenciálních generujících funcí). text 1. přednášky.
2. přednáška 27.2.2008. Algebraická teorie mocninných řad: sčítání, násobení, skládání moc. řad, formální konvergence. text 2. přednášky.
3. přednáška 5.3.2008. Multipl. inverz jako součet nekonečné řady. Pár nekonečných součinů moc. řad. Skládání moc. řad je asociativní. Inverz moc. řady vzhledem ke skládání. Lagrangeova inverzní formule a dva příklady na ni. text 3. přednášky. (bude doplněno)
4. přednáška 12.3.2008. Skládání moc. řad není obecně asociativní (pro F = x + x2 +2x3 + 5x4 + 14x5 + ...,  G= x - x2 a H = 1 je F(G(H)) = F(0) = 0, ale (F(G))(H) = x(1) = 1), pouze za předpokladu, že mají nulové konstantní členy. Hlavní věta o racionálních generujících funkcích: posloupnost má racionální generující funkci <=> členy posloupnosti splňují lineární rekurenci s konstantními koeficienty <=> členy posloupnosti mají explicitní vyjádření ve tvaru lineární kombinace různých exponenciál s polynomiálními koeficienty. Příklad s počtem mřížových cest. text 4. přednášky. (bude doplněno)
5. přednáška 19.3.2008. Dokončení důkazu hlavní věty o racionálních generujících funkcích. Metoda přechodové matice.
6. přednáška 26.3.2008. Metoda přechodové matice, důkaz.  Přiklady na metodu přechodové matice: 1. počítání slov délky n nad abecedou {1,2,3}, neobsahujících jsko podslovo ani 11 ani 23, 2. ne moc úspěšný pokus o odvození vzorce pro generující funkci čtverců Fibonacciových čísel.
7. přednáška 2.4.2008. Tři postupy pro nalezení vzorce pro generující funkci čtverců Fibonacciových čísel: 1. metoda přechodové matice (čtverec Fn je počet slov délky n nad 9-prvkovou abecedou {MM, ML, MP, LM, LL, LP, PM, PL, PP} s jistým zakázanými podslovy), 2. metoda algebraická (Fn je kombinace exponenciál, takže jeho čtverec též a generující funkce je racionální) a 3. metoda nejpraktičtější a proto jediná dopočítaná (čtverec Fn je počet pokrytí obdélníku 2 krát n monominy M a dominy D=LP a každé takové pokrytí rozdělují svislé spáry jednoznačně na bloky, které už mají jednoduchou strukturu a snadno se spočtou).  Problém počtu rozměnění mince a souvislost s počítání mřížových bodů v mnohostěnech.
8. přednáška 9.4.2008. Odvození Popoviciuova vzorečku: p(n; a, b) = počet vyjádření n jako n=ra + sb, kde r, s jsou nezáporná celá čísla a a,b jsou daná nesoudělná přirozená čísla = n/ab + 1 - {b*n/a} - {a*n/b}, kde b* je 1/b modulo a, a* je 1/a modulo b a {.} je zlomková část.
9. přednáška 16.4.2008. Důkaz Ehrhartovy věty: Když je P mnohostěn v d-rozměrném euklidovském prostoru a jeho vrcholy jsou mřížové body (tj. mají celočíselné souřadnice), potom je funkce f(P,n) = "počet mřížových bodů ležících v nafouknutí nP" polynom v n. Má-li P vrcholy s racionálními souřadnicemi, je f(P,n) kvazipolynom (a každé m, pro něž jsou vrcholy mP mřížové, je periodou f(P,n)).
10. přednáška 23.4.2008. Dualita pro počty mřížových bodů v mnohostěnech:  f(P, -n) = (-1)dim(P) f(int(P), n), kde int(P) je relativní vnitřek mnohostěnu P; bez důkazu. Odvození, za pomoci této duality, vzorce pro počet polomagických čtverců 3 x 3 se sumou t: t4/8 + 3t3/4 + 15t2/8 + 9t/4 + 1. Exponenciální generující funkce: součinová a kompoziční formule.
11. přednáška 30.4.2008. Příklady použití exp. generujících funkcí: Bellova a Stirlingova čísla, odvození Cayleyho formule pro počet stromů na množině {1, 2, ..., n}, exp. generující funkce 2-regulárních grafů. Odvození rekurence pro počet 2-regulárních grafů na {1, 2, ..., n}: a(0)=1, a(1)=a(2)=0, a(3)=1 a a(n+1) = n.a(n) + n(n-1)a(n-2)/2 pro n>1.
12. přednáška 7.5.2008. P-rekurzivní posloupnosti a D-konečné mocninné řady. Uzávěrové vlastnosti třídy D-konečných mocninných řad: posloupnost je P-rekurzivní <=> její OGF je D-konečná; součet, součin a Hadamardův součin D-konečných mocninných řad je D-konečný; algebraická mocninná řada je D-konečná; složenina D-konečné a algebraické mocninné řady je D-konečná. 
13. přednáška 14.5.2008. Pro rektorský (sportovní) den přednáška odpadla.
14. přednáška 21.5.2008. Příklad odvození rekurence pro koeficienty algebraické mocninné řady: Schroederova čísla = počet rozřezání konvexního n-úhelníku nekřížícími se úhlopříčkami. Motzkinova čísla = počet částečných nekřížících se párování s n vrcholy, detaily za DOM CV.

květen 2008