Vyuka - Martin Klazar

Místo a čas přednášky: Čt 12:20-13:50 v S5.
Výuka tohoto předmětu v minulých letech: zde .
Plán letošní přednášky. Budu se snažit vyložit některé základní výsledky kombinatorické enumerace a v ní hojně používanou techniku generujících funkcí, a to jak z hlediska algebraických manipulací s GF tak i z hlediska nalézání asymptotických odhadů pomocí GF.

Otázky ke zkoušce. (Ohledně termínu zkoušky mne prosím kontaktujte emailem.) 1. Odvoďte vzorec pro Catalanova čísla. 2. Dokažte, že Catalanova čísla nesplňují lin. rekurenci s konstantními koeficienty. 3. Dokažte Stirlingovu asymptotickou formuli pro n!. 4. Odvoďte Schurovu asymptotiku pro počty rozkladů n na části a_1, ... ,a_k. 5. Popište metodu přechodové matice. 6. Dokažte Ehrhartovu větu o počtech mřížových bodů v nafouknutích mnohostěnů.

1. přednáška 27. 2. 2014. Úvod - Catalanova čísla c_n. Definice: c_n je počet (zakořeněných rovinných) stromů s n vrcholy. Odvození vzorce c_n = (1/n)Binom(2n - 2, n - 1) pomocí generující "funkce" C = C(x) = c_1x + c_2x^2 + ... . Nová rekurence c_{n + 1} = ((4n - 2) / (n - 1))c_n a její odvození z kvadr. rovnice C^2 - C + x = 0: C splňuje i difer. rovnici (1 - 4x)C' = 1 - 2C. P-rekurentní a C-rekurentní posloupnosti. (c_n) je P-rekurentní, jak ale dokázat, že není C-rekurentní? První metoda: protože (a_n) je C-rekurentní <=> její GF A(x) je racionální, stačí dokázat, že (form. moc. řada) (1 - 4x)^{1/2} (neboť C = (1/2)(1 - (1 - 4x)^{1/2})) není racionální, tj. není podíl dvou polynomů p(x) / q(x). To se dokáže úplně stejně jako se dokazuje iracionalita čísla 2^{1/2}. Druhá metoda: protože (a_n) je C-rekurentní => (a_n mod m) je vždy eventuálně periodická, stačí nalézt modul m, že (c_n mod m) není eventuálně periodická. A to nastane pro m = 2, protože pomocí výchozí kombinatorické rekurence se lehce dostane, že c_n je liché <=> n = 2^m. Třetí metoda (jen naznačena): asymptotika Catalanových čísel c_n má tvar neslučitelný s asymptotikami C-rekurentních posloupností. Příště: bijektivní důkaz / odvození vzorce c_n = (1/n)Binom(2n - 2, n - 1) pomocí mřížových cest. Většina povídání o Catalanových číslech je převzata odsud (str. 4-8), zbytek je zde .

3. přednáška 13. 3. 2014. Zjemnění Catalanových čísel: Narayanova čísla n(a, b), tj. počet (zakořeněných rovinných) stromů s a vrcholy a b listy. Důkaz symetrie n(a, b) = n(a, a - b) pomocí generujících funkcí. Další struktury počítané Catalanovými čísly (bez důkazů): permutace se zakázanými vzory a výsledek P. Valtra o podmíněné pravděpodobnosti náhodných bodů ve čtverci, že Prob(n náhodných bodů ve čtverci tvoří konvexní řetězec | tyto body již tvoří konvexní n-úhelník) = 1 / c_n = n / binom(2n - 2, n - 1). Racionální generující funkce a C-rekurentní posloupnosti. Příklad s Fibonacciovými čísly. Viz (str. 15-17) a zde .

4. přednáška 20. 3. 2014. Ještě dvě konkrétní enumerativní úlohy vedoucí na racionální generující funkce: (1) počty vodorovně konvexních polymin s n čtverečky (pro n > 4 splňují rekurenci a_n = 5a_{n - 1} - 7a_{n - 2} + 4a_{n - 3}) a (2) Schurova asymptotika pro počty rozkladů čísla n na (nesoudělné) části a_1, ..., a_k (je jich n^{k - 1} / (a_1a_2...a_k.(k - 1)!) + O(n^{k - 2})). Udělali jsme (1), (2) dokončíme příště. Tato dvě odvození jsou popsána zde (str. 33-35) a zde .

5. přednáška 27. 3. 2014. Dokončení Schurovy asymptotiky. Zmínka o Rademacherově domněnce o parciálních zlomcích a jejím vyvrácení. (Vezměme rozklad na parciální zlomky 1 / ((1 - x)(1 - x^2)...(1 - x^n)) = b_n / (1 - x) + ... . Pak pro n --> oo existuje vlastní limita lim b_n; to se domníval, že platí, Rademacher v r. 1973 (a totéž pro další koeficienty rozkladu). Drmota a Gerhold to ale vyvrátili zde.) Obecné algebraické vlastnosti moc. řad: okruh C[[x]]. Charakterizace jednotek. Podílové těleso k C[[x]] jsou Laurentovy řady. Formální konvergence a sčítání nekonečných řad v C[[x]]. Vyjádření 1/f součtem formální geometrické řady. Přednáška je (kromě Schurovy asymptotiky) zapsána zde.

6. přednáška 3. 4. 2014. Věta charakterizující racionální GF: (a_n) pro n > n_0 splňuje C-rekurenci <=> GF A(x) je racionální <=> pro n > n_0 je a_n = sum_{i=1}^r p_i(n).g_i^n (kde p_i(x) jsou nenulové polynomy a g_i různá nenulová komplexní čísla), důkaz. Kvazipolynomy a věta je charakterizující: (a_n) je pro n > n_0 kvazipolynom <=> GF A(x) = p(x) / (1 - x^a)^n, důkaz. Příklady kvazipolynomů. Metoda přechodové matice, jen formulace: je-li a_n = (M^n)_{i,j}, kde M je k krát k (komplexní) matice, pak je GF A(x) = sum_{n >= 0}a_nx^n racionální, a sice A(x) = (-1)^{i+j} det (I - xM | j, i) / det (I - xM ). Důkaz a kombinatorické aplikace příště. Zápis ze 6. přednášky .

7. přednáška 10. 4. 2014. Přednáška odpadla z důvodu prázdnosti množiny posluchačů (posluchaček).

8. přednáška 17. 4. 2014. Přednášeno, co mělo být minule. Důkaz větičky o přechodové matici. Kombinatorická aplikace: vážené počty sledů v digrafech. Příklad (ze Stanleyho EC1): počet slov délky n nad {1, 2, 3} neobsahujících podslova 11 a 23. Dom. cv.: dokažte, že GF sum_n a_nx^n počtů a_n Hamiltonových kružnic v mřížce k krát n je pro každé pevné k racionální. Zápis z 8. přednášky (bude doplněno).

9. přednáška 24. 4 2014. O exponenciálních generujících funkcích: součinová a kompoziční formule a aplikace. Skládání moc. řad, existence kompozičního inverzu. Viz (kapitola VIII).

10. přednáška 15. 5. 2014 (1. a 8. května byly státní svátky). Mřížové body v mnohostěnech. Ehrhartova věta: Je-li P mřížový mnohostěn v R^d, pak f_P(n) := #(Z^d průnik nP) je racionální polynom v n pro každé n = 0, 1, 2, ... , důkaz.

Kombinatorické počítání NDMI015, LS 2013/14