Vytvořující funkce a reseni rekur ooooooooooooooooooooo Matematika III - 12. přednáška Vytvořující funkce Michal Bulant Masarykova univerzita Fakulta informatiky 16. 12. 2009 □ S Q Vytvořující funkce a řešení rekurenci • Operace s vytvořujícími funkcemi • Přehled mocninných řad • Fibonacciho čísla • Catalanova čísla O Exponenciální vytvořující funkce Q Pravděpodobnostní vytvořující funkce Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Predmetové záložky v IS MU □ s • Martin Panák, Jan Slovák, Drsná matematika, e-text. a Předmětové záložky v IS MU 9 H. S. Wilf, Generatingfunctionology, Academie Press, druhé vydání, 1994 , (rovněž http://www.math.upenn.edu/~wilf/DownldGF.html) • R. Graham, D. Knuth, 0. Patashnik, Concrete Mathematics, druhé vydání, Addison-Wesley, 1994. Q Vytvořující funkce a řešení rekurenci • Operace s vytvořujícími funkcemi • Přehled mocninných řad • Fibonacciho čísla • Catalanova čísla Q Exponenciální vytvořující funkce Q Pravděpodobnostní vytvořující funkce Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: nHWÄHMHH Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (aj + b;) posloupností člen po členu odpovídá součet a(x) + b{x) příslušných vytvořujících funkcí. □ s nHWÄHMHH Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (aj + 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. □ s nHWÄHMHH Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (aj + 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. □ s Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (aj + 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^-1,0,...) a poté podělíme vytvořující funkci xk. Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (aj + 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^-1,0,...) a poté podělíme vytvořující funkci xk. 9 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í k-tého členu posloupnosti skalárem ak. Dosazení f(x) = x" nám do posloupnosti mezi každé dva členy vloží n — 1 nul. Vytvořující funkce a reseni rekur o«ooooooooooooooooooo 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,3a3,...), člen s indexem k je (k + l)a/c+i (tj. mocninnou řadu derivujeme člen po členu). □ s 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,3a3,...), člen s indexem k je (k + l)a/c+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce Jq a(t)dt vytvořuje posloupnost (0, ao, \a\, 132, ^33,...), pro k > 1 je člen s indexem k je \ak-\ (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce 3(x)). 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,3a3,...), člen s indexem k je (k + l)a/c+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce J0xa(ř)dř vytvořuje posloupnost (0, ao, \a\, 132, ^33,...), pro k > 1 je člen s indexem k je \ak-\ (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce a{x)). • Násobení řad: součin a{x)b{x) je vytvořující funkcí posloupnosti (co, ci, C2,... )> kde Ck = ^2 a;bj. i+j=k (tj. členy v součinu až po c k jsou stejné jako v součinu (a0 + a\x + 32x2 H--------h akxk)(bQ + b\x + b^x2 -\------bkxk). Posloupnost c bývá také nazývána konvolucí posloupností a, b. Vytvořující funkce a reseni rekur oo«oooooooooooooooooo Přehled mocninných řad: 1 In 1-x 1 smx cosx (l+x)' n>0 £ n>l E x" n n>0 D-1)" n>0 (2n + l)! ,2n £(-1,:W' □ g - = Vytvořující funkce a reseni reku ooo«ooooooooooooooooc Poznámka • Posled ní vzorec (1 + xy = k>0 > k je tzv. binom zobecněná binomická věta, kde cký koeficient definován vztahem pro r G M je (0- r(r - -l)(r -2). k\ ■■(r -k + ľ) Speciá lně klademe (o) = 1. Vytvořující funkce a reseni reku ooo«ooooooooooooooooc Poznámka • Posled ní vzorec (1 + xy = k>0 ;> k je tzv. zobecněná binomická věta, kde pro r G M je binom cký koeficient def nová n vztahem fr\ r{r- -l)(r -2). ■■(r -k + ľ) \k)- k\ Speciá lně klademe (£) = 1. • Pro n G N z uvedeného vztahu snad no dostaneme 1 -("-^t n-1, K ..+( :":!:>■- (1-* )"-{n-l) + { Vytvořující funkce a reseni reku oooo»oooooooooooooooc 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ů? □ s Vytvořující funkce a reseni reku oooo»oooooooooooooooc 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 x70 v součinu (l+x + x2 + ---+x30)(l+x + x2 + ---+x40)(l+x + x2 + ---+x70). Vytvořující funkce a reseni reku oooo»oooooooooooooooc 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 x70 v součinu (l+x + x2 + ---+x30)(l+x + x2 + ---+x40)(l+x + x2 + ---+x70). Tento součin upravíme na tvar (1 — x)~3(l — x31)(l — x41)(l — x51), odkud pomocí zobecněné binomické věty dostaneme 2,+ 2X+ 2,'* + (1-x 31 „41 „51 , „72 xbl+x" + ...) a tedy koeficientem u x70 je zřejmě /70+2\ _ /70+2-31N _ /70+2-41\ _ /70+2-51\ 1061. Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fo = 0, Fi = 1, F„_|_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. Našim cílem bude (opět) najít formuli pro výpočet n-tého členu posloupnosti. Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fo = 0, Fi = 1, F„_|_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. 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 = l],[2|n] a pod. Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fo = 0, Fi = 1, F„_|_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. 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 = l],[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). Vytvořující funkce a reseni rekur oooooo»oooooooooooooo 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 F(x) ,2- 1 - x - xz Našim cílem je tedy odvodit vztah pro n-tý člen posloupnosti odpovídající vytvořující funkci F(x) l-x-x2 □ s - oooooo»oooooooooooooo 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 — X — X2 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. Vytvořující funkce a reseni rekur oooooo»oooooooooooooo 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 F(x) 1 - X - X2 ' 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 AB + X — X2 ,2 1 — X — X^ X — X\ 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 = 1/xi, A2 = 1/x2 dostáváme vztah x ab + 1 — x — x2 1 — Aix ' 1 —A2X' odkud snadno pomocí znalostí o vytvořujících funkcích F. = z ■ \" -A- h ■ \Q Vytvořující funkce a reseni rekur ooooooo«ooooooooooooo Příklad - závěr S využitím počátečních podmínek dostáváme 1 (1 + VšY /l-\/5N V5 Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. □ g - = ooooooo«ooooooooooooo Příklad - závěr S využitím počátečních podmínek dostáváme 1 (1 + VšY /l-\/5N V5 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/5)/2 ~ —0.618, vidíme, že pro všech přirozená čísla lze Fn snadno spočítat zaokrouhlením čísla 1 (\+y/Š\n V5{ 2 ) ■ □ s ooooooo«ooooooooooooo Příklad - závěr S využitím počátečních podmínek dostáváme 1 (1 + VšY /l-\/5N V5 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/5)/2 ~ —0.618, vidíme, že pro všechna přirozená čísla lze Fn snadno spočítat zaokrouhlením čísla ■\{l±fi)n- Navíc je vidět, že lim,^«, Fn/Fn+1 = 1/\1 « 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ě. ooooooo«ooooooooooooo Příklad - závěr S využitím počátečních podmínek dostáváme 1 (1 + VšY /l-\/5N V5 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/5)/2 ~ —0.618, vidíme, že pro všechna přirozená čísla lze Fn snadno spočítat zaokrouhlením čísla ■\{l±fi)n- Navíc je vidět, že lim,^«, Fn/Fn+1 = 1/\1 « 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 k-tého stupně s konstatními koeficienty. Má-li charakteristická rovnice jednoduché kořeny, je situace jednodušší- viz dříve. 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). 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", což je vytvořující funkce A(x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). Vytvořující funkce a reseni rekur OOOOOOOO0OOOOOOOOOOOO 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", což je vytvořující funkce A(x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). Q Zjištěná rovnice se vyřeší vzhledem k A(x). □ s 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", což je vytvořující funkce A{x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A{x). Q 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 = [x"]A(x) . 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. 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. Rozklad na parciální zlomky Jak jsme již viděli na příkladu Fibonacciho posloupnosti, v kroku 4 často s výhodou využijeme rozkladu na parciálni 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\,..., ct£ jednoduché, pak Q(X) OL\ + ••• + ae □ S Rozklad na parciální zlomky Jak jsme již viděli na příkladu Fibonacciho posloupnosti, v kroku 4 často s výhodou využijeme rozkladu na parciálni 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\,..., ct£ jednoduché, pak Q(X) OL\ + ••• + ae 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- □ s • 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. (V naších úlohách ale někdy rozložíme i kvadratické faktory na lineární výpočtem kořenů vC.) • 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. (V naších úlohách ale někdy rozložíme i kvadratické faktory na lineární výpočtem kořenů vC.) • Neznámé dopočítáme buď roznásobením a porovnáním koeficientů u jednotlivých mocnin x nebo dosazením jednotlivých kořenů. • 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. (V naších úlohách ale někdy rozložíme i kvadratické faktory na lineární výpočtem kořenů vC.) • Neznámé dopočítáme buď 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 B/(l — ßx)k vydělením čitatele i jmenovatele výrazem (—a)k. Tento výraz již umíme rozvinout do mocninné řady. n 3 - = -E -00*0 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, pra vý binární podstrom]. 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 bo = 1, bi = 1, k = 2, b3 = 5. 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 bo = 1, bi = 1, k = 2, b3 = 5. Snadno nahlédneme, že pro n > 1 vyhovuje bn rekurentní formuli bn = bobn-t + btbn-2 H---------h bn-tbo. 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 bo = 1, bi = 1, k = 2, b3 = 5. Snadno nahlédneme, že pro n > 1 vyhovuje bn rekurentní formuli bn = bobn-t + btbn-2 H---------h bn-tbo. Vidíme, že jde vlastně o konvoluci posloupností. Vztah upravíme, aby platil pro všechna n G A/o: bn= Y^ bkbn_k_x + [n = 0]. 0 = °K = n,k n,k J2bkxk(j2bn-k-ixn-k)+l = ■ Y^ bkxk(xB(x)) + 1 = B(x) ■ xB(x) + 1. □ S V kroku 2 vynásobíme obě strany x" a sečteme. Je-li B{x) odpovídající vytvořující funkce, pak: ß(x) = Y, b°x" = E bkbn-k-ix" + Et" = °K = n n,k n,k = ^M" pUV-'í +1 = = Y bkxk(xB(x)) + 1 = B(x) ■ xB(x) + 1. k Pozorný čtenář si jistě povšiml, že ve výše uvedeném výpočtu jsme nahradili konvoluci bn = bobn-\ + b\bn-i + • • • + bn-\bo vztahem bn = bobn-i H--------h bn-ibo + bnb-\ + 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). Vytvořující funkce a reseni rekur ooooooooooooo«ooooooo V kroku 3 řešíme kvadratickou rovnici B{x) = xB{x)2 + 1 pro E(x): = 1±VT^C v ' 2x 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. □ s - 4 Vytvořující funkce a reseni rekur ooooooooooooo«ooooooo V kroku 3 řešíme kvadratickou rovnici B{x) = xB{x)2 + 1 pro E(x): = 1±VT^C v ' 2x 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 v? k>0 V y k>l a po vydělení 1 — \/l — 4x výrazem 2x dostaneme 2k\k-l (-4x)* n>0 n + 1 n>0 n/ n + 1 □ ► < -E ► < -E ► 4 Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = -^ (2n") - tato významná posloupnost se nazývá posloupnost Catalanových čísel. Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = -^ (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 Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = -^ (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 Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = -^ (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ě uzávorkovaných výrazů složených z levých a pravých závorek Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = -^ (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ě uzá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 □ g - = ^ -00*0 Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = -^ (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ě uzá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. □ g - = ^ -00*0 Příklad * Vyřešte rekurenci a0 = a\ = 1 an = an_i + 2an_2 + (-!)" ooooooooooooooo«ooooo Ještě jeden příklad Příklad Vyřešte rekurenci a0 = ai = 1 a„ = a„_i + 2a„_2 + (-!)" 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 a reseni reku oooooooooooooooo«oooo □ s Vytvořující funkce a reseni reku oooooooooooooooo«oooo Řešení(pokr • Krok 1: a„ = a„_i + 2a„_2 + (-1)> > 0] + [n = 1] • Krok 2: A(x) = xA(x) + 2x2A(x) + j^+x. □ S Vytvořující funkce a reseni reku oooooooooooooooo«oooo Řešení (pokr. • Krok 1: a„ = a„_i + 2a„_2 + (-1)> > 0] + [n = 1]. • Krok 2: A(x) = xA(x) + 2x2A(x) + ^ + x. • Krok 3: 1 + x + x2 A(x) (l-2x)(l+x)2- □ s Vytvořující funkce a reseni reku oooooooooooooooo«oooo Řešení (pokr. • Krok 1: a„ = a„_i + 2a„_2 + (-1)> > 0] + [n = 1]. • Krok 2: A(x) = xA(x) + 2x2A(x) + ^ + x. • Krok 3: A(x) - 1+X + x2 /AW-(l-2x)(l+x)2- • Krok 4: a„ = |2" + Qn + |) (-!)". □ s ooooooooooooooooo«ooo Rekurzivně propojené posloupnosti Někdy dokážeme snadno vyjádřit hledaný počet jen pomocí více vzájemně provázaných posloupností. □ s ooooooooooooooooo«ooo Rekurzivně propojené posloupnosti 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? □ g - = ooooooooooooooooo«ooo Rekurzivně propojené posloupnosti 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? Snadno zjistíme, že c\ = 0, ci = 3, C3 = 0, dále klademe co = 1 (nejde jen o konvenci, má to svou logiku). n S - = -E -00*0 ooooooooooooooooo«ooo Rekurzivně propojené posloupnosti 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? Snadno zjistíme, že c\ = 0, ci = 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 + c„_2, rn = c„_i + r„_2, r0 = 0,n = 1, kde rn je počet pokrytí obdélníku 3 x n, ze kterého jsme odstranili levý horní roh. □ s Vytvořující funkce a reseni rekur oooooooooooooooooo«oo Řešení (pokr.) □ s Vytvořující funkce a reseni reku ooooooooooooooooooo»o Řešení (pokr. □ s Vytvořující funkce a reseni reku ooooooooooooooooooo»o Řešení (pokr. • Krok 1: cn = 2r„_i + c„_2 + [n = 0], r„ = u„_i + rn_2. • Krok 2: C(x) = 2x/?(x) + x2C(x) + 1, /?(x) = xC(x) + x2/?(x). □ g - = Vytvořující funkce a reseni reku ooooooooooooooooooo»o Řešení (pokr.) • Krok 1: cn = 2r„_ • Krok 2: C(x) = 2x/?(x) 4 • Krok 3: C()A — -i + cn-2 + [n x2C(x) + l, 1-x2 ^\x) ■, - 4x2 + x4 ' 1 1 = 0], rn = un-i + ^n-2- /?(x) = = xC(x) + x2/?(x). /?(x) X l-4x2 + X4- □ S - = .= -OQ^O • Krok 1: cn = 2r„_i + c„_2 + [n = 0], r„ = u„_i + r„_2. • Krok 2: C(x) = 2x/?(x) + x2C(x) + 1, /?(x) = xC(x) + x2/?(x). • Krok 3: c(x) = i-^+x«' *(x) = í^xW • 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) = (l-x2)D(x2), tj. [x2"]C(x) = [x2"](l -x2)D(x2) = [x"](l -x)D(x), a tedy C2n = dn — dn-\. Vytvořující funkce a reseni rekur oooooooooooooooooooo« Řešení (závěr) Kořeny 1 — 4x + x2 jsou 2 + \/3 a 2 — \/3 a již standardním způsobem obdržíme (2+ 73)" (2-x/3)n Qn = —-------— + 3-^3 3 + V3 □ g - = Vytvořující funkce a reseni rekur oooooooooooooooooooo« Řešení (závěr) Kořeny 1 — 4x + x2 jsou 2 + \/3 a 2 — \/3 a již standardním způsobem obdržíme (2+ 73)" (2-7Š)" Qn = —-------— + 73 3 + 73 Podobně jako u Fibonacciho posloupnosti je druhý sčítanec pro velká n zanedbatelný a pro všechna n leží mezi 0 a 1, proto Qn (2 + 73)" 3-73 Např. c20 = 413403. □ S ooooooooooooooooooooo Plán přednášky Q Vytvořující funkce a řešení rekurenci • Operace s vytvořujícími funkcemi » Přehled mocninných řad 9 Fibonacciho čísla » Catalanova čísla O Exponenciální vytvořující funkce Pra\ istní vytvořující funkce □ g - = 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\ 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\ Zdůrazněme, že exponenciální vytvořující funkce se od obyčejných liší i standardními operacemi. Vytvořující funkce a reseni rekur ooooooooooooooooooooo Vynásobením x získáme funkci posloupnosti (nan_i). □ s Vytvořující funkce a reseni rekur ooooooooooooooooooooo • Vynásobením x získáme funkci posloupnosti (nan_i). • Derivací získáme funkci odpovídající posunutí doleva. □ s Vytvořující funkce a reseni rekur ooooooooooooooooooooo • Vynásobením x získáme funkci posloupnosti (nan_i). • Derivací získáme funkci odpovídající posunutí doleva. • Integrací získáme funkci odpovídající posunutí doprava. □ s Vytvořující funkce a reseni rekur ooooooooooooooooooooo • Vynásobením x získáme funkci posloupnosti (nan_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 (/D^án-ío tzv. binomické konvoluci fn a gn. □ s Vytvořující funkce a reseni reku ooooooooooooooooooooc Příklad * Řešte re kurenci danou vztahy go = 0, gl = = la předpisem gn = -2ngn_ i + T, (í 'gkgr -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. □ s Vytvořující funkce a reseni reku ooooooooooooooooooooc Příklad * Řešte re kurenci danou vztahy go = 0, gl = = la předpisem gn = -2ngn_ i + T, (í 'gkgr -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. • Krok 1: gn = -2ng„-i + Y,k>o {"k)gkgn-k + [n = 1] . □ s Vytvořující funkce a reseni reku ooooooooooooooooooooc Příklad * Řešte re kurenci danou vztahy go = 0, gl = = la předpisem gn = -2ngn_ i + T, (í 'gkgr -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. • Krok 1: gn = -2ngn-i + Y,k>o {k)gkgn-k + [n • Krok 2: G(x) = -2xG(x) + G(x)2 +x. 1] □ s Vytvořující funkce a reseni reku ooooooooooooooooooooc Řešení (pokr. • Krok 3: Řešením kvadratické rovnice dostaneme G(x) = 1/2(1 + 2x ± Vl + 4x2). Dosazením x = odpovídá znaménko —, proto je řešením funkce 0 vidíme, že G(x) = 1 + 2x - Vl + 4x2 Vytvořující funkce a reseni reku ooooooooooooooooooooc Řešení (pokr. • Krok 3: Řešením kvadratické rovnice dostaneme G(x) = 1/2(1 + 2x ± Vl + 4x2). Dosazením x = odpovídá znaménko —, proto je řešením funkce G(x) 0 vidíme, že 1 + 2x - Vl + 4x2 » Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů Vytvořující funkce a reseni reku ooooooooooooooooooooc Řešení (pokr. • Krok 3: Řešením kvadratické rovnice dostaneme G(x) = 1/2(1 + 2x ± Vl + 4x2). Dosazením x = odpovídá znaménko —, proto je řešením funkce G(x) 0 vidíme, že 1 + 2x - Vl + 4x2 » Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů • 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 - Vl + 4x2 G{x) =----------------------. • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů (TH-r© a ^^•D<\\ v 7 .2 k Odtud, protože E*A = č(x) n>0 máme g2k+i = 0 1 + 2x - Vl + 4x2 Vytvořující funkce a reseni rekur ooooooooooooooooooooo Řešení (dokončení) ^=^EÍ-(-r-2-(tí)- k>\ v 7 x2k. Odtud, protože E*A = č(x) n>0 máme g2k+i = 0 a 1 + 2x - Vl + 4x2 1 Í2k - 2 **=(-« ■iU-ii-P«1 Vytvořující funkce a reseni rekur ooooooooooooooooooooo Řešení (dokončení) ^=^EÍ-(-r-2-(tí)- k>\ v 7 x2k. Odtud, protože E*A = č(x) 1 + 2x - Vl + 4x2 n>0 máme g2k+i = 0 a &k = (-i)k -k(2^Ii) • (2/0! = (-1)"• (2/0!• Cfc-i, kde Cn je n-té Catalanovo číslo. Připomeňme, že jsme již dříve dokázali, že počet stromů na n vrcholech je n{Kn) = nn~2. Dokážeme tento výsledek ještě jednou pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = n{Kn). Již dříve jsme viděli, že ři = Í2 = 1, Í3 = 3. Lze rovněž snadno spočítat U = 16. Připomeňme, že jsme již dříve dokázali, že počet stromů na n vrcholech je n{Kn) = nn~2. Dokážeme tento výsledek ještě jednou pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = n{Kn). Již dříve jsme viděli, že ři = Í2 = 1, Í3 = 3. Lze rovněž snadno spočítat U = 16. 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í. Cayleyho formule Připomeňme, že jsme již dříve dokázali, že počet stromů na n vrcholech je n{Kn) = nn~2. Dokážeme tento výsledek ještě jednou pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = n{Kn). Již dříve jsme viděli, že ři = Í2 = 1, Í3 = 3. Lze rovněž snadno spočítat U = 16. 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 " - E mi E m>0 ki-\------\-km=n-l k\,..., kn k\ ■ ■ ■ km ■ tkx ■ ■ ■ tkn □ s Připomeňme, že jsme již dříve dokázali, že počet stromů na n vrcholech je n{Kn) = nn~2. Dokážeme tento výsledek ještě jednou pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = n{Kn). Již dříve jsme viděli, že ři = Í2 = 1, Í3 = 3. Lze rovněž snadno spočítat U = 16. 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 tn=^^. S (klZ\m)kl'''km'tkí'''tk" m>0 k1+-+km=n-l V Ll ' m/ Např. pro n = 4 máme U = 3ŕ3 + 6řiÍ2 + if. Vytvořující funkce a reseni rekur ooooooooooooooooooooo Ošklivě vypadající rekurenci zjednodušíme substitucí un = ntn. Dostáváme pro n > 1 un _ ^-^ 1 ^-^ n! 2-^ m\ . 2-J m>0 ki-\------\-km=n-l a je vidět, že vnitřní sumu dostaneme jako koeficient u x m-té mocnině řady U(x) = J2un^\- n-l □ g - = Vytvořující funkce a reseni rekur ooooooooooooooooooooo Ošklivě vypadající rekurenci zjednodušíme substitucí un = ntn. Dostáváme pro n > 1 un _ ^-^ 1 ^-^ n! 2-^ m\ 2-^ m>0 ki-\------\-km=n-l ki\'km\ a je vidět, že vnitřní sumu dostaneme jako koeficient u x" 1 v m-té mocnině řady U{x) = J2un^\- Proto je ÍH'-'iEi,0«" m>0 a tedy U{x) =xe U(x) □ S Vytvořující funkce a reseni reku ooooooooooooooooooooc 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 Stix) = £(tír + I)*"1 k>0 k\ □ s - = ■€. -o<\(y Vytvořující funkce a reseni reku ooooooooooooooooooooc 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 Stix) = £(tír + I)*"1 k>0 k\ Snadno je vidět, že £q = ex, dále označujeme £{x) = £\{x). n S - = -E -00*0 Vytvořující funkce a reseni reku ooooooooooooooooooooc 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 Stix) = £(tír + I)*"1 k>0 k\ Snadno je vidět, že £q = ex, dále označujeme £{x) = £\{x). Fakt: ln£t(x) = x • £t(x), tj. spec. £(x) = ex£W . Srovnáním tohoto vztahu s výše uvedeným U(x) = xeu^ vidíme, že U{x)=x£{x). □ S Vytvořující funkce a reseni reku ooooooooooooooooooooc 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 Stix) = £(tír + I)*"1 k>0 k\ Snadno je vidět, že £q = ex, dále označujeme £{x) = £\{x). Fakt: ln£t(x) = x • £t(x), tj. spec. £(x) = ex£W . Srovnáním tohoto vztahu s výše uvedeným U(x) = xeu^ vidíme, že U{x)=x£{x). Proto Un n\ tn = f = -[*nMx) = (n- íy.^-^ix) = n n-2 □ s Q Vytvořující funkce a řešení rekurenci • Operace s vytvořujícími funkcemi » Přehled mocninných řad 9 Fibonacciho čísla » Catalanova čísla Q Exponenciální vytvořující funkce Q Pravděpodobnostní vytvořující funkce n 3 - = -E -00*0 Vytvořující funkce a reseni reku ooooooooooooooooooooc Definice Pravděpodobnostní vytvořující funkcí náhodné veličiny X, která nabývá pouze nezáporné celočíselné hodnoty, nazveme funkci Gx(z) = ^pr(X = /c)zA k>0 □ s Vytvořující funkce a reseni reku ooooooooooooooooooooc Definice Pravděpodobnostní vytvořující funkcí náhodné veličiny X, která nabývá pouze nezáporné celočíselné hodnoty, nazveme funkci Gx(z) = ^pr(X = /c)zA k>0 Z vlastností pravděpodobnosti je vidět, že Gx(l) = 1. Obráceně, libovolná mocninná řada G{z) s nezápornými koeficienty, splňující G(l) = 1 je pravděpodobnostní mocninnou řadou nějaké náhodné veličiny. □ s Vytvořující funkce a reseni reku ooooooooooooooooooooc Definice Pravděpodobnostní vytvořující funkcí náhodné veličiny X, která nabývá pouze nezáporné celočíselné hodnoty, nazveme funkci Gx(z) = ^pr(X = /c)zA k>0 Z vlastností pravděpodobnosti je vidět, že Gx(l) = 1. Obráceně, libovolná mocninná řada G{z) s nezápornými koeficienty, splňující G(l) = 1 je pravděpodobnostní mocninnou řadou nějaké náhodné veličiny. Mocninné řady nám velmi usnadňují výpočet charakteristik náhodných veličin, např. střední hodnoty a rozptylu. E(X) = Y,k- pr(X = k) = J>(X = k) kz fc-ii Gjf(l). k>0 k>0 □ s Podobně pro rozptyl V{X) = E(X2) - E{Xf = Gjf(l) + Gjf(l) - {G'x{lf). □ S - = -E ^Q.O' Podobně pro rozptyl V{X) = E(X2) - E{Xf = Gjf(l) + Gjf(l) - {G'x{lf). □ S - = -E ^Q.O'