Diskrétní matematika - 12. týden Příklady řešení rekurencí Dnosti Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2020 Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo oooo Obsah přednášky Q Binární stromy a Catalanova čísla Q Caleyho vztah pro počet stromů Q Rekurzivně propojené posloupnosti Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo oooo Doporučené zdroje • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. • Donald E. Knuth, The Art Of Computer Programming. • Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994. S využitím standardních vytvořujících funkcí určíme formuli pro počet bn tzv. pěstovaných binárních stromů na n vrcholech, které je pro naše účely možné definovat jako kořen s uspořádanou dvojicí [levý binární podstrom, pravý binární podstrom]. Prozkoumáním případů pro malá n vidíme, že Dělením problému na levý a pravý strom dostaneme pro n > 1 Vidíme, že jde vlastně o konvoluci posloupností. Vztah upravíme, aby platil pro všechna n £ A/q: bo = l.£>i = 1, £>2 = 2, £>3 = 5. b bobn-i + bibn-2 H-----h bn-ib0. 0 = 0]xn = n n,k n,k =E^x" ^^-ix11-^ +1 = = bkxk(xB(x)) + 1 = B(x) • xB(x) + 1. k Pravá strana rekurence na prvním řádku je koeficientem u xn v součinu B(x) • B(x), tj. členem u xn v xB(x)2. Je tedy x6(x)2 vytvořující po tutéž posloupnost jako 6(x) s výjimkou prvního členu u x°. V kroku 3 řešíme kvadratickou rovnici 6(x) = xB(x) + 1 pro Znaménko + ale nepřichází v úvahu, protože pak by pro x —>> 0+ 6(x) měla limitu oo, zatímco vytvořující funkce pro naši posloupnost musí mít v 0 hodnotu bo = 1. Naopak pro znaménko — to tak dostaneme. Pro vytvořující funkci 6(x) tedy platí B(x): B(x) 1 ± VI -4x 2x B(x) 1 - VI -4x 2^č Zbývá už pouze krok 4, tedy rozvinout B(x) do mocninné řady. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti oooto oooooooo oooo Rozvoj získáme pomocí zobecněné binomické věty d - 4*>1/2 = E T <-4*>' =1+E i U I) (-4x) k>0 V 7 /c>l v a po vydělení 1 — Vl 4x výrazem 2x dostaneme /c>l V 7 ^ /-l/2\ (-4x)" = y, /2n\ _x^_ Dokázali jsme, že počet binárních pěstovaných stromů na n Tato významná posloupnost se nazývá posloupnost Catalanových čísel. Kromě toho, že Catalanova čísla vyjadřují počet binárních pěstovaných stromů, vystupují rovněž jako: • počet monotónních cest z [0,0] do [r?, n] podél stran jednotkových čtverců, které nepřekročí diagonálu o počet slov délky 2n obsahujících n znaků X a Y takových, že žádný prefix slova neobsahuje více Y než X 9 podobně takové fronty u pokladny (n lidí má 5korunu a m lOkorunu, lístek stojí 5 Kč.), že nezásobená pokladna může vždy vrátit • počet korektně ozávorkovaných výrazů složených z levých a pravých závorek • počet různých triangulací konvexního (r? + 2)-úhelníku. vrcholech je roven Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciální varianty1. Jméno vychází z toho, že exponenciální funkce ex je (exponenciální) vytvořující funkcí pro základní posloupnost (1,1,1,1,...). V zápětí v důkazu Cayleyho věty uvidíme, že je použití exponenciálních vytvořujících funkcí výhodné. Používají se i další typy vytvořujících funkcí (např. v teorii čísel se používají Dirichletovy vytvořující funkce, kde roli faktoru x11 hraje n~x), ale těmi se zde zabývat nebudeme. n>0 Opět standardním operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami (coby exponenciálními vytvořujícími funkcemi): • Sčítání (a; + b\) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení {a • a;) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a • a(x) příslušné vytvořující funkce. • Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, a2, a3,...), tj. derivování odpovídá posuvu doleva o jedno místo . • Integrování JQX a(t) dt vytvořuje posloupnost (0, ao, ai, a2, a3,...), tj. odpovídá posuvu doprava o jedno místo. Součin vytvořujících funkcí vytvořuje posloupnost se členy Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oo«ooooo oooo Cayleyho formule Cayleyho formule je vztah z kombinatorické teorie grafů, který udává, že počet stromů (tj. grafů, v nichž jsou libovolné dva vrcholy spojené právě jednou cestou) na n vrcholech je tv(Kn) = nn~2. Dokážeme tento výsledek pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = tv(Kn). Lze snadno spočítat, že t\ — t2 = 1, h — 3, U — 16. (Např. víme, že v případě stromů na 4 vrcholech musíme z (3) = 20 potenciálních grafů s právě 3 hranami odebrat ty možnosti, kde tyto hrany tvoří trojúhelník. Těch je ale právě (3) = 4). Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti OOOOO 000*0000 oooo Rekurentní vztah získáme tak, že zafixujeme jeden vrchol v a možné případy rozdělíme podle počtu komponent v grafu, který dostaneme z koster Kn tak, že odstraníme vrchol v a hrany s ním incidentní. Pak pro n > 1 El v-^ (r?-l)! ^ Z. kí\...kmikl"'km'tkí"'tk» m>0 /ciH-----\-km=n—l Např. pro n = 4 máme £4 = 3ŕ3 + 6ŕiŕ2 + . Ošklivě vypadající rekurenci zjednodušíme substitucí un = r?rn (uvědomte si přitom, že un udává počet tzv. kořenových stromů). Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooo«ooo oooo Dostáváme pro n > 1 _ Uk±_ ukm n\~ ^ m\ ^ ki\"' km\ m>0 /ciH-----\-km=n—l a je vidět, že vnitřní sumu dostaneme jako koeficient u xn_1 v m-té mocnině řady U(x) — ^ un^\- Proto je £ = [x-'] e ^ om-. a tedy (7(x) =xeeM. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti OOOOO OOOOO0OO oooo Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice _1 Zobecněnou exponenciální mocninnou řadou £t{x) nazýváme řadu €t{x) - = S>+i)*-i£. k>0 Snadno je vidět, že £q = ex, dále označujeme £{x) = £\{x). Fakt: In Et(x) = x • £t(x), tj. spec. £{x) = exS^ . Srovnáním tohoto vztahu s výše uvedeným U{x) — xe^x' vidíme, že U{x) — x£[x). Proto tn = ^ = ^ixn]U(x) = („- l)![x""VW = n Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti OOOOO OOOOOO0O oooo Alternativní závěr výpočtu Pokud vám přišel závěr výpočtu příliš umělý, zkusme to ještě jednou, s využitím tzv. Lagrangeovy inverzní formule: Pokud vytvořující funkce g(x) — X)n>i SnXn splňuje vztah x = f(g{x)), kde f(0) = 0, ř"'(0) ^ 0, pak Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo ooooooo* oooo Alternativní závěr výpočtu Řešíme U(x) = xeu(x\ tj. U(x) splňuje vztah x = f(U(x)), kde f(u) = -17. Odtud z Lagrangeovy formule [xn]U(x) = -[u"-1] f-^- n 1 1 nn_1 = -n[u ]e =n(^l)í A7-1 n\ Protože = [xn]U(x), dostáváme odtud Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo •ooo Někdy dokážeme snadno vyjádřit hledaný počet jen pomocí více vzájemně provázaných posloupností. Příklad Kolika způsoby můžeme pokrýt (nerozlíšenými) kostkami domina obdélník 3 x n? Řešení Snadno zjistíme, že c\ — 0, c2 = 3, C3 = 0, dále klademe co = 1 (nejde jen o konvenci, má to svou logiku). Najdeme rekurzívní vztah - diskusí chování „na kraji" zjistíme, že cn = 2r„_i + cn_2, rn = cn_i + rn_2, r0 = 0, r\ = 1, kde rn je počet pokrytí obdélníku 3 x n, ze kterého jsme odstranili levý horní roh. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo o«oo Řešení (pokr.) Hodnoty cn a rn pro několik malých n jsou: n 0 1 2 3 4 5 6 7 1 0 3 0 11 0 41 0 rn 0 1 0 4 0 15 0 56 Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo oo»o Řešení (pokr.) • Krok 1: c„ = 2r„_i + c„_2 + [n = 0], rn = cn_x + r„_2. • Krok 2: C(x) = 2xR(x) + x2C(x) + 1, R(x) • Krok 3: 1 -x2 C(x) =-=-j, R(x) y J l-4x2+x4' y J » Krok 4: Vidíme, že obě funkce jsou funkcemi x2, ušetříme si práci tím, že uvážíme funkci D(z) = 1/(1 — 4z + z ), pak totiž C(x) = (1 - x2)D(x2), tj. [x2"]C(x) = [x2"](l - x2)D(x2) = [x"](l - x)D(x), a tedy Q2n = dn — dn-\. = xC(x)+x2R(x). X = 1 - 4x2 + x4 ' Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo ooo« Řešení (závěr) Kořeny 1 — 4x + x2 jsou 2 + V3 a 2 — V3 a již standardním způsobem obdržíme = (2 + VŠ)n (2 - y/3)n C2n 3 - y/3 3 + VŠ Podobně jako u Fibonacciho posloupnosti je druhý sčítanec pro velká n zanedbatelný a pro všechna n leží mezi 0 a 1, proto C2n = (2 + VŠ)n 3-VŠ Např. c20 = 413403.