Diskrétní matematika B - 11. týden Kombinatorické výpočty ;urencí >oooooo Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2013 Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo oooooooooooo ooooooooooooo 0 Motivace • Opakování kombinatorických vztahů 0 Vytvoř uj íc í fu n kce Q (Formální) mocninné řady • Přehled mocninných řad • Operace s vytvořujícími funkcemi 0 Řešení rekurencí • Fibonacciho čísla • Catalanova čísla • Martin Panák, Jan Slovák, Drsná matematika, průběžně připravovaný 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) Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí •oooo oooo oooooooooooo ooooooooooooo Úvodní motivace Naším cílem nyní bude vybudovat základní prostředky pro řešení úloh obdobných těmto: odvození Cayleyho formule Určete počet stromů na daných n vrcholech. Analýza algoritmů Určete očekávaný počet porovnání během algoritmu Quicksort. Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí o»ooo oooo oooooooooooo ooooooooooooo Quicksort - analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): i f L = [ ]: return [] return qsort([x for x in L[l:] if x=L[0]]) O Počet porovnání při rozdělení (divide): n — 1. O (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je k-tý největší, je ^. O Velikost tříděných polí ve fázi conquer: k — 1 a n — k. Pro střední hodnotu počtu porovnání tak dostáváme rekurentní vzta h: " 1 Cn = n-1 + ^2- (Q_i + Cn_k). k=l " 1 Cn = n - l + + Cn-k), C0 = 0. n k=l 2 n Cn = n — 1 H— >^ Ck-i symetrie obou sum n t—' k=l n nCn = n(n — 1) + 2 Q_i vynásob n n-1 l)Cn-i = (n — l)(n — 2) + 2 Q_i tentýž výraz pro C„_ nCn = (n + l)Cn_i + 2(n — 1) odečteno a upraveno nCn = (n + l)Cn-1 + 2(n-l) Přestože jsme již rekurenci výrazně zjednodušili, takže je možné jednoduše iterativně hodnoty Cn dopočítat, je často žádoucí tyto hodnoty konkrétně (nebo alespoň přibližně) vyjádřit explicitně jako funkci n. Nejprve si pomůžeme drobným trikem, kdy vydělíme obě strany výrazem n(n + 1) : Cn = C„_! | 2{n - 1) n + 1 n n(n + l) Nyní tento vztah „rozbalíme" (telescope, příp. si pomůžeme substitucí Bn = Cn/n + 1): Cn = 2(n-l) 2(n-2) 2_1 Q n + 1 + (n-l)n 2-3 2 Vytvořující funkce oooo oooooooooooo í rekurer Odkud C n-1 "±ÍT = 2E n + 1 ^(/c + l)(/c + 2)-Výraz sečteme např. pomocí rozkladu na parciální zlomky (k+l)(k+2) odkud ^2 ~~ 'F^T a dostaneme n + 1 2 Hn4 2 + n + 1 Cn = 2(n + l)Hn+i-4(n + l) + 2 (H? = Ylk=i \ Je součet prvních n členů harmonické řady). Přitom je možné odhadnout Hn ~ J" ^ + 7, odkud C„ ~ 2(n + l)(ln(n + 1) + 7 - 2) + 2. Vytvořující funkce oooo oooooooooooo Stručně nyní zopakujme některé důležité kombinatorické pojmy a vztahy: Geometrická řada 2 k=0 x- 1 n / Binomická věta (x + y)n = ( xkyn-k Horní binomická řada Vandermondova konvoluce ' ~'~ n + 1 m + l E 7 r" k=Q V 7 V Vytvořující funkce (Formální) mocninné řady Řešení rekurencí •ooo oooooooooooo ooooooooooooo Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují. Příklad Máme v peněžence 4 korunové mince, 5 dvoukorunových a 3 pětikorunové. Z automatu, který nevrací, chceme minerálku za 22 Kč. Kolika způsoby to umíme, aniž bychom ztratili přeplatek? Hledáme zjevně čísla /', j a k taková, že /+_/' + k = 22 a zároveň / G {0,1, 2, 3,4}, j G {0,2,4, 6, 8,10}, k e {0,5,10,15}. Uvažme součin polynomů (třeba nad reálnými čísly) (X0+Xl+X2+X3+X4)(x0+X2+X4+X6+X8+X10)(x0+X5+X10+Xl5)- Mělo by být zřejmé, že hledaný počet řešení je díky (Cauchyovskému) způsobu násobení polynomů právě koeficient u x22 ve výsledném polynomu. Skutečně tak dostáváme čtyři možnosti 3*5 + 3*2 + 1*1, 3*5 + 2*2 + 3*1, 2*5 + 5*2 + 2*1 a 2*5 + 4*2 + 4*1. Literatura Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo o»oo oooooooooooo ooooooooooooo Předchozí příklad asi vypadal spíš jako složitý zápis jednoduchých „backtrackingových úvah". Následující příklad ukazuje, že tento postup lze ale s výhodou zobecnit. Nechť /, J jsou konečné množiny nezáporných celých čísel. Potom je pro dané r G N počet řešení (/,_/') rovnice /+_/' = r splňujících / G /,_/' G J roven koeficientu u xr v polynomu (J2iei x')E/e./x'/) Příklad Kolika způsoby můžeme pomocí mincí (1, 2, 5, 10, 20 a 50 Kč) zaplatit platbu 100 Kč? Hledáme přirozená čísla a\, 32, 35, 3io, 320 a 350 taková, že 3/ je násobkem / pro všechna / G {1,2,5,10,20,50} a zároveň 3i + 32 + 35 + 3io + 320 + a50 = 100- Podobně jako výše je vidět, že požadovaný počet lze získat jako koeficient u x100 v (l+x + x2 + ...)(l+x2+x4 + ...)(l+x5+x10 + ...) (1 +x10 +x20 + +x20 +x40 + _ )(1 +x50 +x100 + _ ) Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí OOOOOO 0090 oooooooooooo ooooooooooooo Podobným způsobem můžeme znovu velmi snadno odvodit některé kombinatorické vztahy, které známe již z dřívějška. Využijeme přitom binomickou větu. Věta (binomická) Pro n G N a r G M platí Na levou stranu se můžeme dívat jako na součin n polynomů, pravá je zápisem polynomu vzniklého jejich roznásobením. Dosazením čísel x = 1, resp. x = —1 dostáváme známé vzorce: '-" Důsledek • E2=o( 2r (Z) = 0. Vytvořující funkce ooo» Podíváme se teď na obě strany v binomické větě „spojitýma očima" a s využitím vlastností derivací odvodíme další vztah mezi kombinačními čísly. Důsledek Platí k=0 w Důkaz. Na obě strany binomické věty se podíváme jako na polynomiální funkce. Derivací levé strany dostaneme n(l +x)"~1, derivací pravé strany (člen po členu) pak Yl"k=i ^(k)xkl- Dosazením x = 1 dostaneme tvrzení. □ Literatura Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí OOOOOO OOOO »00000000000 ooooooooooooo Definice Buď dána nekonečná posloupnost a = (so, ai, 32,.. .). Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru oo ^ 3/x' = 30 + 3lX + 32X2 H----. /=0 Poznámka O formální mocninné řadě hovoříme proto, že se zatím na tuto řadu díváme čistě formálně jako na jiný zápis dané posloupnosti a nezajímáme se o konvergenci. Na druhou stranu to ale znamená, že formální mocninná řada není funkce a nemůžeme do ní dosazovat. To ovšem vzápětí napravíme, když s využitím znalostí z analýzy nekonečných řad přejdeme od formálních mocninnných řad k příslušným funkcím. Literatura Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo o»oooooooooo ooooooooooooo Posloupnosti samých jedniček odpovídá formální mocninná řada 1 + x + x2 + x3 + • • •. Z analýzy víme, že stejně zapsaná mocninná řada konverguje pro x G (—1,1) a její součet je roven funkci 1/(1 — x). Stejně tak obráceně, rozvineme-li tuto funkci do Taylorovy řady v bodě 0, dostaneme zřejmě původní řadu. Takovéto „zakódování" posloupnosti čísel do funkce a zpět je klíčovým obratem v teorii vytvořujících funkcí. Jak jsme již zmínili, tento obrat lze ale použít pouze tehdy, pokud víme, že řada alespoň v nějakém okolí 0 konverguje. Často ale „diskrétní" matematici používají následující „podvod": • pomocí formálních mocninných řad odvodí nějaký vztah (formuli, rekurenci,...) bez toho, aby se zajímali o konvergenci • jinými prostředky (často matematickou indukcí) tento vztah dokážou Vytvořující funkce oooo Vytvořující funkce v praxi využíváme: • k nalezení explicitní formule pro n-tý člen posloupnosti; • často vytvořující funkce vycházejí z rekurentních vztahů, občas ale díky nim odvodíme rekurentní vztahy nové; • výpočet průměrů či jiných statistických závislostí (např. průměrná složitost algoritmu); • důkaz různých identit; • často je nalezení přesného vztahu příliš obtížné, ale mnohdy stačí vztah přibližný nebo alespoň asymptotické chování. 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 V některých případech (např. v důkazu Cayleyho věty) je použití exponenciálních vytvořujících funkcí výhodnější. 1Použí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 x" hraje n~x), ale těmi se zde zabývat nebudeme. n>0 (1,1,1,1,...). Literatura Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo oooo»ooooooo ooooooooooooo Následující větu znáte z matematické analýzy z loňského semestru: Věta Bud (sq, 3i, 32,...) posloupnost reálných čísel. Platí-li pro nějaké K G M, že pro všechna n > 1 je \an\ < Kn, pak řada a{x) = ^2 an*" n>0 konverguje pro každé x G Součet této řady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a(x). Hodnotami funkce a(x) na libovolném okolí 0 je jednoznačně určena původní posloupnost, nebot má a(x) v 0 derivace všech řádů a platí _ a(")(0) Vytvořující funkce oooo In 1 -x 1 1~ sin x cosx x n n>0 £ n>l T- n>0 n>0 n>0 ,2n+l (2/j + l)!' ^2n (2")!' ' = £ (I fc>0 Vytvořující funkce oooo oooooo»ooooo Poznámka • Poslední vzorec u+*>' = Sil k>0 je tzv. zobecněná binomická věta, kde pro r £ M. je binomický koeficient definován vztahem r(r- l)(r-2)---(r-/c + l) ~k\ ' Speciálně klademe = 1. • Pro n G N z uvedeného vztahu snadno dostaneme 1 _ /O + n - 1 (1 - x)" ~ V n-1 + ... + /c + n- 1 n - 1 xk + Literatura Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo ooooooo^oooo ooooooooooooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (af- + 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. • Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. • Pro posunutí posloupnosti doleva o k míst (tj. vynechání prvních k míst posloupnosti) nejprve od a(x) odečteme polynom bk(x) odpovídají posloupnosti (ao,..., a/c-i, 0,...) a poté podělíme vytvořující funkci xk. « Substitucí polynomu f(x) s nulovým absolutním členem za x vytvoříme specifické kombinace členů původní posloupnosti. Jednoduše je vyjádříme pro f(x) = ax, což odpovídá vynásobení /c-tého členu posloupnosti skalárem ak. Dosazení f(x) = x" nám do posloupnosti mezi každé dva členy vloží n — 1 nul. Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: • Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, 2a2, 333,...), člen s indexem k je (k + l)a/(+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce f* a(t)dt vytvořuje posloupnost (0, 3o, \a\, ^32, \a-i-, ■ ■ ■), pro k > 1 je člen s indexem k roven \sk-\ (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce s(x)). • Násobení řad: součin a{x)b{x) je vytvořující funkcí posloupnosti (cq, ci, c2,...), kde tj. členy v součinu až po c^ jsou stejné jako v součinu (a0 + aix + s2x2 H-----h 3/(x/í)(íjo + bix + ^2^2 H----bkxk). Posloupnost (cn) bývá také nazývána konvolucí posloupností (a„), (/>„). Literatura Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo ooooooooosoo ooooooooooooo Ukažme si důležitý příklad využívající konvoluci posloupností: Příklad j^a(x) je v.f.p. (a0, a0 + ai, a0 + ax + a2,.. .)■ Odtud např. dostáváme, že —-—In—-— je v.f.p. harmonických čísel Hn. 1 — x 1 — x Příklad Protože = ^n>ox"' dostáváme konvoluci posloupnosti (1,1,...) se sebou vztahy v ' n>0 v ' n>0 v 7 což již sice máme dokázáno z dřívějška (dokonce dvakrát - jednou díky zobecněné binomické větě a podruhé díky derivaci řady), ale další důkaz jistě nezaškodí © Motivace oooooo Vytvořující funkce oooo (Formální) mocninné řady oooooooooo»o Řešení rekurencí ooooooooooooo Příklad V krabici je 30 červených, 40 modrých a 50 bílých míčků, míčky stejné barvy přitom nelze rozeznat. Kolika způsoby je možné vybrat soubor 70 míčků? Řešení Hledaný počet je roven koeficientu u x 0 v součinu (l+x + x2 + ---+x30)(l+x + x2 + ---+x40)(l+x + x2 + ---+x50). Tento součin upravíme na tvar (1 — x)~3(l — x31)(l — x41)(l — x51), odkud pomocí zobecněné binomické věty dostaneme ( Q + Q x + Q x" + • • • ) í1 " " ~ + x72 + • • •) a tedy koeficientem u x70 je zřejmě (70+2) _ (70+2-31) _ (70+2-41) _ (70+2-51) = 1Q6L Vytvořující funkce OOOO Příklad Dokažte, že n ^2 Hk = {n+ 1)^^-1). k=l Řešení Potřebnou konvoluci získáme součinem řad v^- a -r^- In 1—x 1—x 1—X Odtud M(TJx7lnT^ = Éi("+1-^)' k=l odkud již snadnou úpravou dostaneme požadované. Literatura Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí OOOOOO OOOO OOOOOOOOOOOO »000000000000 Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí. Tím je míněno vyjádření členu a„ 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á a„, tj. an = [xn]A(x) . Literatura Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo oooooooooooo o»ooooooooooo ' Příklad ^ Řešte rekurenci a0 = 0, ai = 1 3n = 5a„_i — 6an_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 ^ ~ 1 -5x + 6x2 ~ 1 -3x l-2x' • Krok 4: a„ = 3n-2n. Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo oooooooooooo oo»oooooooooo 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„>0 "C,x" = E„>0- i)xn + 2 En>0 ELi C/c-ix" • xC'(x) = ^ + 2*gs> • 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)]' = 3^,) a tedy c(x) = (T^(lnrb-x)' odkud konečně C„ = 2(n + l)(H„+i — 1) — 2n. Literatura Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo oooooooooooo ooo»ooooooooo Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fq = 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. 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). Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo oooooooooooo oooo»oooooooo Příklad - pokr. 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-2 = - + -' 1 — X — Xz X — X\ 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 F_ = ^ • \0 -a- h ■ \" Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo oooooooooooo ooooo»ooooooo S využitím počátečních podmínek dostáváme Fn 1 y/E 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 - y/5)/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. Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo oooooooooooo oooooo»oooooo Rozklad na parciální zlomky - připomenutí 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 Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo oooooooooooo ooooooo^ooooo • 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. Literatura Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo oooooooooooo oooooooo»oooo 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]. 0o^n-i + b\bn-2 + • • • + ^n-i^o vztahem bn = bobn-! H-----h fan-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). 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 — Vl — 4x výrazem 2x dostaneme Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo oooooooooooo ooooooooooo«o Catalanova čísla Dokázali jsme, že počet binárních pěstovaných stromů 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. Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí OOOOOO OOOO OOOOOOOOOOOO 000000000000« Ještě jeden příklad Pří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. < Vytvořující funkce oooo Řešení (pokr.) • Krok 1: an = 3n_i+2an_2 + (-l)>>0] + [n = l]. « Krok 2: ^(x) = xA{x) + 2x2A(x) + j^+x. « Krok 3: A[X)- (l-2x)(l+x)2- • Krok 4: an = Literatura Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo oooooooooooo ooooooooooooo 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 Motivace Vytvořující funkce (Formální) mocninné řady Řešení rekurencí oooooo oooo oooooooooooo ooooooooooooo Ř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 Vytvořující funkce oooo Ř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) = R{X) = l-4x2+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. Vytvořující funkce OOOO Ř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 0 a 1, proto C2n (2 + VŠ)n 3-VŠ Např. c20 = 413403.