Kombinatorické počítání (Combinatorial counting) NDMI015, LS 2013/14

Místo a čas přednášky (place and time of the lecture): Tuesday 10:40 - 12:10, S221 (corridor lecture room of KAM (Dept. of Applied Mathematics), 2nd floor).
Výuka tohoto předmětu v minulých letech (past lectures): zde .
Plán letošní přednášky (plan of the course). Vyložím různé výsledky kombinatorické enumerace pomocí v ní hojně používané techniky generujících funkcí, s důrazem na algebraické manipulace s nimi (The topic is various results of combinatorial enumeration and the method of generating functions, emphasizing algebraic manipulations with them).
Otázky ke zkoušce/Exam questions. 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. Odvoďte Schurovu asymptotiku. 5.  Načrtněte, jak se v O(log n) operacích počítá modulo p n-tý koeficient algebraické mocninné řady ze Z[[x]]. 6. Zformulujte a odvoďte Gesselovo--Viennotovo lemma  o determinantech a cestách. 7. Odvoďte vzorec pro počet koster n-rozměrné nadkrychle Q_n. 

---

přednáška 2, 8. 3. 2016. Nyní již cesky. Dvě formulky pro c_n pomocí binomických koeficientů.  Přesná asymptotika čísel c_n pomocí Stirlingovy formule pro faktoriál. Bijektivní důkaz vzorce c_n = (1/n)binom(2n - 2, n - 1) pomocí Dyckových slov.

---

přednáška 3, 15. 3. 2016. Tři důkazy toho, že Catalanova čísla c_n nesplňují žádnou lineární rekurenci s konstantními koeficienty. První založený na tom, že c_n je liché, právě když n je mocnina 2. Druhý založený na tom, že GF Catalanových čísel C(x) = (1/2)(1 - (1 - 4x)^{1/2}) není racionální. Třetí založený na tom, že Catalanova čísla mají asymptotiku c_n ~ cn^{-3/2}4^n, což není asymptoticky rovno (d_1z_1^n+ ... +d_tz_t^n)n^kg^n + O(n^{k-1}g^n), kde d_i jsou nenulová komplezní čísla, g>0 je reálné, k je celé nezáporné a z_i jsou různá čísla na jednotkové komplexní kružnici (to je vedoucí člen obecné formule pro lin. rekurentní posloupnost).

---

---

přednáška 5, 29. 3. 2016. 1. důkaz Stirlingovy asymptotiky n! = (2pi*n)^{1/2}(n/e)^n(1 + o(1)) pomocí náhrady log(n!) integrálem z log x přes [1/2, n + 1/2]. 2. důkaz pomocí n! = int_0^{+infty} x^n e{-x}dx Laplaceovou metodou, dokončení příště.

---

přednáška 6, 5. 4. 2016. Dokončení druhého důkazu Stirlingovy asymptotiky. Pouze idea 3. důkazu: kruhová metoda, tj. Cauchyova formule dává 1/n! = (1/2pi*i)int_C (e^z/z^{n+1})dz (C je lib. kladně orientovaná kružnice v komplexní rovině se středem v počátku). Co si řekneme příště: jak efektivně (v polylog n operacích) spočítat n-té Catalanovo číslo modulo p, pro každé pevné prvočíslo p. Pro p = 2 to je založeno na relaci pro GF Catalanových čísel C(x) = C(x)^2 + x = C(x^2) + x (poslední rovnost platí pouze modulo 2). Samozřejmě to funguje obecněji pro  posloupnosti koeficientů algebraických mocninných řad - uvidíme příště.

---

---

přednáška 8, 19. 4. 2016. Tak teď už. V preprintu A. Bostana, G. Christola a P. Dumase se dokazuje věta (Theorem 5): Nechť E je v F_p[x, y]_{h, d} (tj. E(x, y) je polynom s koeficienty v p-prvkovém tělese, p je prvočíslo, s x-ovým stupněm h a y-ovým d), přičemž E(0, 0) = 0 a E_y(0, 0) (parc. derivace podle y) není 0, a f v F_p[[x]] (moc. řada s koef. v F_p) je (jednoznačné) řešení rovnice E(x, f(x)) = 0 s f(0) = 0 --- pak lze n-tý koeficient f_n v f(x) = f_1x + f_2x^2 + ... spočítat v O~(d^3*h^2*p^{3d}*log(n)) operacích v tělese F_p, tj. v  počtu operací polynomiálním (vlastně lineárním) ve velikosti (=počtu bitů) čísla n. Zde O~(a) znamená O(a*log^k(a)) pro nějaké pevné k > 0, tj. v odhadu počtu operací zanedbáváme polylogaritmické faktory. Já se budu snažit ukázat jednodušeji pouze kvalitativní výsledek, že ten počet operací je O_{E, p}(log(n)). Začali jsme klíčovým faktem (Lemma 1), že pro každou mocninnou (ba i Laurentovu, viz dále) řadu z(x) v F_p[[x]] máme identitu z(x)^p = z(x^p) (to je základní trik). Dále algebraičnost f(x) implikuje tzv. mahlerovskou rovnici c_0(x)f(x) + c_1(x)f(x^p) + ... + c_k(x)f(x^{p^k}) = 0 (termín podle K. Mahlera), kde c_i(x) jsou polynomy z F_p[x] a k je nejvýše d. Podle jednoho lemmatu (Lemma 12.2.3) v knize J.-P. Allouche a J. Shallita o automatických posloupnostech z minimality k (tj. pro f(x) máme mahlerovskou rovnici minimálního řádu) plyne nenulovost koeficientu c_0(x). Ten bychom potřebovali, aby měl jen jeden monom, a nejlépe, aby byl 1. To se dosáhne přechodem k nové neznámé (moc. řadě) g(x), dané vztahem f(x) = c_0(x)g(x). Tato substituce dává pro g(x) mahlerovskou rovnici  g(x) + c_1(x)c_0(x)^{p - 2}g(x^p) + ... + c_k(x)c_0(x)^{p^k - 2}g(x^{p^k}) = 0. Teď máme ten koeficient rovný 1, ale za (mírnou) cenu, že g(x) není moc. řada, ale řada Laurentova v F_p((x)), tedy má obecně pár členů se zápornými exponenty, g(x) = sum_{n>r}g_nx^n, kde g_n jsou v F_p a r je celé číslo - to je zřejmé ze vztahu g(x) = f(x)/c_0(x). Rozdělme g(x) na zápornou část a na moc. řadu: g(x) = g_{-}(x) + h(x) =  sum_{n<0}g_nx^n +  sum_{n>-1}g_nx^n. Pro h(x) pak dostáváme (nehomogenní) mahlerovskou rovnici (*) h(x) + c_1(x)c_0(x)^{p - 2}h(x^p) + ... + c_k(x)c_0(x)^{p^k - 2}h(x^{p^k}) = b(x), kde b(x) je polynom v F_p[x] daný jako b(x) = -L(x, M)g_{-}(x) (zde L(x, M)g(x) = 0 je původní rovnice pro g(x) a M je Mahlerův operátor x |--> x^p). Laurentův polynom g_{-}(x) se lehce spočte z prvních pár členů v f(x), takže z h(x) hned máme g(x), a od g(x) snadno přejdeme k f(x) (f_n je podle f(x) = c_0(x)g(x) jenom lineární kombinace pár koeficientů g_n). A mahlerovská rovnice (*) pro h(x) už dává efektivní rekurenci pro její koeficienty h_n (= g_n pro nezáporné n), která umožňuje počítat h_n - a tedy i f_n - v O(log(n)) operacích v F_p. To dodělám podrobněji příště, kdy se též pokusím celý postup ilustrovat na Catalanových číslech f(x) = sum_{n>0}f_nx^n = x + x^2+ 2x^3 + 5x^4 + ..., f^2 - f +x = 0, a p = 3 (pro p = 2 též funguje: máme ihned (v F_2[[x]]) f(x) =f(x)^2 + x = f(x^2) + x , tedy f_n = f_{n/2} pro n > 1 a f_1 = 1 (pro necelý index je hodnota koeficientu 0), což hned dává výsledek f_n = 1 pro n = 2^m, f_n = 0 jinak, z 1. přednášky). 

---

---

---

přednáška 11, 10. 5. 2016. Ještě jednou identita det(binom(a_i, b_j)) = počet k-tic neprotínajících se cest z (0, -a_i) do (b_i, -b_i), i=1, 2, ..., k, v mřížovém or. grafu (vrcholy jsou Z^2 a hrany jsou šipky délky 1 nahoru a doprava), kde 0<a_1<...<a_k a 0<b_1<...<b_k jsou celá čísla. Dále odvozování determinantového vzorce pro počet eulerovských tahů v souvislém or. vyváženém grafu. Podle kapitolky v knize Stanley - Enumerative Combinatorics 2.

---

---

přednáška 13, 24. 5. 2016. Dokončení toho důkazu. Poznámka: na přednášce jsem tvrdil, že důkaz lemmatu ve Stanleym (Lemma 5.6.5) není správně, že nasčítáním sloupců matice N(x) do posledního se dostanou -x a ne nuly. Protože se ale správně načítávají sloupce matice N(0), x zmizí a Stanley má pravdu (a já jsem si to pořádně nepřečetl). Odvození vzorce pro počet koster n-rozměrné nadkrychle Q_n (stále podle Stanleyho).

---