Vyuka - Martin Klazar

Místo a čas přednášky: pondělí 12:20-13:50 v S8 na Malé Straně.
Výuka tohoto předmětu v minulých letech: zde . Literatura: předběžný učební text v angličtině je zde .
Plán letošní přednášky. 1. část. Něco o Catalanových číslech (abychom pokryli státnicové otázky "Kombinatorické počítání, vytvořující funkce, rekurence" zaměření DMA/Diskrétní matematika a algoritmy). 2. část. Enumerativní úlohy počítané kvazipolynomy (např. počet rozměnění n-korunové bankovky na jedno-, dvou- a tříkoruny je qpolynom v n), hodně podle tohoto článku. 3. část. Důkaz toho, že počet cest (selfavoiding walks) v šestiúhelníkové mřížce, s pevným začátkem a délkou n, má asymptotiku (2cos(pi/8))^{n + o(n)}, víceméně podle tohoto článku.

Zkouška. Zkouškové otázky jsou následující. 1. Uveďte (a někdy dokažte) základní vlastnosti Catalanových čísel. 2. Dokažte, že Catalanova čísla c_n nesplňují žádnou lineární rekurenci s konstantními koeficienty. 3. Dokažte Stirlingovu formuli pro faktoriál. 4. Dokažte Pólyovu větu pro d = 2 (skoro všechny procházky v Z^2 opět navštíví svůj začátek). 5. Dokažte Pólyovu větu pro d = 3 (pozitivní frakce procházek v Z^3 nikdy opět nenavštíví svůj začátek). 6. Zformulujte a dokažte identitu pro cesty mezi dvěma hraničními hranami domény X v šestiúhelníkovém grafu H: sum_{e je v hranici X }l(e)y^{r(e)}F_{a, e}(x) = (1 + x.zeta^{-2}y + x.zeta^2y^{-1})sum_{w je v S}l(w)y^{r(w)}x^{|w|} + (zeta^2y^{-4} + zeta^{-2}y^4)sum_{w je v S, C je v C(w)}l(w)y^{r(w)}x^{|w| + |C|}.

přednáška 1, 26. 2. 2018. Co bude na přednášce, viz výše. Definice Catalanových čísel c_n jako počtu zakořeněných rovinných stromů s n vrcholy. Odvození rekurence c_1 = 1, c_n = c_1c_{n-1} + c_2c_{n-2} + ... + c_{n-1}c_1 pro n > 1 a kvadratické rovnice pro jejich generující funkci C(x). Vyřešení rovnice a (pomocí Newtonovy binomické věty (1 + x)^a = sum_{n=0}^{infty}binom(a, n)x^n) odvození vzorce c_n = binom(2n - 2, n - 1)/n. Z něho plyne jednodušší rekurence c_n = ((4n - 6)/n)c_{n-1} a pomocí Stirlingovy formule (n! ~ (2pi.n)^{1/2}(n/e)^n) i asymptotika c_n ~ (1/4pi^{1/2})4^n. Viz kap. 1 v textu .

přednáška 2, 5. 3. 2018. Větička: c_n je liché iff n = 2^m, důkaz. Pozorování: c_n > 2^n pro n > 6. Lemma: pro n > 1 je sum{k=1}^{n-1}(1/k(n-k))^2 < 8/n^2, důkaz. Důsledek: c_n =< 8^{n-1}/n^2 < 8^n pro každé n > 0, důkaz. Bijektivní důkaz vzorce c_n = binom(2n - 2, n - 1)/n pomocí Dykových slov: c_n = |D_n|, kde D_n je množina (2n - 2)-tic z n-1 -1 a n-1 1 s nezápornými počátečními součty, E_n = tato množina bez omezení na počáteční součty a F_n = množina (2n - 2)-tic z n -1 a n-2 1 a konečně E_n bez D_n je v bijekci s F_n. Viz kap. 1 v textu .

přednáška 3, 12. 3. 2018. Odvození rekurence c_n = (4n - 6)c_{n-1}/n derivováním rovnice C^2 - C + x = 0 a získáním difer. rovnic C' = 1/(1 - 2C) a (1 - 4x)C' + 2C - 1 = 0. Poznámka, že tato metoda funguje obecně: každá algebraická GF F(x) splňuje lin. difer. rovnici s polynom. koeficienty a tudíž koeficienty v F(x) splňují lineární rekurenci s polynomiálními koeficienty. Méně známý vzorec: c_n =((-1)^{n+1}/2).binom(1/2, n).4^n. Odtud odhady 4^n/(8n^2) < c_n =< 4^n/(4n). Ovšem velmi podobné odhady se pomocí binom. věty dostanou i z klasického c_n = (1/n)binom(2n - 2, n - 1). Dva důkazy toho, že posloupnost (c_n) není lineárně rekurentní (nesplňuje žádnou fibonacciovskou rekurenci typu c_n = a_1c_{n-1} + a_2c_{n-2} + ... + a_kc_{n-k}, n > k, kde a_i jsou konstantní, třeba komplexní, koeficienty): 1) generující funkce C = C(x) = (1/2)(1 - (1 - 4x)^{1/2}) není racionální, protože ... a 2) do vztahu c_n = a_1c_{n-1} + a_2c_{n-2} + ... + a_kc_{n-k} dosaďte c_{n-i} = (1/(n - i))binom(2n - 2i - 2, n - i - 1) a dostanete nenulový polynom s nekonečně mnoha kořeny, což nejde. Důkaz Stirlingovy formule pro faktoriál (n! ~ (2pi.n)^{1/2}(n/e)^n). Začátek: int_{m - 1/2}^{m + 1/2}log(x)dx = log(m) + O(1/m^2) (m je přirozené číslo).

přednáška 4, 19. 3. 2018. Dokončení důkazu Stirlingovy formule, zejména odvození tvaru konstanty c = (2pi)^{1/2}pomocí rekurence a asymptotiky pro integrály W_n = int_0^{pi/2}(cos x)^n.dx. Další tři integrální reprezentace n!: gamma funkce, Cauchyho formule a vícerozměrná Cauchyho formule. Náhodná procházka v grafu (mřížce) Z^d. Dokážeme Pólyovu větu (z r. 1921): 1) pro d = 1 a 2 se náhodná procházka v grafu Z^d s pravděpodobností 1 vrátí na start, ale 2) v dimenzi d > 2 se na start vrátí s pravděpodobností < 1 (a s pravděpodobností > 0 uteče do nekonečna). Skončili jsme zatím u vztahu B(x) = 1/(1 - C(x)) mezi generujícími funkcemi.

přednáška 6, 9. 4. 2018. Bollobásova--Thomasonova věta (z r. 1986) o existenci prahové funkce pro rostoucí vlastnosti hypergrafů na [n]: je-li Q=(Q^n) posloupnost netriv. rostoucích vlastností podmnožin množiny [n], pak existuje funkce m*(n), že pro m(n)/m*(n) jsoucí do nekonečná (resp. k nule) pravděpodobnost P_{m(n)}(Q^n) (že m(n)-bodovka z [n] má vlastnost Q^n) jde k 1 (resp. k 0). Začátek důkazu. Viz text (Oddíl 3.1).

přednáška 8, 23. 4. 2018. Dokončení důkazu Bollobásovy--Thomasonovy věty, vlastní definice prahové funkce m*(n) pro danou posloupnost Q=(Q^n) netriv. rostoucích vlastností podmnožin množiny [n]. Důkaz Kruskalovy--Katonovy věty, podle článku P. Frankla z r. 1984. Časem to bude sepsané v textu (Oddíl 3.1). Kvazipolynomy. Bellova věta (1943): počet rozkladů čísla n na části z konečné množiny je racionální kvazipolynom v n, dokončení důkazu příště.

přednáška 9, 30. 4. 2018. Důkaz Bellovy věty (podle tohoto preprintu). Důkaz věty Duminila-Copina a Smirnova (počet cest s pevným počátkem a délkou n v šestiúhelníkové mřížce je (2cos(pi/8))^{n + o(n)}). Podle mého preprintu, ale pokusím se to sepsat lépe v mém textu (kapitola 7.2). Úvodní povídání.

Kombinatorické počítání NDMI015, LS 2017/18