Kombinatorické počítání DMI015

Přednáška je v pondělí v 15:40-17:10 v S7 na Malé Straně.

Přednáška se zabývá kombinatorickou enumerací a technikou generujících (vytvořujících) funkcí, která bude ilustrovaná na příkladech. Literatura: R. P. Stanley, Enumerative Combinatorics. Volumes I (1986) and II (1999). Můj učební text z r. 1999: ps soubor a pdf soubor.

Zkoušky. Tři termíny jsou vypsané v SISu, jiné jsou též možné, po domluvě se zkoušejícím (v týdnu 11.-15.6. budu ale v zahraničí). Zkušební otázky: 1. Vlastnosti Catalanových čísel. 2. Součinová a kompoziční formule pro EGF a její použití. 3. Algebraické vlastnosti mocninných řad - opreace s moc. řadami. 4. Lagrangeova inverzní formule a její použití. 5. Racionální moc. řady: odvození rekurence pro počet vodorovně konvexních polymin. 6. Racionální moc. řady: asymptotika počtů rozkladů čísla n na části z konečné množiny A. 7. Racionální moc. řady: metoda přechodové matice a její použití.

1. přednáška 26.2.2007. 1. Co to je enumerativní kombinatorika?  Úvodní příklad s Catalanovými čísly a počítáním (zakořeněných rovinných) stromů.  text 1. přednášky.

2. přednáška 5.3.2007. Parita Catalanových čísel: cn  je liché, právě když n je mocnina dvojky. Odtud plyne, že Catalanova čísla nesplňují žádnou lineární rekurenci s konstantními koeficienty. Kombinatorický důkaz vzorce cn  =  binom(2n - 2, n - 1) / n pomocí mřížových cest a triku se zrcadlením. Catalanova čísla a pravděpodobnost konvexity. text 2. přednášky.

3. přednáška 12.3.2007. 2. Generující funkce a kombinatorické struktury.  Obyčejné a exponenciální generující funkce (OGF a EGF).  Sčítání a násobení mocninných řad s jednou proměnnou.  M. řady s operacemi sčítání a násobení tvoří obor integrity. M. řada má multiplikativní inverz, právě když má nenulový konstantní člen.  Formální geometrické řady. Posloupnost Stirlingových čísel (S(0, k), S(1, k), ...), což jsou počty rozkladů n-prvkové množiny na k bloků, má OGF rovnou xk / (1 - x)(1 - 2x)...(1 - kx) . Číslo n má 2n - 1 kompozic (vyjádření ve tvaru uspořádaného součtu přirozených čísel) a binom(n - 1, k - 1) kompozic s k částmi - odvození pomocí OGF. text 3. přednášky.

4. přednáška 19.3.2007. Součinová konstrukce a součinová formule pro EGF. Příklad: EGF Stirlingových čísel je rovna (ex - 1)k/k! . Formální konvergence mocninných řad, nekonečné řady a součiny mocninných řad. Příklad: dvě OGF počtů číselných rozkladů n na různé části a na části bez omezení ve tvaru nekonečných součinů (1 + x)(1 + x2)(1 + x3) ... a  1/(1 - x)(1 - x2)(1 - x3) ... . Operace skládání mocninných řad (substituce). Příklad: explicitní tvar multiplikativního inverzu. text 4. přednášky.

5. přednáška 26.3.2007. Kombinatorický význam skládání OGF. Příklady: 1. počet kompozic čísla n je 2n - 1 , 2. počet vnoření koštěte do n-vrcholového (zakořeněného rovinného) stromu je (4n - 1 + binom(2n - 2, n - 1)) / 2. Kombinatorický význam skládání OGF: kompoziční formule. Příklady: EGF rozkladů na k-prvkové bloky, na k bloků a na libovolné (neprázdné) bloky. text 5. přednášky.

6. přednáška 2.4.2007. Důkaz kompoziční formule pro EGF. Vzorec pro počet rozkladů na 2-prvkové bloky pomocí EGF a pomocí indukce. Ještě tři aplikace kompoziční formule: vzorec pro EGF počtů sn surjekcí z [n] na [m]; rekurence pro počty souvislých grafů; rekurence pro počty 2-regulárních grafů.  text 6. přednášky.

7. přednáška 9.4.2007. Cvičení: skládání moc. řad je asociativní. Tvrzení: Moc. řada f s ord(f) = 1 má jednoznačně určený kompoziční inverz g = f <-1>, pro který platí f(g) = g(f) = x. Důkaz pomocí porovnávání koeficientů. Lagrangeova inverzní formule (LIF), zatím bez důkazu. Aplikace LIF: formule pro počet zr stromů, kde každý vrchol má 5 dětí nebo žádné; jiné odvození formule pro Catalanova čísla; odvození Cayleyho formule n n - 2 pro počet stromů na množině {1, 2, ..., n}. Podílové těleso moc. řad C[[x]] je tvořeno Laurentovými řadami C((x)) (což jsou moc. řady s konečně mnoha sčítanci se záporným exponentem). text 7. přednášky (zatím ne).

16.4.2007. Přednáška odpadla - Velikonoční pondělí.

8. přednáška 23.4.2007. Formální derivování moc. (popř. Laurentových) řad a jeho vlastnosti: linearita, Leibnizova formule, řetízkové pravidlo, derivace podílu, moc. řady s rovnými derivacemi se rovnají až na aditivní konstantu. Formální exponenciála, binomický rozvoj a logaritmus. Důkazy identit pro tyto formální rozvoje. Důkaz Lagrangeovy inverzní formule. text 8. přednášky (zatím ne).

9. přednáška 30.4.2007. 3. Racionální mocninné řady v enumeraci. Fibonacciova čísla. Hlavní věta o rac. moc. řadách: moc. řada je racionální <=> její koeficienty splňují lineární rekurenci s konstantními koeficienty <=> její koeficienty jsou vyjádřeny lin. kombinací exponenciál s polynomiálními koeficienty. Počítání mřížových cest s kroky N, W a E, které sebe sama neprotínají.  text 9. přednášky (zatím ne).

10. přednáška 7.5.2007. Počítání vodorovně konvexních polymin (odvození lineární rekurence pomocí m. řady se dvěma proměnnými). Kvazipolynomy  a charakterizace kvazipolynomů pomocí jejich generující funkce. Příklad kvazipolynomu: pA(n)  = počet rozkladů n na části z (konečné) množiny A. Příklad s A = {1, 2, 3}. Obecně platí: pA(n) je kvazipolynom a pA(n) = nk - 1 / (součin prvků v A).(k-1)! + O(nk - 2). text 10. přednášky (zatím ne).

11. přednáška 14.5.2007. Metoda přechodové matice (transfer matrix method): ogf vah cest délky n v daném orientovaném grafu s váženými hrananami, s předepsaným začátečním a koncovým vrcholem, je složka inverzní matice k jisté matici s polynomiálními složkami - tato ogf je tedy racionální. Příklady. text 11. přednášky .

12. přednáška 21.5.2007. Počítání mřížových bodů v mnohostěnech pomocí racionálních mocninných řad - informativně.

červen 2007