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

Místo a čas přednášky: středa 12:20-13:50 v S221 (chodba KAM) 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).

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. Dále bude doplněno.

přednáška 1, 27. 2. 2019. Definice Catalanových čísel c_n jako počtu zakořeněných pěstovaných stromů s n vrcholy. Odvození rekurence c_1 = 1 a c_n = c_1c_{n-1} + c_2c_{n-2} + ... + c_{n-1}c_1 pro n > 1 a z ní odvození parity c_n (Catalanovo číslo c_n je liché iff n je mocnina 2) a exponenciáních odhadů 2^n < c_n <= 8^n/n^2 (dolní pro n > 6). Odvození kvadratické a diferenciální rovnice pro jejich generující funkci C(x). Odvození z diferenciální rovnice rekurence c_n = ((4n - 6)/n)c_{n-1} a z ní pak vzorců c_n = binom(2n - 2, n - 1)/n a c_n = ((-1)^{n+1}/2).binom(1/2, n).4^n. Z posledního plynou daleko lepší odhady 4^n/8n^2 < c_n <= 4^n/4n.

přednáška 2, 6. 3. 2019. Asymptotika C. čísel pomocí Stirlingovy formule pro faktoriál: c_n ~ c.n^{-3/2}.4^n. Odvození vzorce c_n = (1/n)binom(2n-2, n-1) bijektivním důkazem pomocí Dyckových slov. Čtyři důkazy, že posloupnost Catalanových čísel (c_n) není lineárně rekurentní posloupnost (LRP), tedy nesplňuje pro všechna velká n rekurenci tvaru c_n = a_1.c_{n-1}+ a_2.c_{n-2}+ ... + a_k.c_{n-k}. 1. důkaz pomocí funkce ord_2(.) a parity čísel c_n. 2. důkaz pomocí toho, že (1-4x)^{1/2} není racionální mocninná řada. Začátek 3. důkazu založeného na tom, že přesná asymptotika c_n ~ c.n^{-3/2}.4^n není kompatibilní s asymptotikou čísel v LRP.

přednáška 3, 13. 3. 2019. Dokončení 3. důkazu. Konečně asi nejjednodušší 4. důkaz: do c_n = a_1.c_{n-1}+ a_2.c_{n-2}+ ... + a_k.c_{n-k} dosaď explicitní vzorec c_{n-i} = (1/(n-i))binom(2n-2i-2, n-i-1) a ukaž, že tím vznikne nenulový polynom s nekonečně mnoha kořeny. Zmínka o Valtrově větě (bez důkazu): podmíněná pravděpodobnost toho, že n náhodných a nezávislých bodů ve čtverci tvoří konvexní řetězec, pokud již tvoří konvexní n-úhelník, je rovna 1/c_n. Problém: najít kombinatorický důkaz, bez separátního počítání obou pravděpodobností, např. už pro n=4. Narayanova čísla, dokončení příště.

přednáška 4, 20. 3. 2019. Důkaz symetrie N(n, k) = N(n, n-k) pro Narayanova čísla (N(n, k) je počet zp stromů s n vrcholy a k listy) pomoci generující funkce C(x, y). Další úlohy vedoucí na Catalanova čísla: počet triangulací konvexního n-úhelníku, počet permutací čísel 1, 2, ..., n neobsahujících danou permutaci délky 3. Stirlingova formule pro n!. Což je asymptotika, pro přirozené n jdoucí do nekonečna, n! = (1 + o(1))(2pi.n)^{1/2}(n/e)^n. 1. důkaz pomocí vyjádření log(n!) = int_{1/2}^{n+1/2}log(x)dx + c + O(1/n), dokončení příště (zbývá spočítat, že int_{m-1/2}^{m+1/2}log(x)dx = log(m) + O(1/m^2), a zbývá dokončit odvození konstanty (2pi)^{1/2}).

přednáška 5, 27. 3. 2019. Dva resty z minula. 2. důkaz pomocí vyjádření n! = int_0^{+oo}e^{-x}x^n.dx = e^{-n}n^{n+1}int_{-1}^{+oo}(e^{-y}(1+y))^n.dy pomocí Laplaceovy metody.

přednáška 6, 3. 4. 2019. 2. důkaz Laplaceovou metodou ještě jednou a pořádně.

přednáška 7, 10. 4. 2019. Přednáška se nekoná (posluchač na jarní škole).

přednáška 8, 17. 4. 2019. Přednáška odpadla (přednášející u zubařky). tato přednáška bude nahrazena příští týden od 10:40.

přednášky 9+10, 24. 4. 2019. V těchto dvou přednáškách jsem zhruba vyložil, jak dokázat (mou) větu: Každá lineárně rekurentní posloupnost f: N --> Z má PIO formuli [ nějaký algoritmus počítá f(n) z n v čase poly(log(1 + n), log(2 + |f(n)|) ]. Snad sem brzy dám odkaz na příslušný text v ArXivu.

přednáška 11, 1. 5. 2019. Odpadá kvůli státnímu svátku 1. května.

přednáška 12, 8. 5. 2019. Odpadá kvůli státnímu svátku 8. května.

přednáška 13, 15. 5. 2019. Dva výsledky o p_A(n) = počet rozkladů čísla n na části z dané konečné množiny A přirozených čísel. 1. Schurova asymptotika: když NSD(A) = 1, pak pro k = |A| máme p_A(n) =n^{k-1}/(součin čísel v A krát (k-1)!) + O(n^{k-2}), důkaz rozkladem GF na parciální zlomky. 2. p_A(n) je racionální kvazipolynom v n s periodou D, kde D je společný násobek čísel v A = {a_1, ..., a_k}.

přednáška 14, 22. 5. 2019. Důkaz 2. Platí totiž explicitní vzorec p_A(n) = sum_{j v J, že (*)}binom((n - j_1a_1 - ... - j_ka_k)/D + k - 1, k - 1), kde J je množina všech celočíselných k-tic j = (j_1, ..., j_k), že 0 <= j_i <= D/a_i - 1, a podmínka (*) říká, že n je modulo D kongruentní j_1a_1 + ... + j_ka_k. Dostane se vhodným rozšířením zlomku pro GF. Lagrangeova inverzní formule. Formulace a několi aplikací, důkaz jsme nestihli. Viz můj 20 let starý textík .

květen 2019