Kombinatoricke pocitani DMI015

• 21. 2. 2001 Catalanova cisla (rekurence, generujici funkce,  rovnice pro GF, vzorecek pro GF, vzorece pro C. cisla, rychlost rustu). Dva dukazy faktu, ze C. cisla pocitaji rovinne zakorenene stromy na n vrcholech: (i) pomoci GF a (ii) zrcadlenim mrizovych cest. Definice P-rekurzivni posloupnosti a poznamka (bez dukazu), ze koeficienty algebraicke mocninne rady tvori P-rek. posloupnost.
• 28. 2. 2001 Rekapitulace minule prednasky. Zakladni veta o rekurencich s konstantnimi koeficienty: (i) OGF posloupnosti je podil dvou polynomu, ekvivalentne (ii) posloupnost splnuje rekurenci s konstantnimi koeficienty, ekvivalentne (iii) n-ty clen posloupnosti je lin. kombinace exponenciel v n s polynomialnimi (v n) koeficienty. Priklad: mrizove cesty s tremi typy jednotkovych kroku (E, W, N), ktere samy sebe neprotinaji.
• 7. 3. 2001 Schroederova cisla: pocitaji rozrezani konvexniho mnohouhelnika (=systemy neprotinajicich se uhlopricek). Odvozeni P-rekurence pro Schroderova cisla. Priklady dalsich struktur pocitanych Schr. cisly. Zacatek dukazu faktu, ze koeficienty algebraicke mocninne rady tvori P-rekurzivni posloupnost.
• 14. 3. 2001 Dokonceni dukazu z minule prednasky. K cemu jsou dobre integraly, zejmena Wallisuv, a integrace per partes: dukaz Stirlingovy formule n! ~ (2.pi.n)^{1/2}.(n/e)^n. Priklady dalsich struktur pocitanych Catalanovymi cisly (bez dukazu), napr.: pravdepodobnost jevu, ze n bodu nahodne a vzajemne nezavisle vybranych z jednotkoveho ctverce tvori konvexni retezec podminena jevem, ze techto n bodu jiz tvori konv. n-uhelnik, je rovna 1/c_n; kde c_n=B(2n-2, n-1)/n [vysledek P. Valtra].
• 21. 3. 2001 Odvozeni pravdepodobnosti, ze n nahodnych bodu ve ctverci tvori konvexni retezec. Bijektivni dukaz pomoci parovani toho, ze Catalanova cisla pocitaji stromy.
• 28. 3. 2001 Narayanova cisla n(a,b) pocitajici stromy s a vrcholy a b listy, dukaz symetrie n(a,b) = n(a,a-b) pomoci generujici funkce o dvou promennych. Hratky s obrazci neboli rovnobeznikovymi polyminy: pocet obrazcu velikosti n je B(2n-2, n-1)/n a celkova plocha vsech obrazcu velikosti n je 4^{n-2}. Dukazy rekurencemi a pomoci generujicich funkci.
• 4. 4. 2001 Dukaz pomoci GF toho, ze pocet vsech porovnatelnych dvojic vrcholu (u,v) v V(T) X V(T) ve vsech n-vrcholovych stromech T je 4^{n-1}. Chenova bijekce [W. Y. C. Chen, Proc. Natl. Acad. Sci. USA 87 (1990), 9635-9639]: ex. bijekce mezi Schroderovymi stromy T s n vrcholy a k bloky a lesy F s n+k-1 vrcholy a k malymi stromy jako komponentami. Popis a priklad zobrazeni F -> T.
• 11. 4. 2001 Popis opacneho zobrazeni T -> F. Dusledky Chenovy bijekce: pocet rov. stromu s n+1 vrcholy je B(n,n)/(n+1), pocet rov. stromu s n+1 vrcholy a k listy je B(n+1,k).B(n-1,n-k)/(n+1) (Narayanova cisla), pocet rov. stromu s n vrcholy majicich n_i vrcholu stupne i je M(n; n_0, n_1, ..., n_m)/n (M je multinomicky koeficient a n_0 je pocet listu) a dusledek tohoto dusledku: pocet k-arnich rov. stromu (stupne jsou 0 nebo k) s kn+1 vrcholy je B(kn+1, n)/(kn+1). Posledni vysledek lze tez ziskat Lagrangeovou inverzni formuli, jeji formulace.
• 18. 4. 2001 a 25. 4. 2001 Prednaska odpadla kvuli Jarni kombinatoricke skole.
• 2. 5. 2001 Lagrangeova inverzni formule. Pouziti pri pocitani nezavislych mnozin ve stromech: celkovy pocet vsech nez. mnozin (vcetne prazdne) ve vsech (zakorenenych rovinnych) stromech na n vrcholech je B(3n-3,n)/(n-1). Dukaz LIF pomoci Laurentovych rad a rezidui.
• 9. 5. 2001 Exponencialni generujici funkce posloupnosti (a_n) je mocninna rada a_0. x^0/0!+a_1. x^1/1!+... . Soucinova formule: jsou-li F(x), G(x) a H(x) EGF poctu struktur, kde H-struktura vznikla soucinovou konstrukci z F-struktury a G-struktury, plati H(x)=F(x).G(x). Kompozicni formule: podobne, vznikla-li H-str. slozenim F-str. a G-str., plati H(x)=F(G(x)). Pouziti teto teorie: odvozeni Cayleyho vzorce pro pocet oznacenych stromu s n vrcholy (n^{n-2}) a vzorec pro EGF Bellovych cisel B_n (=pocet rozkladu n-prvkovr mnoziny). Dobinskiho vzorec pro Bellova cisla: 0^m/0!+1^m/1!+2^m/2!+... = e.B_m (e=2.71828...) a jeho dukaz pomoci linearni algebry a kombinatoriky. Stirlingova cisla druheho druhu a reprezentace rozkladu pomoci normalnich slov.
• 16. 5. 2001 Ruzne vztahy pro Bellova a Stirlingova cisla. Jsou-li B_n Bellova cisla a  B(x) jejich obycejna gen. funkce, plati B(x)=1+(x/(1-x)) . B(x/(1-x)), tj. B(x/(1+x))=1+x . B(x). Dale B(x)=1 + x/(1-x) + x^2/((1-x) (1-2x)) + ... . Plati rekurence B_n=B(n-1,0) . B_0+B(n-1,1) . B_1+...+B(n-1,n-1) . B_{n-1}, kde B(. , .) je binomicky koeficient. OGF Stirlingovych cisel S(n,k) je rovna (pro pevne k) x^k . ((1-x)(1-2x)...(1-kx))^{-1}. Pro tato cisla plati fmle S(n,k)=(k!)^{-1} . sum_{j=0}^k (-1)^j . B(k , j) . (k-j)^n. Jejich EGF je (e^x-1)^k/k!. Plati rekurence S(n,k)=S(n-1,k-1) + k . S(n-1,k). Vypocet Bellovych cisel pomoci konecnych diferenci (bez dukazu). Asymptotika Bellovych cisel (bez dukazu): B_n ~ n^{-1/2} . w^{n+1/2} . exp(w-n-1), kde w . log(w)=n.
• 23. 5. 2001 Prednaska odpadla-pobyt na konferenci.

kveten 2001