Kombinatorické počítání DMI015


Přednáška se koná v pátek ve 14:00-15:30 v K9 (budova v Karlíně). 
20.5. přednáška odpadá!
Termíny zkoušek: jsou vypsány v SISu na 7., 16. a 28. června, další (v létě, v září) po dohodě.
Zkušební otázky: 1. Vlastnosti Catalanových čísel. 2. Popište algebraickou teorii formálních mocninných řad (bez Lagrangeovy inverzní formule). 3. Lagrangeova inverzní formule a její aplikace. 4. Rekurence pro počet rozřezání n-úhelníka (Schroederova čísla). 5. Pentagonální identita pro partitní funkci p(n), rekurence pro p(n). 6. Cohenova-Remmelova identita pro počty rozkladů se zakázanými podrozklady. 7. Exponenciální generující funkce a jejich aplikace. 8. Uveďte a odvoďte vzorce pro Bellova a Stirlingova čísla (rekurence, ogf, egf, explicitní formule). 9. Dokažte horní odhad na p(n) a odvoďte asymptotiku pro pA(n) (buď indukcí nebo pomocí ogf). 10. Odvoďte rekurenci pro počet vodorovně konvexních polymin.  
1. přednáška 25.2.2005. Stromy a Dyckovy cesty. Zakořeněné rovinné stromy, jejich počty tn a generující funkce T(x) = t1x + t2x2 + t3x3 +... = x + x2 +2x3 + ... . Odvození rovnic T(x)2 - T(x) + x = 0  a T(x) = (1 - (1 - 4x)1/2) / 2 a odvození vzorce tn = binom(2n - 1, n - 1) / n - jsou to Catalanova čísla! Dvě rekurence: tn = t1tn-1 + t2tn-2 + ...+ tn-1t1 (n > 1, t1 = 1) a   tn+1 = tn(4n - 2) / (n + 1). Odvození druhé rekurence z explicitní formule pro tn, z explicitní formule pro T(x)  a z kvadratické rovnice pro T(x). Použití  první rekurence pro určení parity Catalanových čísel (je neperiodická, tn je liché, právě když n je mocnina dvou). Asymptotika Catalanových čísel pomocí Stirlingovy formule. Dyckovy cesty a jejich kombinatorická dekompozice, zase je počítají Catalanova čísla.
2. přednáška 4.3.2005. Algebraická teorie mocninných řad. Moc. řady C[[x]] tvoří komutativní okruh s jednotkovým prvkem a nemají dělitele nuly. Řád m. řady ord(f). Formální konvergence posloupností m. řad.  Nekonečné součty a součiny m. řad. Jednotky v okruhu m. řad jsou ty z nich, co mají nenulový absolutní člen.  Substituce jedné m. řady do druhé. Laurentovy řady C((x)) (podílové těleso C[[x]]).  Inverzní moc. řada.  Lagrangeova  inverzní formule; bez důkazu. Aplikace LIF: Catalanova čísla a počty ternárních rovinných stromů.
3. přednáška 11.3.2005. Úložka: počty nekřížících se stromů na {1, 2, ..., n} se dají spočítat pomocí počtů ternárních rovinných stromů. Důkaz Lagrangeovy inverzní formule. Další příklady na LIF: odvození Cayleyovy formule pro počet všech stromů na  {1, 2, ..., n}; formule pro součet prvních n členů v binom. rozvoji (1 - 1/2)-n; koeficient u x-1 v rozvoji (1/ tan x)n. Formální derivace a její vlastnosti (linearita, Leibnizova formule, derivace složené moc. řady), dokazování identit derivováním. Moc. řady exp(x), log(1 / (1 - x)) a (1 + x)a a identity pro ně: exp a log jsou vzájemně inverzní, log (1 + x)a = a.log(1 + x),((1 + x)a)b = (1 + x)ab,exp(x + y) = exp(x).exp(y). Algebraický uzávěr tělesa Laurentových řad C((x)) jsou Pusieuxovy řady (=Laurentovy řady se zlomkovými exponenty); bez důkazu.   
Přednášky 18.3. a 25.3. odpadají pro zahraniční služební cestu přednášejícího!
4. přednáška 1.4.2005. Obecné pojetí operací s generujícími funkcemi. Kombinatorická třída, její počítací posloupnost, izomorfismus komb. tříd, ogf (obycejná generující funkce) komb. třídy. Přípustné konstrukce pro komb. třídy: součet (= disj. sjednocení) +, (kartézský) součin X, posloupnost S(.), multimnožina M(.), množina P(.) a cyklus C(.). Věta (překlad těchto konstrukcí do ogf): 1. součtu odpovídá součet ogf B(z) + C(z), 2. součinu odpovídá součin ogf B(z)C(z), 3. posloupnosti odpovídá 1/(1 - B(z)), 4. multimnožině odpovídá (1 - z)-b(1)(1 - z2)-b(2)... = exp(B(z) + B(z2)/2 + ...), 5. množině odpovídá (1 + z)b(1)(1 + z2)b(2)... = exp(B(z) - B(z2)/2 + B(z3)/3 - ...) a 6.  cyklu odpovídá (fi(1)/1).log(1/(1 - B(z))) + (fi(2)/2).log(1/(1 - B(z2))) + ..., kde fi(n) je Eulerova funkce.
5. přednáška 8.4.2005. Překlad omezení na počty komponent v posloupnostech ((multi)množinách) do ogf. Zadání (specifikace) komb. tříd pomocí rovnic. Příklad  se Schroderovými čísly: počet rozřezání n-úhelníka.
6. přednáška 15.4.2005. Kompozice a rozklady čísel. Kompozice čísel, formule pro jejich počty a pro jejich ogf, cyklické kompozice. Rozklady čísel, Ferrersův diagram rozkladu, dvojí rekurence pro počet všech rozkladů p(n): pomocí logaritmické derivace a pentagonální identita, jejíž důkaz bude příště.
7. přednáška 22.4.2005. Důkaz pentagonální identity pomocí involuce na Ferrersových diagramech (přesouvání základny a sklonu). Odvození rekurence s(n) = s(n-1) +  s(n-2) -  s(n-5) - s(n-7) + s(n-12) + s(n-15) - ..., s(0) = s(n-n) := n, pro funkci s(n) = součet dělitelů čísla n (1, 2, 5, 7, 12, 15, ... jsou pětiúhelníková čísla). Eulerova jednodušší identita (pocet rozkladů n na různé části je týž jako pocet rozkladů na liché části), důkaz pomocí gen. funkcí a pomocí bijekce.
8. přednáška 29.4.2005. Multimnožiny, jejich obsahování, součty a sjednocení. Obecná identita (Cohen; Remmel) pro počty rozkladů se zakázanými podrozklady a její důkaz pomocí PIE. Čtyři důsledky. Exponenciální generující funkce. Součinová a kompoziční formule. Bellova čísla.
9. přednáška 6.5.2005.  Cayleyova formule (počet stromů na [n] je nn-2) a její důkaz pomocí EGF. Počítání 2-regulárních grafů na [n] pomocí EGF, odvození rekurence d(n+1) = n.d(n) + n(n-1).d(n-2)/2. Bellova čísla b(n) a Stirlingova čísla S(n, k).  Rekurence, "Bellův" trojúhelník,  formule pro OGF a EGF Stirlingových čísel, EGF pro Bellova čísla, funkcionální  rovnice pro  OGF Bellových čísel. Explicitní formule pro S(n, k) (součet exponenciál) a b(n) (Dobinského formule), zbývá nám ještě dokončit Dobinského formuli.  
10. přednáška 13.5.2005. Dokončení Dobinského formule. Schema bijektivního důkazu identity: Počet rozkladů [n], v nichž každých i <= k po sobě jdoucích čísel leží v i různých blocích, je roven počtu všech rozkladů [n-k+1] bez omezení. Pár asymptotik. Důkaz odhadu p(n) < (pi/(6(n-1)1/2)).exp(pi.(2n/3)1/2) pro partitní funkci pomocí ogf.  Nechť pA(n) označuje počet rozkladů  čísla n na části brané z množiny A. Pokud A sestává z k vesměs nesoudělných (přirozených) čísel a s označuje jejich součin, pak pA(n) = nk-1/(s(k-1)!) + O(nk-2); důkaz indukcí podle k.
20.5. přednáška odpadá!
11. přednáška 27.5.2005. Hlavní věta o racionálních generujících funkcích: následující vlastnosti mocninné řady f(x) = a(0) + a(1)x + a(2)x2 + ... jsou ekvivalentní: (i)  f(x)  je racionální, tj. f(x) = p(x) / q(x) pro dva polynomy p a q, (ii) koeficienty a(i) splňují lineární rekurenci s konstantními koeficienty a (iii) a(i) je lineární kombinací exponenciál s algebraickými základy a polynomiálními koeficienty. Asymptotika koeficientů racionálních gen. funkcí pomocí rozkladu na parciální zlomky; odvození asymptotiky pro pA(n) touto metodou. Odvození rekurence a(n) - 5a(n-1) +7a(n-2) - 4a(n-3) = 0 (n > 4) pro počet vodorovně konvexních polymin.

červen 2005