Vyuka - Martin Klazar

Místo a čas přednášky: pondělí od 9 h v S1.

Plán přednášky pro LS 2012. Přednáška bude věnována kombinatorické enumeraci, použití generujících funkcí při odvozování přesných a asymptotických enumerativních výsledků (=počítání různých diskrétních struktur, např. grafů, stromů, slov, permutací, rozkladů množin, obarvení, ...).

Zkušební otázky. 1. Dokažte, že (i) přirozená čísla {1, 2, ...} nelze rozložit na dvě či více aritmetických posloupností se vzájemně různými diferencemi a že (ii) neexistuje taková k-tice celých čísel a_1 < a_2 < ... < a_k, pro k > 4, že vzdálenosti a_j - a_i, j > i, probíhají přesně čísla 1, 2, ..., k(k-1)/2. 2. Dokažte (kombinatoricky nebo počítáním s moc. řadami) Eulerovu pentagonální identitu. 3. Dokažte součinovou a kompoziční formuli pro exponenciální generující funkce a uveďte aplikace. 4. Dokažte Lagrangeovu inverzní formuli a uveďte aplikace. 5. Odvoďte vzorec v metodě přechodové matice a uveďte jeho kombinatorické použití. 6. Dokažte, že počet mřížových bodů ležících v n-tém nafouknutí daného mřížového mnohostěnu (v R^d) je polynom v n. 7. Dokažte, že počty a_n konfigurací nekřížících se úhlopříček v (konvexním) n-úhelníku pro n > 2 splňují rekurentní vztah (n+1)a_{n+2} - (6n-3)a_{n+1} + (n-2)a_n = 0.

1. přednáška 27. 2. 2012. Úvod. Příklad s Catalanovýmí čísly (c_n počítá zakořeněné rovinné stromy s n vrcholy, vzorec pro c_n pomocí generující funkce získané vyřešením kvadratické rovnice, rekurence pro c_n, c_n je liché, právě když n=2^m (tudíž se c_n nedají počítat, narozdíl od Fibonacciových čísel, žádnou lineární rekurencí s konstantními koeficienty), asymptotika c_n pomocí Stirlingovy formule). Příště ještě dva příklady na použití generujících funkcí: 1) Přirozená čísla 1, 2, ... nelze rozložit (na alespoň dvě) aritmetické posloupnosti se vzájemně různými diferencemi. 2) Neexistuje k > 4 celých čísel tak, že jejich k(k-1)/2 vzájemných vzdáleností jsou právě čísla 1, 2, ..., k(k-1)/2; pro k = 4 je protipříkladem čtveřice 0, 1, 4, 6. Postupoval jsem podle mých dávných skriptíček Kombinatorické počítání z r. 1999.

2. přednáška 5. 3. 2012. Dva zmíněné příklady na použití generujících funkcí. V př. 1 jsme ukázali, že když takový rozklad N na vzájemně disjunktní aritmetické posloupnosti existuje (např. N = (0+2N) U (1+4N) U (3+4N)), pak každá diference musí dělit nějakou jinou. Když se dovolí, aby se aritmetické posloupnosti v rozkladu protínaly, pak už rozklady se vzájemně různými diferencemi existují (tzv. pokrývající kongruence). Algebraická teorie mocninných řad. Operace v okruhu formálních moc. řad (C[[x]], +, .) (Cauchyův součin). Řád mocninné řady. Jednotky jsou právě moc. řady s nulovým řádem, tj. s nenulovým konstantním členem.

3. přednáška 12. 3. 2012. Rovnost 1/(1 - x - x^2) = a/(1 - bx) + c/(1 - dx) (rozklad generující funkce Fib. čísel na parciální zlomky) lze chápat alespoň třemi způsoby: v C[[x]], v C(x) a jako mezi funkcemi. Formální konvergence posloupností moc. řad, nekonečné řady a nekonečné součiny moc. řad. Pár identit s nekonečnými součiny: 1) (1 + x)(1 + x^2)(1 + x^4)(1 + x^8) ... = 1 + x + x^2 + x^3 + ... = 1/(1 - x), 2) Eulerova: (1 + x)(1 + x^2)(1 + x^3)(1 + x^4) ... = 1/((1 - x)(1 - x^3)(1 - x^5)(1 - x^7)...) , 3) Eulerova pentagonální: (1 - x)(1 - x^2)(1 - x^3)(1 - x^4) ... = 1- x - x^2 + x^5 + x^7 -x^{12} - x^{15} + x^{22} + x^{26} - ... a 4) Jacobiho třísoučinová: 1 + (z + 1/z)x + (z^2 + 1/z^2)x^4 + (z^3 + 1/z^3)x^9 + (z^4 + 1/z^4)x^{16} + ... = prod_{m>0}(1 - x^{2m})(1 +zx^{2m - 1})(1 + (1/z)x^{2m - 1}). Důkazy 1) a 2), důkaz 3) příště, 4) bez důkazu.

4. přednáška 19. 3. 2012. Důkaz pentagonální identity pomocí počítání s moc. řadami. Formální derivace moc. řad a identita (A_1.A_2. ...)' / (A_1.A_2. ...) = A_1' / A_1 + A_2' / A_2 + ... (logaritmická derivace). Aplikace na pentagonální identitu dává rekurenci pro funkci součtu dělitelů s(n) = s(n-1) + s(n-2) - s(n-5) - s(n-7) + ..., kde s(n-n) = n. Skládání moc. řad: F(G) je definována, pokud G(0) = 0. Je asociativní, dk. příště. Zobecněné skládání, kde je složenina F(G) navíc definována i pokud je F polynom, asociativní není.

5. přednáška 26. 3. 2012. Důkaz asociativity skládání moc. řad f o (g o h) = (f o g) o h; svádí se to ke komutativitě (f_1 + f_2 + ...) o g = f_1 o g + f_2 o g + ... a (f_1f_2) o g = (f_1 o g)(f_2 o g), což zase plyne z identit (f_1 + f_2 + ...) + (g_1 + g_2 + ...) = (f_1 + g_1) + (f_2 + g_2) + ... a (f_1 + f_2 + ...)(g_1 + g_2 + ...) = sum_n sum_k (f_k.g_{n-k}) (formální konvergence). Tvrzení o existenci, jednoznačnosti a rovnosti levého a pravého kompozičního inverzu moc. řady. Příklad neasociativity zobecněného skládání moc. řad: když f = x + x^2 + 2x^3 + 5x^4 + 14x^5 + ..., g = x - x^2 a h = 1, tak (f o g) o h = x o 1 = 1, ale f o (g o h) = f o (1 - 1^2) = 0. Kombinatorický význam skládání moc. řad. Exponenciální generující funkce (EGF), součinová formule a kompoziční formule. Bellova čísla počítající množinové rozklady mají EGF exp(exp(x) - 1), další příklady (Cayleyho formule pro počet stromů aj.) příště.

6. přednáška 2. 4. 2012. EGF a OGF Stirlingových čísel (počty množinových rozkladů se zadaným počtem bloků). Rovnice Z(x) = x.exp(Z(x)) pro EGF stromů na {1, 2, ..., n} s vyznačeným vrcholem. Rekurence pro počty souvislých grafů na {1, 2, ..., n}. LIF (Lagrangeova inverzní formule): když F(f(x)) = x, tak [x^n] g(f(x)) = (1/n)[x^{n-1}] g(x)'.(x/F(x))^n. Příklady: Cayley, Catalan, stromy s omezeními na stupně. Důkaz LIF pomocí rezidua příště.

7. přednáška 16. 4. 2012. Důkaz LIF pomocí rezidua (koeficient u x^{-1}) počítáním v tělese Laurentových řad C((x)). Racionální generující funkce/mocninné řady. Hlavní věta: posloupnost (a_n) má racionální gen. fci A(x) <=> (a_n) splňuje lineární rekurenci s konstantními koeficienty <=> a_n = lineární kombinace exponenciál s polynomiálními koeficienty <=> A(x) má vyjádření pomocí parciálních zlomků, důkaz pomocí vektorových prostorů a dimenze. Příklad: počty vodorovně konvexních polymin s n čtverečky jsou dány rekurencí a_0 = 0, a_1 = 1, a_2 = 2, a_3 = 6, a_4 = 19 a a_{n+3} = 5a_{n+2} - 7a_{n+1} + 4a_n pro n > 1, odvození příště.

8. přednáška 23. 4. 2012. Odvození rekurence pro počet vodorovně konvexních polymin s n čtverečky. Další příklad racionálních generujících funkcí: denumeranty čili počty rozkladů na části z dané (konečné) množiny přir. čísel A. Příklad s A = {1, 2}. Tvrzení: denumerant je kvazipolynom. Tvrzení: asymptotika denumerantů, důkaz příště.

9. přednáška 30. 4. 2012. Důkazy dvou tvrzení o denumerantech. Metoda přechodové matice. Je založena na tomto algebraickém výsledku: Je-li M k krát k matice s položkami v R (komut. okruh s 1), pak pro každé pevné i, j je generující funkce posloupnosti ((M)_{i,j}, (M^2)_{i,j}, (M^3)_{i,j}, ...) racionální, totiž podíl polynomů (-1)^{i+j}det(I - xM | j, i) / det(I - xM) (=položka i, j matice inverzní k matici I - xM). Kombinatorika metody přechodové matice příště.

10. přednáška 7. 5. 2012. Kombinatorika metody přechodové matice. Příklad na přechodovou matici: počet slov nad abecedou {1, 2, 3} bez podslov 11 a 23. Přechodová matice dává hned, že obecně je generující funkce počtů slov (nad konečnou abecedou) vyhýbajících se dané konečné množině zakázaných podslov racionální. Počítání mřížových bodů v mnohostěnech, Ehrhardtova věta: počet mř. bodů v nafouknutích daného mř. (rac.) mnohostěnu je polynom (kazipolynom). Důkaz příště.

12. přednáška 21. 5. 2012. Pár slov o P-rekurzivních posloupnostech, to jest posloupnostech (a_n) splňujících rekurenci p_k(n)a_{n+k} + p_{k-1}(n)a_{n+k-1} + ... + p_0(n)a_n = 0, kde p_i(n) jsou polynomy, což je zobecnění lineárních rekurencí s konstantními koeficienty. Tvrzení: (a_n) je P-rekurzivní <=> její OGF A(x) = a_0 + a_1x + ... je D-konečná (což znamená, že množina derivací A, A', A'', ... má konečnou lineární dimenzi nad tělesem C(x), čili A splňuje lineární diferenciální rovnici s polynomiálními koeficienty). Tvrzení: Každá algebraická moc. řada A(x) = a_0 + a_1x + ... je D-konečná, a tedy má P-rekurzivní posloupnost koeficientů. Příklad se Schroderovými čísly: posloupnost (a_n)_{n>2} = (1, 3, 11, 45, 197, 903, ...), jež počítá konfigurace nekřížících se úhlopříček v (konvexním) trojúhelníku, čtyřúhelníku, pětiúhelníku, ..., splňuje P-rekurenci (n+1)a_{n+2} - (6n-3)a_{n+1} + (n-2)a_n = 0.

Kombinatorické počítání NDMI015