Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Matematika III - 12. přednáška Vytvořující funkce Michal Bulant Masarykova univerzita Fakulta informatiky 15. 12. 2010 Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Obsah přednášky Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Q Vytvořující funkce a řešení rekurencí 9 Mocninné řady • Operace s vytvořujícími funkcemi a Přehled mocninných řad • Fibonacciho čísla • Catalanova čísla Q Exponenciální vytvořující funkce Q Pravděpodobnostní vytvořující funkce Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooooooo oooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. » Předmětové záložky v IS MU Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Doporučené zdroje Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce • Martin Panák, Jan Slovák, Drsná matematika, e-text. » Předmětové záložky v IS MU • H. S. Wilf, Generatingfunctionology, Academie Press, druhé vydání, 1994 , (rovněž http://www.math.upenn.edu/~wilf/DownldGF.html) • R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, druhé vydání, Addison-Wesley, 1994. Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Plán přednášky Q Vytvořující funkce a řešení rekurencí 9 Mocninné řady • Operace s vytvořujícími funkcemi a Přehled mocninných řad • Fibonacciho čísla a Catalanova čísla Q Exponenciální vytvořující funkce Vytvořující funkce a řešení rekurencí •ooooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce (Formální) mocninné řady * Definice Buď dána nekonečná posloupnost a = (ao, a\, 32,.. .). Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru 00 ^ a,x' = ao + aix + a2x2 H----. /=o Vytvořující funkce a řešení rekurencí •ooooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce (Formální) mocninné řady * Definice Buď dána nekonečná posloupnost a = (ao, a\, 32,.. .). Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru 00 ^ a,x' = ao + aix + a2x2 H----. /=o 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. Vytvořující funkce a řešení rekurencí •ooooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Buď dána nekonečná posloupnost a = (ao, a\, 32,.. .)■ Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru 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. 00 ;=o Vytvořující funkce a řešení rekurencí o«oooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Příklad 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 e (—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í. Vytvořující funkce a řešení rekurencí o«oooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Příklad 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 e (—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 □ s - ■ * Vytvořující funkce a řešení rekurencí o«oooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Příklad 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 e (—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 a řešení rekurencí oo«ooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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é; Vytvořující funkce a řešení rekurencí oo«ooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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); Vytvořující funkce a řešení rekurencí oo«ooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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í. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooo«oooooooooooooooooooooo oooooooo Exponenciální vytvořující funkce Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciálníVarianty. n>0 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooo«oooooooooooooooooooooo oooooooo Exponenciální vytvořující funkce Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciálníVarianty. n>0 Poznámka 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 některých případech (např. v důkaze Cayleyho věty) je použití exponenciálních vytvořujících funkcí výhodnější. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooo»ooooooooooooooooooooo oooooooo Dosazování do mocninných řad Následující větu znáte z matematické analýzy z loňského semestru: Věta Buď (ao, 3i, 32,...) posloupnost reálných čísel. Platí-li pro nějaké K G R, že pro všechna n > 1 je \ an\ < K", pak řada a{x) = ^ an*" n>0 konverguje pro každé x e (—^, Součet této řady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a(x). Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooo»ooooooooooooooooooooo oooooooo Dosazování do mocninných řad Následující větu znáte z matematické analýzy z loňského semestru: Věta Buď (ao, 3i, 32,...) posloupnost reálných čísel. Platí-li pro nějaké K G R, že pro všechna n > 1 je \ an\ < K", pak řada a{x) = ^ 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) an =-:—• n\ Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooo«oooooooooooooooooooo oooooooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: Vytvořující funkce a řešení rekurencí ooooo«oooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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í. Vytvořující funkce a řešení rekurencí ooooo«oooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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 i) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a ■ a(x) příslušné vytvořující funkce. Vytvořující funkce a řešení rekurencí ooooo«oooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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. Vytvořující funkce a řešení rekurencí ooooo«oooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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. Vytvořující funkce a řešení rekurencí ooooo«oooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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í /c-tého členu posloupnosti skalárem ak. Dosazení f(x) = x" nám do posloupnosti mezi každé dva členy vloží Vytvořující funkce a řešení rekurencí oooooo»ooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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). Vytvořující funkce a řešení rekurencí oooooo»ooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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(ř) dř vytvořuje posloupnost (0, ao, \a\, |a2, ^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)). Vytvořující funkce a řešení rekurencí oooooo»ooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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/f+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce Jq a{ť) át vytvořuje posloupnost (0, 3o, |ai, |a2, ^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)). • Násobení řad: součin a{x)b{x) je vytvořující funkcí posloupnosti (co, ci, C2,...), kde (tj. členy v součinu až po q jsou stejné jako v součinu (30 + 3ix + 32x2 H-----h akxk)(b0 + bix + b^x2 -\----bkxk). Posloupnost c bývá také nazývána konvolucí posloupností 3, b. i+j=k Vytvořující funkce a řešení rekurencí ooooooo«oooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Přehled mocninných řad: 1 In 1 -x 1 sin x E*° n>0 E n>l E x n>0 X £(-Dn ,2/7+1 n>0 (2n + l)!' ,2/7 cosx = £(_!)»_ ixE Vytvořující funkce a řešení rekurencí OOOOOOOO0OOOOOOOOOOOOOOOOO Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Poznámka • Poslední vzorec ' k>0 v 7 je tzv. zobecněná binomická věta, kde pro r G R je binomický koeficient definován vztahem fr\ = r(r - l)(r - 2) • • • (r -/c + 1) \k) ~ k\ Speciálně klademe (q) = 1. Vytvořující funkce a řešení rekurencí OOOOOOOO0OOOOOOOOOOOOOOOOO Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Poznámka • Poslední vzorec k>0 v 7 je tzv. zobecněná binomická věta, kde pro r e R je binomický koeficient definován vztahem _ r(r-l)(r-2)-(r-/c + l) k\ Speciálně klademe (£) 9 Pro n G N z uvedeného vztahu snadno dostaneme (1-x)" + n- 1 n + k-1 Vytvořující funkce a řešení rekurencí ooooooooo«oooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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ů? Vytvořující funkce a řešení rekurencí ooooooooo«oooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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 v součinu (l+x + x2 + ...+x30)(1+x + x2 + ...+x40)(1+x + x2 + ...+x70) 90.0- Vytvořující funkce a řešení rekurencí ooooooooo«oooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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 v součinu (l+x + x2 + ...+x30)(1+x + x2 + ...+x40)(1+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) + (2)X+(2)x2 + '")(1-x31-x41-x51+x72+-) a tedy koeficientem u x70 je zřejmě (70+2) _ (70+2-31) _ (70+2-41) _ (70+2-51) = ^ Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce OOOOOOOOOO0OOOOOOOOOOOOOOO oooooooo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fo = 0, F\ = 1, Fn+2 = Fn+\ + 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. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce OOOOOOOOOO0OOOOOOOOOOOOOOO oooooooo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fo = 0, F\ = 1, Fn+2 = Fn+\ + 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] apod. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce OOOOOOOOOO0OOOOOOOOOOOOOOO oooooooo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fo = 0, F\ = 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] apod. 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 řešení rekurencí ooooooooooo«oooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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_x_ 2. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooo«oooooooooooooo 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 — 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 řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooo«oooooooooooooo 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 — 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. Po substituci Ai = 1/xi, A2 = 1/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 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce OOOOOOOOOOOO0OOOOOOOOOOOOO oooooooo Příklad - závěr S využitím počátečních podmínek dostáváme V5 Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce OOOOOOOOOOOO0OOOOOOOOOOOOO oooooooo Příklad - závěr S využitím počátečních podmínek dostáváme 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 — V5)/2 ř« —0.618, vidíme, že pro všechna přirozená čísla lze Fn snadno spočítat zaokrouhlením čísla 1 (\ + y/Š\n V5{ 2 ) ■ Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce OOOOOOOOOOOO0OOOOOOOOOOOOO oooooooo Příklad - závěr S využitím počátečních podmínek dostáváme y/5 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 — V5)/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 = « 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ě. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce OOOOOOOOOOOO0OOOOOOOOOOOOO oooooooo Příklad - závěr S využitím počátečních podmínek dostáváme y/5 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 — V5)/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 = « 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. □ g - ■ Vytvořující funkce a řešení rekurencí ooooooooooooo«oooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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 e No (předpokládajíce a_i = a_2 = • • • = 0). Vytvořující funkce a řešení rekurencí ooooooooooooo«oooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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). Q 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 řešení rekurencí ooooooooooooo«oooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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). Q 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). Vytvořující funkce a řešení rekurencí ooooooooooooo«oooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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). Q 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) . Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooo»ooooooooooo oooooooo 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á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. Vytvořující funkce a řešení rekurencí oooooooooooooo»ooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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á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. Vytvořující funkce a řešení rekurencí oooooooooooooo»ooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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 ct\,... ,ct£ jednoduché, pak P{x) _ At + ■■■ + Q(X) x - ai x — ag Vytvořující funkce a řešení rekurencí oooooooooooooo»ooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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 ct\,... ,ct£ jednoduché, pak • Má-li kořen a násobnost k, pak jsou příslušné parciální zlomky P{x) _ At + ■■■ + Q(X) x - ai x — ag tvaru A! , A2 + ■■■ + Ak (x — a) (x — a)2 (x-a)k' Vytvořující funkce a řešení rekurencí ooooooooooooooo«oooooooooo Exponenciální oooooooo vytvořující funkce Pravděpodobnostní vytvořující funkce Rozklad na parciální zlomky - pokr. • V případě dvojice komplexně sdružených kořenů nahrazujeme sčítanec A/(x — a) sčítancem {Ax + 6)/(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ů v C.) Vytvořující funkce a řešení rekurencí ooooooooooooooo«oooooooooo Exponenciální oooooooo vytvořující funkce Pravděpodobnostní vytvořující funkce Rozklad na parciální zlomky - pokr. • 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ů v c.) • 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ů. Vytvořující funkce a řešení rekurencí ooooooooooooooo«oooooooooo Exponenciální oooooooo vytvořující funkce Pravděpodobnostní vytvořující funkce Rozklad na parciální zlomky - pokr. • 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ů v c.) • 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 6/(1 — f3x)k vydělením čitatele i jmenovatele výrazem {—a)k. Tento výraz již umíme rozvinout do mocninné řady. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooo«ooooooooo oooooooo Binární stromy a Catalanova čísla 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]. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooo«ooooooooo oooooooo Binární stromy a Catalanova čísla 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, b2 = 2, b3 = 5. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooo«ooooooooo oooooooo Binární stromy a Catalanova čísla 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, b2 = 2, b3 = 5. Snadno nahlédneme, že pro n > 1 vyhovuje bn rekurentní formuli bn = bobn-t + btbn-2 H-----h bn-tbo. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooo«ooooooooo oooooooo Binární stromy a Catalanova čísla 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, b2 = 2, b3 = 5. Snadno nahlédneme, že pro n > 1 vyhovuje bn rekurentní formuli bn = bobn-l + bibn-2 H-----h 6„_iŮo. Vidíme, že jde vlastně o konvoluci posloupností. Vztah upravíme, aby platil pro všechna n G A/o: bn= bkbn-k-i + [n = 0]. 0 = 0]xn = n n,k n,k = X>X,< (j2bn-k-lXn~^j +1 = = y bkxk(xB(x)) + 1 = B(x) • xB(x) + 1. k Vytvořující funkce a řešení rekurencí ooooooooooooooooo«oooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce V kroku 2 vynásobíme obě strany x" a sečteme. Je-li B(x) odpovídající vytvořující funkce, pak: B{x) = bnxn = bkbn-k-ixn + J> = 0]x" = n n,k n,k = Y^bkxk ^í>n_,_K-^ +1 = = 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 řešení rekurencí oooooooooooooooooo«ooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce V kroku 3 řešíme kvadratickou rovnici B(x) = xB(x)2 + 1 pro E(x): = l±vT^ v ' 2x Znaménko + ale nepřichází v úvahu, protože pak by pro x —> C 6(x) měla limitu oo, zatímco vytvořující funkce pro naši posloupnost musí mít v 0 hodnotu bo = 1. Vytvořující funkce a řešení rekurencí oooooooooooooooooo«ooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce 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+ 6(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 6(x) do mocninné řady. Rozvoj získáme pomocí zobecněné binomické věty B(x): e(x) 1 ± VI -4x 2x k>0 v 7 k>l v 7 a po vydělení 1 — \/l — 4x výrazem 2x dostaneme l/2\ (-4x) n J n + 1 n Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooo»oooooo oooooooo Catalanova čísla 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. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooo»oooooo oooooooo Catalanova čísla 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 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooo»oooooo oooooooo Catalanova čísla 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 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooo»oooooo oooooooo Catalanova čísla 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ě ozávorkovaných výrazů složených z levých a pravých závorek Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooo»oooooo oooooooo Catalanova čísla 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ě 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 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooo»oooooo oooooooo Catalanova čísla 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ě 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. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooo«ooooo oooooooo Ještě jeden příklad Příklad Vyřešte rekurenci ao = ai = 1 a„ = a„_i + 2an_2 + (-!)" Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooo«ooooo oooooooo Ještě jeden příklad Příklad Vyřešte rekurenci ao = a\ = 1 a„ = a„_i + 2a„_2 + (-!)" Ř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 a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooooo»oooo oooooooo Řešení (pokr.) • Krok 1: an = a„_i + 2a„_2 + (-1)> > 0] + [n = 1]. Vytvořující funkce a řešení rekurencí ooooooooooooooooooooo»oooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Řešení (pokr.) • Krok 1: an = a„_i + 2a„_2 + (-1)> > 0] + [n = 1]. • Krok 2: A(x) = xA(x) + 2x2A(x) + ^- + x. Vytvořující funkce a řešení rekurencí ooooooooooooooooooooo»oooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Řešení (pokr.) • Krok 1: an = a„_! + 2a„_2 + (-1)> > 0] + [n = 1]. • Krok 2: A(x) = xA(x) + 2x2A(x) + j^+x. 9 Krok 3: >\M- 1+x + x2 A[X)~ (l-2x)(l+x)2- Vytvořující funkce a řešení rekurencí ooooooooooooooooooooo»oooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Řešení (pokr.) • Krok 1: an = a„_! + 2a„_2 + (-1)> > 0] + [n = 1]. 9 Krok 2: A(x) = xA(x) + 2x2A(x) + j^+x. 9 Krok 3: >\M- 1+x + x2 A[X)~ (l-2x)(l+x)2- • Krok 4: an = Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooo«ooo oooooooo Rekurzivně propojené posloupnosti Někdy dokážeme snadno vyjádřit hledaný počet jen pomocí více vzájemně provázaných posloupností. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooo«ooo oooooooo 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? Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooo«ooo oooooooo 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? Řešení Snadno zjistíme, že c\ = 0, C2 = 3, C3 = 0, dále klademe cq = 1 (nejde jen o konvenci, má to svou logiku). Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooo«ooo oooooooo 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? Řešení Snadno zjistíme, že c\ = 0, C2 = 3, C3 = 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, r0 = 0,n = 1, kde rn je počet pokrytí obdélníku 3 x n, ze kterého jsme odstranili levý horní roh. Vytvořující funkce a řešení rekurencí OOOOOOOOOOOOOOOOOOOOOOO0OO Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Ř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 Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooo«o Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = u„_i + r„_2. □ SI - ■ M Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooo«o Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = un_i + r„_2. • Krok 2: C(x) = 2xR{x) + x2C(x) + 1, R{x) = xC(x) + x2/?(x). □ S - ■ M Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooo«o Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = un-i + r„_2. • Krok 2: C(x) = 2xR{x) + x2C(x) + 1, /?(x) =xC(x) + x2/?(x). • Krok 3: C(x)=l-4x2+x4' □ s - ■ ■* Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooo«o Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Řešení (pokr.) 9 Krok 1: c„ = 2r„_i + c„_2 + [n = 0], rn = + rn_2. a Krok 2: C(x) = 2xR(x) + x2C(x) + 1, R(x) = xC(x) + x2/?(x). « Krok 3: C(x) = , 1~?X2„4, /?(x) 1 - 4x2 + x4 1 - 4x2 + x 4 - • 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 řešení rekurencí 0000000000000000000000000» Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Ř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 + VŠ)n | (2 - x/3)" C2n 3-^3 3 + ^3 Vytvořující funkce a řešení rekurencí 0000000000000000000000000» Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Ř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 + ^3)" (2-x/3)n Qn = —-— + 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 + V3)n 3-VŠ Např. c20 = 413403. Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Plán přednášky Q Vytvořující funkce a řešení rekurencí a Mocninné řady • Operace s vytvořujícími funkcemi 9 Přehled mocninných řad a Fibonacciho čísla » Catalanova čísla Q Exponenciální vytvořující funkce Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce OOOOOOOOOOOOOOOOOOOOOOOOOO «0000000 Exponenciální vytvořující funkce 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\ Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce OOOOOOOOOOOOOOOOOOOOOOOOOO «0000000 Exponenciální vytvořující funkce 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 řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooooooo o»oooooo • Vynásobením x získáme funkci posloupnosti (nan_i). Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce o»oooooo Pravděpodobnostní vytvořující funkce • Vynásobením x získáme funkci posloupnosti (nan_i). • Derivací získáme funkci odpovídající posunutí doleva. Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce o»oooooo Pravděpodobnostní vytvořující funkce • 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. Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce o»oooooo Pravděpodobnostní vytvořující funkce • 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. Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oo«ooooo Pravděpodobnostní vytvořující funkce Příklad Řešte rekurenci danou vztahy go = 0, g\ = 1 a předpisem gn = -2ngn_X + ^ yAgkgn-k- k>0 ^ ' Řešení 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. Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oo«ooooo Pravděpodobnostní vytvořující funkce Příklad Řešte rekurenci danou vztahy go = 0, g\ = 1 a předpisem gn = -2ngn_X + yAgkgn-k- k>0 ^ 7 Řešení 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-X + Y,k>o i.k)Skgn-k + [n = 1] . Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oo«ooooo Pravděpodobnostní vytvořující funkce Příklad Řešte rekurenci danou vztahy go = 0, g\ = 1 a předpisem gn = -2ngn_X + ^ yAgkgn-k- k>0 ^ ' Řešení 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-X + Y,k>o i.k)Skgn-k + [n = 1] . • Krok 2: G(x) = -2xG(x) + G(x)2 +x. Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce OOO0OOOO Pravděpodobnostní vytvořující funkce Ř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 řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce OOO0OOOO Pravděpodobnostní vytvořující funkce Ř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 - Vl + 4x2 G(x) =---. • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce OOO0OOOO Pravděpodobnostní vytvořující funkce Ř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 - Vl + 4x2 G(x) =---. • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce OOO0OOOO Pravděpodobnostní vytvořující funkce Ř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 - Vl + 4x2 G(x) =---. • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů a Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce OOO0OOOO Pravděpodobnostní vytvořující funkce Ř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 - Vl + 4x2 G(x) =---. • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů a postupně dostaneme Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce OOO0OOOO Pravděpodobnostní vytvořující funkce Ř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 - Vl + 4x2 G(x) =---. • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů a postupně dostaneme Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oooo«ooo Pravděpodobnostní vytvořující funkce Řešení (dokončení) ^=i+Ei-(-i)H-!(?:12)' k>l v 7 Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oooo«ooo Pravděpodobnostní vytvořující funkce Řešení (dokončení) v/l + 4x2 = k>\ Odtud, protože ^2 S n n>0 x" - 1 + 2x - Vl + 4x2 2 máme g2k+i = 0 □ S Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oooo«ooo Pravděpodobnostní vytvořující funkce Řešení (dokončení) v/l + 4x2 = k>l (-1)«,(-;i2)^. Odtud, protože ^2 S n n>0 x" - 1 + 2x - Vl + 4x2 2 máme g2k+i = 0 a g2k = (-I)" ' 1 Í2k - 2\ k\k-l) •(2/0! = □ s Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oooo«ooo Pravděpodobnostní vytvořující funkce Řešení (dokončení) \/l + 4x2 = 1 + Y \ ■ ( k>l -I)''-1 • Odtud, protože n>0 1 + 2x - Vl + 4x2 2 máme g2k+i = 0 a «*=<-^K*-"i2)- (2k)\ = (-l)fc.(2/c)!.Cfc_1, kde Cn je n-té Catalanovo číslo. □ s Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce OOOOOOOOOOOOOOOOOOOOOOOOOO OOOOO0OO 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 ř4 = 16. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce OOOOOOOOOOOOOOOOOOOOOOOOOO OOOOO0OO 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í. Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Cayleyho formule Exponenciální vytvořujíc OOOOO0OO Pravděpodobnostní vytvořující funkce 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 m>0 ki-\-----\-km=n-l k\, . . . , kn ki ■ ■ ■ km ■ tkx ■ ■ ■ tkn Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce OOOOOOOOOOOOOOOOOOOOOOOOOO OOOOO0OO 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 m>0 ki-\-----\-km=n-l n-1 k\, . . . , kn k\ ■ ■ ■ km ■ tkx ■ ■ ■ tkn Např. pro n = 4 máme U = 3ŕ3 + 6řiÍ2 + íf. Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oooooo«o Pravděpodobnostní vytvořující funkce Ošklivě vypadající rekurenci zjednodušíme substitucí un = ntn. Dostáváme pro n > 1 un _ \ 1 \ ^ n! ^ m\ ^ m>0 ki-\-----\-km=n-l ^ L^ 1 un _ \ 1 \ ^ n! ^ m\ ^ 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^nj- Proto je Un = lx" ~J m>0 a tedy U(x) =xeĎ(x) Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce 0000000» Pravděpodobnostní vytvořující funkce 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 8t{x) = YJ{tk + lf-^. k>0 Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce 0000000» Pravděpodobnostní vytvořující funkce Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Zobecněnou exponenciální mocninnou řadou £t(x) nazýváme řadu 8t{x) = YJ{tk + lf-^. k>0 Snadno je vidět, že 8q = ex, dále označujeme 8{x) = £\{x). Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce 0000000» Pravděpodobnostní vytvořující funkce Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice Zobecněnou exponenciální mocninnou řadou St{x) nazýváme řadu k>0 Snadno je vidět, že So = ex, dále označujeme S{x) = S\{x). Fakt: ln£t(x) = x • £t(x), tj. spec. S(x) = ex£W . Srovnáním tohoto vztahu s výše uvedeným U(x) = xeu^ vidíme, že U(x)=xS(x). Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce 0000000» Pravděpodobnostní vytvořující funkce Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice Zobecněnou exponenciální mocninnou řadou St{x) nazýváme řadu 8t{x) = YJ{tk + lf-^. k>0 Snadno je vidět, že So = ex, dále označujeme S{x) = S\{x). Fakt: ln£t(x) = x • £t(x), tj. spec. S(x) = ex£W . Srovnáním tohoto vztahu s výše uvedeným U(x) = xeu^ vidíme, že U(x)=xS(x). Proto tn = ^ = ;[x?(x) = (n - mx^nx) = nn~2. Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Plán přednášky Q Vytvořující funkce a řešení rekurencí a Mocninné řady • Operace s vytvořujícími funkcemi 9 Přehled mocninných řad 9 Fibonacciho čísla 9 Catalanova čísla Q Exponenciální vytvořující funkce Q Pravděpodobnostní vytvořující funkce Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Definice Pravděpodobnostní vytvořující funkcí náhodné veličiny X (viz MB104), která nabývá pouze nezáporné celočíselné hodnoty, nazveme funkci Gx{z) = Y,w{X = k)zk. k>0 Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Definice Pravděpodobnostní vytvořující funkcí náhodné veličiny X (viz MB104), která nabývá pouze nezáporné celočíselné hodnoty, nazveme funkci Gx{z) = Y,w{X = k)zk. 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. Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Definice Pravděpodobnostní vytvořující funkcí náhodné veličiny X (viz MB104), která nabývá pouze nezáporné celočíselné hodnoty, nazveme funkci Gx{z) = Yw{X = k)zk. 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) = £ /r • F(X = /r) = £ Pr(* = k) ■ kzk~%=1 = Gx(l). k>0 k>0 Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Podobně pro rozptyl V{X) = E(X2) - E{Xf = Gjf(l) + Gjf(l) - (G^l)2). Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooo Exponenciální vytvořující funkce oooooooo Pravděpodobnostní vytvořující funkce Podobně pro rozptyl V{X) = E(X2) - E(X)2 = Gx(l) + Gjf(l) - (Gx(l)2).