Literatura Řešení rekurencí Řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo oooooooooooooooooo Diskrétní matematika B - 13. týden Kombinatorické výpočty - řešení rekurencí Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2014 Literatura Řešení rekurencí Řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo oooooooooooooooooo Obsah přednášky Řešení rekurencí Řešení rekurencí • Fibonacciho čísla • Catalanova čísla Exponenciální vytvořující funkce Řešení rekurencí Řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo oooooooooooooooooo Doporučené zdroje • Jan Slovák, Martin Panák, Michal Bulant, Matematika drsně a svižně, MU Brno, 2013, 774 s. (též jako e-text). • Předmětové záložky v IS MU • Donald E. Knuth, The Art Of Computer Programming. • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, MIT Press, 2009. • Robert Sedgewick, Philippe Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 1995. • Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994. • H. S. Wilf, Generatingfunctionology, Academic Press, 1994, (rovněž http://www.math.upenn.edu/~wilf/DownldGF.html) juBAO>jedo oooooooooooooooooo ooooooooooooooo Literatura Řešení rekur encí Řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo oooooooooooooooooo Poznámka (Nejen) pro manipulace se sumami používají autoři Concrete mathematics velmi vhodné označení [logický predikát] -výraz je roven 1 v případě splnění predikátu, jinak 0. Např. [n = 1], [2\n] a pod. Pro vyjádření koeficientu u x" ve vytvořující funkci F(x) se pak často používá zápis [x"]F(x). Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí. Tím je míněno vyjádření členu an jako funkci n. Často se s pomocí řad podaří vyřešit na první pohled velmi složité rekurence. Obvyklý (takřka mechanický) postup pro řešení rekurencí se skládá ze 4 kroků: O Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n G No (předpokládajíce a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme x" a sečteme přes všechna n G No- Na jedné straně tak dostaneme J2n anx", coz Je vytvořující funkce A(x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). O Zjištěná rovnice se vyřeší vzhledem k A(x). Q Výsledné A(x) se rozvine do mocninné řady, přičemž koeficient u x" udává an, tj. an = [xn]A(x) . Literatura Řešení rekurem Řešení rekurencí ooooooooooooooo Exponenciální vytvořující funkce oooooooooooooooooo ' Příklad ^ Řešte rekurenci a0 = 0, ai = 1 3n = 5an_i — 6a„_2 Řešení • Krok 1: a„ = 5a„_i - 6an_2 + [n = 1]. • Krok 2: i4(x) = 5x^(x) - 6x2^(x) + x. • Krok 3: x 1 1 A(X' ~ 1 -5x + 6x2 ~ 1 -3x l-2x' • Krok 4: an = 3"-2". Řešení rekurencí Řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo oooooooooooooooooo Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurenci n nCn = n(n - 1) + 2 C0 = d = 0 pomocí uvedeného postupu. • E„>o "O" = E„>0 n(n - l)x" + 2 E„>o(£Li Q-iK • xC'(x) = píp + 2^ • Vyřešíme tuto lineární diferenciální rovnici prvního řádu f- — dx (vynásobíme integračním faktorem eJ x = (1 — x)2, odkud [(1 - x)2C(x)]' = I2^), a tedy C(x) = (rľ^(lnrb-X)' odkud konečně Cn = 2(n + l)(H„+i — 1) — 2n. Pripomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fo = 0, Fi = 1, Fn+2 = Fn+i + Fn. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice (podrobně viz http://is.muni.cz/th/41281/prif_d/disertace.pdf). Našim cílem bude (opět) najít formuli pro výpočet n-tého členu posloupnosti. Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Pak zřejmě F(x) — xF(x) — x2F(x) = x, a tedy Našim cílem je tedy odvodit vztah pro n-tý člen posloupnosti odpovídající vytvořující funkci F(x) = 1_*_x2■ Využijeme k tomu rozklad na parciální zlomky a dostaneme x _ A B 1 — X — X2 X — Xi X — X2 ' kde xi,X2 jsou kořeny polynomu 1 — x — x2 a A, B vhodné konstanty odvozené z počátečních podmínek. Po substituci Ai = l/xi,A2 = l/x2 dostáváme vztah x a b 1 — x — x2 1 — Aix 1 — A2X' odkud snadno pomocí znalostí o vytvořujících funkcích Fn = a ■ XI + b ■ Ag. S využitím počátečních podmínek dostávame 1 Vš i +Vš VšN Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Uvážíme-li navíc, že (1 - VŠ)/2 « -0.618, vid íme, že pro všechna přirozená čísla lze Fn snadno spočítat zaokrouhlením čísla _i^iiA)n Navíc je vidět, že lim,,^ Fn/Fn+1 = 1/Ai «0.618, což je poměr známý jako zlatý řez - objevuje se již od antiky v architektuře, výtvarném umění i hudbě. Analogický postup je možné použít při řešení obecných lineárních diferenčních rovnic /c-tého stupně s konstatními koeficienty. Má-li charakteristická rovnice jednoduché kořeny, je situace jednodušší-viz dříve. Jak jsme již viděli na příkladu Fibonacciho posloupnosti, v kroku 4 často s výhodou využijeme rozkladu na parciální zlomky. Ten jsme již viděli dříve (často se používá při integraci racionálních lomených funkcí), proto připomeneme jen stručně: • Předpokládáme, že P(x)/Q(x) je podíl polynomů, kde st P < st Q (jinak vydělíme se zbytkem) a P(x), Q(x) nemají společné kořeny. • Polynom Q(x) rozložíme na kořenové činitele. • Jsou-li všechny kořeny a\,..., ai jednoduché, pak P(x) A, | | Ae Q(X) x — a\ x — ot£ • Má-li kořen a násobnost k, pak jsou příslušné parciální zlomky tvaru Ai A2 | Ak (x — a) (x — a)2 (x — a)k • V případě dvojice komplexně sdružených kořenů nahrazujeme sčítanec A/(x — a) sčítancem (Ax + B)/(x2 + px + q) včetně příslušných mocnin jmenovatele. • Neznámé dopočítáme bud' roznásobením a porovnáním koeficientů u jednotlivých mocnin x nebo dosazením jednotlivých kořenů. • Výrazy A/(x — a)k převedeme na výrazy tvaru 6/(1 — (3x)k vydělením čitatele i jmenovatele výrazem {—a)k. Tento výraz již umíme rozvinout do mocninné řady. S využitím vytvořujících funkcí určíme formuli pro počet bn 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 b0 = l,b! = = 2,b3 = 5. Snadno nahlédneme, že pro n > 1 vyhovuje bn rekurentní formuli bn = b0bn-! + bibn-2 H-----h ón-i^o- Vidíme, že jde vlastně o konvoluci posloupností. Vztah upravíme, aby platil pro všechna n G Nq\ bn= bkbn-k-i + [n = 0]. 0 = 0]x" = n n,k n,k = bkxk(xB(x)) + 1 = B (x) ■ xB(x) + 1. Pozorný čtenář si jistě povšiml, že ve výše uvedeném výpočtu jsme nahradili konvoluci bn = £>o^n-i + b\bn-2 + • • • + ^n-i^o vztahem bn = b0bn-i H-----h ^n-i^o + bnb-i + bn+1b_2 H----■ Díky naší konvenci to ale není problém a velmi to usnadňuje práci se sumami (s nekonečnými součty se zde pracuje podstatně snadněji než s konečnými, kdy musíme neustále hlídat meze). Literatura Řešení rekurem Řešení rekurencí ooooooo»ooooooo Exponenciální vytvořující funkce oooooooooooooooooo V kroku 3 řešíme kvadratickou rovnici B(x) = xB(x)2 + 1 pro Znaménko + ale nepřichází v úvahu, protože pak by pro x —> 0+ B(x) měla limitu oo, zatímco vytvořující funkce pro naši posloupnost musí mít v 0 hodnotu bo = 1. Zbývá už pouze krok 4, tedy rozvinout B(x) do mocninné řady. Rozvoj získáme pomocí zobecněné binomické věty B(x): B(x) 1 ± VI - 4x 2x a po vydělení 1 — \/l — 4x výrazem 2x dostaneme fr>l V 7 Dokázali jsme, že počet binárních pěstovaných stromu na n vrcholech je roven bn = ^j(2n") _ 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 slov délky 2n obsahujících n znaků X a Y takových, že žádný prefix slova neobsahuje více Y než X • podobně takové fronty u pokladny (5koruny a lOkoruny), ž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 monotónních cest z [0,0] do [n, n] podél stran jednotkových čtverců, které nepřekročí diagonálu • počet různých triangulací konvexního (n + 2)-úhelníku. Príklad Vyřešte rekurenci 3q = a1 = 1 3n = 3n-l+2an_2 + (-l)" Řešení Tato rekurence je opět jiného typu než dosud studované. Jako vždy neuškodí vypsání prvních několika členů posloupnosti (teď ale ani moc nepomůže, snad jen pro kontrolu správnosti výsledku).3 aNarozdíl od tvrzení v Concrete mathematics je již možné tuto posloupnost nalézt v The On-Line Encyclopedia of Integer Sequences. < Literatura Řešení rekur encí Řeše ní rekurencí Exponenciální vytvořující funkce 000 0000000*0000 oooooooooooooooooo Řešení (pokr.) • Krok 1: an = 3n_i+2an_2 + (-l)>>0] + [n = l]. « Krok 2: ^(x) = xA{x) + 2x2A(x) + + x. « Krok 3: (l-2x)(l+x)2- • Krok 4: an = Í2"+(J»+ »(-1)". Řei OS 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, cj = 0, dále klademe cq = 1 (nejde jen o konvenci, má to svou logiku). Najdeme rekurzívní vztah - diskusí chování „na kraji" zjistíme, že cn = 2r„_i + c„_2, rn = c„_i + r„_2, = 0, a = 1, kde rn je počet pokrytí obdélníku 3 x n, ze kterého jsme odstranili levý horní roh. Literatura Řešení rekur encí Řeše ní rekurencí Exponenciální vytvořující funkce 000 ooooooooo«oo oooooooooooooooooo Řešení (pokr.) Hodnoty cn a rn pro několik malých n jsou: n 0 1 2 3 4 5 6 7 Cn 1 0 3 0 11 0 41 0 rn 0 1 0 4 0 15 0 56 Literatura Řešení rekurencí Řeše ní rekurencí Exponenciální vytvořující funkce 000 oooooooooo»o oooooooooooooooooo Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = c„_i + r„_2- • Krok 2: C(x) = 2xR{x) +x2C(x) + 1, /?(x) =xC(x) + x2/?(x). • Krok 3: C(X) = l-\7+x^ R{X) = l-4xX2+x^ • 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 + z2), pak totiž C(x) = (1 -x2)D(x2), tj. [x2n]C(x) = [x2n](l -x2)D(x2) = [x"](l -x)D(x), a tedy C2n = dn — dn-i. Literatura Řešení rekur encí Řeše ní rekurencí Exponenciální vytvořující funkce 000 00000000000» oooooooooooooooooo Řešení (závěr) Kořeny 1 — 4x + x2 jsou 2 + y/Ž a 2 — VŠ a již standardním způsobem obdržíme = (2 + y/3)n (2 - Všy C2n~ 3-VŠ 3 + VŠ Podobně jako u Fibonacciho posloupnosti je druhý sčítanec pro velká n zanedbatelný a pro všechna n leží mezi O a 1, proto C2n (2 + VŠ)n 3-y/3 Např. c20 = 413403. Někdy mívá vytvořující funkce posloupnosti (a„) komplikované vlastnosti, přičemž posloupnost (an/n\) má vytvořující funkci daleko jednodušší. V takových případech raději pracujeme s tzv. exponenciálními vytvořujícími funkcemi n>0 Jméno vychází z toho, že vytvořující funkcí základní posloupnosti (1,1,1,1,...) je e\ e* ^4 (1,1,1,...), — ^4(1,1,2,6,24,...) Zdůrazněme, že exponenciální vytvořující funkce se od obyčejných liší i standardními operacemi. • Vynásobením x získáme funkci posloupnosti (na„_i). • Derivací získáme funkci odpovídající posunutí doleva. • Integrací získáme funkci odpovídající posunutí doprava. • Součinem dvou funkcí F(x) a G(x) získáme funkci H(x), která odpovídá posloupnosti hn = J2k {1)^kSn-k< tzv. binomické konvoluci fn a gn. Literatura Řešení rekur encí Řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo oo»ooooooooooooooo Příklad Uvažme permutace na n-prvkové množině a označme p„ = n\ jejich počet. Pak příslušná e.v.f je n>0 n\ 1 -x Příklad Nyní uvažme cykly délky n na n-prvkové množině a označme cn jejich počet. Snadno se ukáže, že cn = (n — 1)!. Pak příslušná e.v.f je y7n-l)!^ = ln-í-. ^v ' n\ 1 - x n>0 Řešení rekurencí Řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo ooo»oooooooooooooo Kombinatorické konstrukce Jsou-li A, B třídy kombinatorických objektů s e.v.f A(x), B(x), pak níže uvedeným konstrukcím odpovídají příslušné e.v.f: disjunktní sjednocení................................^(x) + B(x) uspořádané dvojice objektů z A a B..................^(x) • B(x) posloupnost k objektů z A...............................(A(x))k posloupnost objektů z A..................................^ ^ ^ množina k objektů z A................................... množina objektů z A.......................................eAW cyklus k objektů z A..................................... (^W) cyklus objektů z A.....................................In ^ ^ Literatura Řešení rekurem Řešení rekurencí ooooooooooooooo Exponenciální vytvořující funkce oooo»ooooooooooooo Příklad Určete počet permutací n prvků s využitím faktu, že každá permutace je množina cyklů. E.V.f pro počet permutací je tedy podle předchozího přehledu e 1~x 1-x' jak jsme již jednou odvodili, odkud tedy pn = n\[x"]j^ = n\ Literatura Řešení rekur encí Řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo ooooo»oooooooooooo Příklad Určete počet permutací na n-prvkové množině, které nemají pevný bod. Řešení Analogicky jako výše jde o množinu cyklů (v tomto případě) délky větší než 1, proto je je příslušná e.v.f rovna D(x) = e^">ix"/" = elni^-x = K ' 1-x Odtud d„ = n\[xn]Ď(x) = n\ ELo ^ží > což lze Pro velká " aproximovat dn ^. Jinými slovy, pro velká n náhodná permutace n-prvkové množiny neobsahuje pevný bod s pravděpodobností cca i Literatura Řešení rekurem Řešení rekurencí ooooooooooooooo Exponenciální vytvořující funkce oooooo»ooooooooooo Příklad Určete pravděpodobnost, že náhodná permutace 10 prvků nebude mít žádný cyklus delší než 5. Řešení Podobně jako dříve, odvodíme, že jde o to, určit [x10]ex+x2/2+x3/3+xV4+x5/5 TentQ vyraz |zg díky vnodné vo|bě konstant upravit na jednodušší v6 v7 v10 což je ale rovno [x10](l+x + x2 + -- + *10)(i-1ir-^ 10 " °'354- „10 —) 10 ; Řešení rekurencí Řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo ooooooo»oooooooooo „Praktická" aplikace Deset odsouzených na smrt dostalo poslední šanci. Identifikace každého z nich byla umístěna do jedné z deseti přihrádek (do každé po jedné). Odsouzenci přistupují po jednom k přihrádkám a mohou otevřít pět z nich. Pokud každý z odsouzených nalezne svoji identifikaci, všichni dostanou milost jinak budou všichni popraveni. Navrhněte strategii, při níž budou mít co největší šanci na úspěch. Literatura Řešení rekur encí Řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo oooooooo»ooooooooo Příklad O Určete počet cyklů délky 1, které se objeví v rozkladu náhodné n-prvkové permutace na součin nezávislých cyklů Q Určete počet inverzí v náhodné n-prvkové permutaci. Příklad Řešte rekurenci danou vztahem k>0 (n\ak UM3o = 1- Literatura Řešení rekurem Řešení rekurencí ooooooooooooooo Exponenciální vytvořující funkce ooooooooo#oooooooo Příklad Řešte rekurenci danou vztahy go = 0, g\ = 1 a předpisem gn = -2ngn-í + )gkgn-k- k>0 Vzhledem k rekurentnímu vztahu, který obsahuje binomickou konvoluci posloupností, se zdá vhodné využít exponenciálních vytvořujících funkcí. Označme G(x) příslušnou exponenciální mocninnou řadu. Budeme postupovat v obvyklých čtyřech krocích. o Krok 1: gn = -2ng„_i + Zk>o (k)Skgn-k + [" = !]■ • Krok 2: G(x) = -2xG(x) + G{xf+x. Řešení rekurencí Řešení rekurencí ooooooooooooooo Exponenciální vytvořující funkce oooooooooo^ooooooo Řešení (pokr.) • Krok 3: Řešením kvadratické rovnice dostaneme G(x) = 1/2(1 + 2x ± Vl +4x2). Dosazením x = 0 vidíme, že odpovídá znaménko —, proto je řešením funkce , 1 + 2x - VI + 4x2 • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím dříve dokázaného vztahu a protože 1/2\ = J_ f-Vs /c ) 2k \k - 1 postupně dostaneme Literatura Řešení rekurencí Řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo ooooooooooo»oooooo Řešení (dokončení) y/l + 4x2 = 1 + V \ ■ ( k>í (ľ:ľ) Odtud, protože n>0 1 + 2x - Vl + 4x2 2 máme g2k+i = 0 a (2/c)! = (-l)^(2/c)!-Q_1, kde C„ je n-té Catalanovo číslo. Řešení rekurencí Řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo oooooooooooo»ooooo 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 K,(Kn) = nn~2. Dokážeme tento výsledek pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = n(Kn). Lze snadno spočítat, že t\ = t2 = 1, Í3 = 3, Í4 = 16. (Např. víme, že v případě stromů na 4 vrcholech musíme z (^) = 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ě (^) = 4). Literatura Řešení rekurem Řešení rekurencí ooooooooooooooo Exponenciální vytvořující funkce ooooooooooooo»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 m>0 ki~\-----Vkm=n-1 Např. pro n = 4 máme £4 = 3ř3 + 6ŕiŕ2 + tf. Literatura Řešení rekurencí Řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo oooooooooooooosooo Ošklivě vypadající rekurenci zjednodušíme substitucí un = ntn (uvědomte si přitom, že un udává počet tzv. kořenových stromů). Dostáváme pro n > 1 a je vidět, že vnitřní sumu dostaneme jako koeficient u x"-1 v m-té mocnině řady U(x) = un^\ - Proto je m>0 a tedy U{x) =xetyW Literatura Řešení rekurem Řešení rekurencí ooooooooooooooo Exponenciální vytvořující funkce ooooooooooooooo»oo Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice Zobecněnou exponenciální mocninnou řadou £t{x) nazýváme řadu k>0 Snadno je vidět, že £q = ex, dále označujeme £(x) = £\{x). Fakt: In £t(x) = x ■ £t(x), tj. spec. £{x) = exřM . Srovnáním tohoto vztahu s výše uvedeným U(x) = xeyM vidíme, že U{x)=x£(x). Proto tn = — = -[xn]U{x) = {n- l)!^"-1]^*) = n"~2- Literatura Řešení rekurencí Řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo oooooooooooooooo»o 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) = J2n>i SnXn splňuje vztah kde f(0) = 0, f'(0) + 0, pak gn=n[u Řešení rekurencí Řešení rekurencí Exponenciální vytvořující funkce OOOOOOOOOOOOOOO 00000000000000000» Alternativní závěr výpočtu Řešíme U{x) =xeuW, tj. U{x) splňuje vztah x = f {U {x)), kde f(u) = -77. Odtud z Lagrangeovy formule MBM = -[Ov/e. -n-1 -n-1 n(n-l)\ Protože ^ = [xn]U(x), dostávame odtud