Kombinatorické počítání DMI015

Přednáška bude z téže oblasti jako v předchozích letech - kombinatorická enumerace, tj. počítání různých struktur a potvor, jako jsou stromy, číselné rozklady, posloupnosti, permutace atd. Jedním z internetově dostupných textů o enumeraci je Flajolet a Sadgewick, viz kapitoly 1-9 jejich připravované knihy. 

Zkouška. Domluva emailem. Nebudu zde od 2. do 6. června a od 23. do 27. června. Jinak jsem přístupný i termínům v létě. Okruhy ke zkoušce:
1. Vlastnosti racionálních gen. funkcí a příklady. 2. Metoda přechodové matice a příklady na ni. 3. Vlastnosti algebraických gen. funkcí (posloupnosti jejich koeficientů jsou P-rekurzivní) a příklady. 4. Lagrangeova inverzní formule a její aplikace. 5. Kompoziční formule a její aplikace.


24.2.2003 Rozdán rozmnožený textík o Catalanových číslech.

3.3.2003 Základní vlastnosti mocninných řad. Formální konvergence moc. řad, substituce jedné moc. řady do druhé. Moc. řada f má multiplikativní inverz iff ord(f)=0. Každá f = a1.x + a2.x2 +..., a1 nenulové, má jednoznačně určený kompoziční inverz. Zmínka o Laurentových řadách a Puiseuxových řadách. 

10.3.2003 Základní věta o racionálních mocninných řadách: Že a0 + a1.x + a2.x2 +... = P(x)/Q(x), kde P má stupeň menší než Q a Q má konstantní člen 1, je ekvivalentní tomu, že posloupnost (a0, a1, ...) splňuje lin. rekurenci an+d + b1.an+d-1 + ... + bd.an = 0, což  je ekvivalentní tomu, že an = P1(n).(c1)n + ... + Pk(n).(ck)n, kde Q(x) = (1-c1.x)d_1.(1-c2.x)d_2 ... (1-ck.x)d_k, cijsou různé kořeny a Pi je polynom stupně menšího než di. Dvě úlohy vedoucí na racionální generující funkce: (i) počet slov délky n nad {N, W, E}, v nichž není E a W nikdy vedle sebe, a (ii) počet vodorovně konvexních polymin s n čtverečky.

17.3.2002 Metoda přechodové matice (transfer matrix method): Nechť D je orientovaný graf na vrcholech v1, ..., vp (násobné hrany a násobné smyčky jsou povoleny), jehož hrany e mají váhy w(e) a tahy e1 e2 ...en mají váhy w(e1).w(e2)...w(en). Nechť Aij(n) je součet vah cest délky n z vido vj a matice A je definována Aij = Aij(1) (=součet vah hran spojujících via vj). Pak Aij(0) + Aij(1).x1 + Aij(2).x2 +... = (-1)i+j.det(I-xA: j,i)/det(I-xA), kde I je jednotková pxp matice a matice v čitateli vznikne vynecháním j-tého řádku a i-tého sloupce. Příklad: počet slov délky n nad {1, 2, 3}, která neobsahují ani ...11... ani ...23... . Tvrzení: Každá taková úloha o počtu slov délky n nad konečnou abecedou S, která neobsahují jako souvislé podslovo žádné slovo z dané konečné množiny slov F nad S, vede pomocí přechodové matice na racionální generující funkci.

24.3.2003 Úloha o počtu krotkých permutací: Kolik je permutací pi čísel 1, 2, ..., n, které splňují p(i) - i = 0, -1, 1 ? První složité řešení pomocí přechodové matice. Faktorizace slov ve volném monoidu. Je-li B množina slov nad abecedou A taková, že každé slovo z B* se rozkládá jednoznačně na faktory z B, pak gf daná součtem x|u|, u z B* (|u| je délka u), se rovná 1/(1 - součet x|u|, u z B). Řešení touto metodou (i) úlohy o krotkých permutacích a (ii) odvození fmle pro generující funkci čtverců Fibonacciových čísel.

31.3.2003 Algebraické generující funkce. Připomenutí Catalanových čísel: jejich ogf je (1 - (1-4x)1/2)/2. Narayanova čísla N(a, b) (počet zakořeněných rovinných stromů s a vrcholy a b listy): jejich ogf je (1-x+xy - ((1-x+xy)2 - 4xy)1/2)/2. Důkaz symetrie N(a, b) = N(a, a-b) pomocí tohoto vzorce. Schröderova čísla S_n (počet rozřezání konv. n+2-úhelníka): jejich ogf je (1-3x - (1-6x+x2)1/2)/4x. Odvození rekurence (n+1)Sn - (6n-3)Sn-1 + (n-2)Sn-2 = 0.

7.4.2003 Rychlost růstu Schröderových čísel: zhruba jako (3 + 2.21/2)n. Další struktury jimi počítané: např. počet stromů s n vrcholy, v nichž každý list je buď červený nebo modrý (ve vzorci odvozeném na minulé přednášce stačí položit y = 2), nebo počet pokrytí pagody dominy. Tvrzení: posloupnost čísel je P-rekurzivní (splňuje lineární rekurenci s polynomiálními koeficienty), právě když je její generující funkce D-konečná (splňuje lineární diferenciální rovnici s polynomiálními koeficienty). Věta: algebraická mocninná řada má vždy za koeficienty P-rekurzivní posloupnost (rekurence pro Schröderova čísla tedy není vůbec náhodná).

14.4.2003 Lagrangeova inverzní formule: Jsou-li f(x) = a0 + a1.x + ... a g(x) = x + b2.x2 + ... dvě mocninné řady, potom se koeficient u xn v f(g(x)<-1>), kde g(x)<-1> je funkcionální inverz g(x), rovná koeficientu u xn-1v n-1.f(x)'.(x/g(x))n; zatím bez důkazu. Aplikace a příklady na LIF: ternární stromy, řešení kvadratické rovnice definující Catalanova čísla pomocí LIF, řešení rovnice g(x) = x.eg(x) pomocí LIF. Počítání jednoduchých permutací, které dokončíme příště. (Permutace čísel 1, 2, ..., n  je jednoduchá, když nezobrazuje žádný interval I, 1 < |I| < n, na interval.)

21.4.2003 Velikonoční pondělí - přednáška odpadla.

28.4.2003 Dokončení enumerace jednoduchých permutací. Jedna aplikace Lagrangeovy inverzní formule: Je-li tn koeficient u xn v kompozičním inverzu k 1!.x + 2!.x2+ ..., pak ord2(tn) >= (n-1)/2 (vlevo je největší m, že 2m dělí tn).

5.5.2003 Odvození Narayanový čísel pomocí LIF. Důkaz LIF. Součinová a kompoziční konstrukce a odpovídající formule pro exponenciální generující funkce. Příklady exp. gen. funkcí: Bellova čísla a Stirlingova čísla. 

12.5.2003 Přednáška odpadla kvůli Jarní komninatorické škole. 

19.5.2003 Odvození Cayleyova vzorce nn-2 pro počet stromů na {1, 2, ..., n} pomocí kompoziční formule a LIF. Exp. gen. funkce pro počty 2-regulárních grafů. Obyčejná gen. funkce Stirlingových čísel: S(1, k).x + S(2, k).x2 + ... = xk/(1-x)(1-2x)...(1-kx). Dobinského formule pro Bellova čísla: 1n/1! + 2n/2! + 3n/3! + ... = e.Bn.

květen 2003