Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Matematika III - 13. přednáška Vytvořující funkce Michal Bulant Masarykova univerzita Fakulta informatiky 12. 12. 2012 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo oooooooo Obsah přednášky Pravděpodobnostní vytvořující funkce Q Vytvořující funkce a řešení rekurencí • Mocninné řady • 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 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooooooooooo 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í Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo oooooooo poručené zdroje 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í Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo oooooooo Plán přednášky Pravděpodobnostní vytvořující funkce Q Vytvořující funkce a řešení rekurencí • Mocninné řady • Operace s vytvořujícími funkcemi • Přehled mocninných řad • Fibonacciho čísla • Catalanova čísla Ql Exponenciální vytvořující funkce Q Pravděpodobnostní vytvořující funkce Vytvořující funkce a řešení rekurencí •ooooooooooooooooooooooooooooo Exponenciáln oooooooo vytvořující funkce Pravděpodobnostní vytvořující funko Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují. _ Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce •ooooooooooooooooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují. Příklad Máme v peněžence 4 korunové mince, 5 dvoukorunových a 3 pětikorunové. Z automatu, který nevrací, chceme minerálku za 22 Kč. Kolika způsoby to umíme, aniž bychom ztratili přeplatek? i Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce •ooooooooooooooooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují. Příklad Máme v peněžence 4 korunové mince, 5 dvoukorunových a 3 pětikorunové. Z automatu, který nevrací, chceme minerálku za 22 Kč. Kolika způsoby to umíme, aniž bychom ztratili přeplatek? Hledáme zjevně čísla /', j a k taková, že /+_/' + k = 22 a zároveň / G {0,1, 2, 3,4}, j G {0,2,4, 6, 8,10}, k G {0,5,10,15}. Uvažme součin polynomů (třeba nad reálnými čísly) (X0+Xl+X2+X3+X4)(x0+X2+X4+X6+X8+X10)(x0+X5+X10+Xl5)- Mělo by být zřejmé, že hledaný počet řešení je díky (Cauchyovskému) způsobu násobení polynomů právě koeficient u x22 ve výsledném polynomu. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce •ooooooooooooooooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují. Příklad Máme v peněžence 4 korunové mince, 5 dvoukorunových a 3 pětikorunové. Z automatu, který nevrací, chceme minerálku za 22 Kč. Kolika způsoby to umíme, aniž bychom ztratili přeplatek? i Hledáme zjevně čísla /', j a k taková, že /+_/' + k = 22 a zároveň / G {0,1, 2, 3,4}, j G {0,2,4, 6, 8,10}, k G {0,5,10,15}. Uvažme součin polynomů (třeba nad reálnými čísly) (X0+Xl+X2+X3+X4)(x0+X2+X4+X6+X8+X10)(x0+X5+X10+Xl5)- Mělo by být zřejmé, že hledaný počet řešení je díky (Cauchyovskému) způsobu násobení polynomů právě koeficient u x22 ve výsledném polynomu. Skutečně tak dostáváme čtyři možnosti 3*5 + 3*2 + 1*1, 3*5 + 2*2 + 3*1, 2 * 5 + 5 * 2 + 2 * 1 a 2 * 5+ 4 * 2+ 4 * 1. <9> Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce o»oooooooooooooooooooooooooooo oooooooo Předchozí příklad asi vypadal spíš jako složitý zápis jednoduchých „backtrackingových úvah". Následující příklad ukazuje, že tento postup lze ale s výhodou zobecnit. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce o»oooooooooooooooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Předchozí příklad asi vypadal spíš jako složitý zápis jednoduchých „backtrackingových úvah". Následující příklad ukazuje, že tento postup lze ale s výhodou zobecnit. Nechť /, J jsou konečné množiny nezáporných celých čísel. Potom je pro dané r G N počet řešení (/,_/') rovnice /+_/' = r splňujících / G /,_/' G J roven koeficientu u xr v polynomu (J2iei x')E/e./x'/) Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce o»oooooooooooooooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Předchozí příklad asi vypadal spíš jako složitý zápis jednoduchých „backtrackingových úvah". Následující příklad ukazuje, že tento postup lze ale s výhodou zobecnit. Nechť /, J jsou konečné množiny nezáporných celých čísel. Potom je pro dané r G N počet řešení (/,_/') rovnice /+_/' = r splňujících / G /,_/' G J roven koeficientu u xr v polynomu (J2iei x')E/e./x'/) Příklad Kolika způsoby můžeme pomocí mincí (1, 2, 5, 10, 20 a 50 Kč) zaplatit platbu 100 Kč? Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce o»oooooooooooooooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Předchozí příklad asi vypadal spíš jako složitý zápis jednoduchých „backtrackingových úvah". Následující příklad ukazuje, že tento postup lze ale s výhodou zobecnit. Nechť /, J jsou konečné množiny nezáporných celých čísel. Potom je pro dané r G N počet řešení (/,_/') rovnice /+_/' = r splňujících / G /,_/' G J roven koeficientu u xr v polynomu (J2iei x')E/e./x'/) Příklad Kolika způsoby můžeme pomocí mincí (1, 2, 5, 10, 20 a 50 Kč) zaplatit platbu 100 Kč? Hledáme přirozená čísla a\, 32, 35, 3io, 320 a 350 taková, že 3/ je násobkem / pro všechna / £ {1,2,5,10,20,50} a zároveň 3l + 32 + 35 + 310 + 320 + ^50 = 100. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce o»oooooooooooooooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Předchozí příklad asi vypadal spíš jako složitý zápis jednoduchých „backtrackingových úvah". Následující příklad ukazuje, že tento postup lze ale s výhodou zobecnit. Nechť /, J jsou konečné množiny nezáporných celých čísel. Potom je pro dané r G N počet řešení (/,_/') rovnice /+_/' = r splňujících / G /,_/' G J roven koeficientu u xr v polynomu (J2iei x')E/e./x'/) Příklad Kolika způsoby můžeme pomocí mincí (1, 2, 5, 10, 20 a 50 Kč) zaplatit platbu 100 Kč? ■ Hledáme přirozená čísla a\, 32, 35, 3io, 320 a 350 taková, že 3/ je násobkem / pro všechna / G {1,2,5,10,20,50} a zároveň 3i + 32 + 35 + 3io + 320 + a50 = 100- Podobně jako výše je vidět, že požadovaný počet lze získat jako koeficient u x100 v (l+x + x2 + ...)(l+x2+x4 + ...)(l+x5+x10 + ...) (1 +x10 +x20 + +x20 +x40 + _ )(1 +x50 +x100 + _ ) n^. n>0 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooo»oooooooooooooooooooooo oooooooo Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciální varianty. ár(x) = 2>n^. 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ší. 4Ľ3k4l3*4 = k4 = * -š -O^O Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooosooooooooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Dosazování do mocninných řad Následující větu znáte z matematické analýzy z loňského semestru: Věta Bud (sq, 3i, 32,...) posloupnost reálných čísel. Platí-li pro nějaké K G M, že pro všechna n > 1 je \an\ < Kn, pak řada a{x) = ^2 an*" n>0 konverguje pro každé x G Součet této řady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a(x). Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooosooooooooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Dosazování do mocninných řad Následující větu znáte z matematické analýzy z loňského semestru: Věta Bud (sq, 3i, 32,...) posloupnost reálných čísel. Platí-li pro nějaké K G M, že pro všechna n > 1 je \an\ < Kn, pak řada a{x) = ^2 an*" n>0 konverguje pro každé x G Součet této řady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a(x). Hodnotami funkce a(x) na libovolném okolí 0 je jednoznačně určena původní posloupnost, nebot má a(x) v 0 derivace všech řádů a platí _ a(")(0) Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooo»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í Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooo»oooooooooooooooooooo oooooooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (af- + b,) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce ooooooooo»oooooooooooooooooooo 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í (af- + b,) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení (a • a,-) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a • a(x) příslušné vytvořující funkce. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooo»oooooooooooooooooooo oooooooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (af- + b,) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení (a • a,-) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a • a(x) příslušné vytvořující funkce. • Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooo»oooooooooooooooooooo oooooooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (af- + b,) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení (a • a,-) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a • a(x) příslušné vytvořující funkce. • Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. • Pro posunutí posloupnosti doleva o k míst (tj. vynechání prvních k míst posloupnosti) nejprve od a(x) odečteme polynom bk(x) odpovídají posloupnosti (ao,..., a/c-i, 0,...) a poté podělíme vytvořující funkci xk. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooo»oooooooooooooooooooo oooooooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (af- + b,) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení (a • a,-) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a • a(x) příslušné vytvořující funkce. • Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. • Pro posunutí posloupnosti doleva o k míst (tj. vynechání prvních k míst posloupnosti) nejprve od a(x) odečteme polynom bk(x) odpovídají posloupnosti (ao,..., a/c-i, 0,...) a poté podělíme vytvořující funkci xk. « Substitucí polynomu f(x) s nulovým absolutním členem za x vytvoříme specifické kombinace členů původní posloupnosti. Jednoduše je vyjádříme pro f(x) = ax, což odpovídá vynásobení /c-tého členu posloupnosti skalárem ak. Dosazení f(x) = x" nám do posloupnosti mezi každé dva členy vloží Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooo«ooooooooooooooooooo oooooooo 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 + 1)3^+1 (tj. mocninnou řadu derivujeme člen po členu). Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooo«ooooooooooooooooooo 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/(+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce f* a(t)dt vytvořuje posloupnost (0, ao, |si, ^32, ^33,...), pro k > 1 je člen s indexem /c je \sk-\ (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce s(x)). Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooo«ooooooooooooooooooo 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/(+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce f* a(t)dt vytvořuje posloupnost (0, 3o, |si, ^32, ^33,...), pro k > 1 je člen s indexem k je \sk-\ (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce s(x)). • Násobení řad: součin a{x)b{x) je vytvořující funkcí posloupnosti (cq, ci, C2,...), kde (tj. členy v součinu až po c^ jsou stejné jako v součinu (a0 + aix + s2x2 H-----h akxk)(b0 + í?ix + fa2x2 H----^x^). Posloupnost c bývá také nazývána konvolucí posloupností a, b. i+j=k Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce ooooooooooo»oooooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Přehled mocninných řad: 1 1 -x n>0 1 — x t—' n n>l sin x cosx ^ n!' x2n+l ^(_1)"(2n + l)! n>0 fc>0 v x2n (2n)!' Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooo»ooooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Poznámka • Poslední vzorec u+*>' = Sil k>0 je tzv. zobecněná binomická věta, kde pro r £ M. je binomický koeficient definován vztahem r(r- l)(r-2)---(r-/c + l) Speciálně klademe = 1. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooo»ooooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Poznámka • Poslední vzorec u+*>' = Sil k>0 je tzv. zobecněná binomická věta, kde pro r £ M. je binomický koeficient definován vztahem r(r- l)(r-2)---(r-/c + l) Speciálně klademe = 1. • Pro n G N z uvedeného vztahu snadno dostaneme (1-x)" n- 1 n - 1 + n- 1 n + k-1 n - 1 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce ooooooooooooo»oooooooooooooooo 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ů? 4Ľ3k4l3*4 = k4 = * -š -O^O Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce ooooooooooooo»oooooooooooooooo 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 0 v součinu (l+x + x2 + ---+x30)(l+x + x2 + ---+x40)(l+x + x2 + ---+x70). 00.0 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce ooooooooooooo»oooooooooooooooo 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 0 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 ( Q + Q x + Q x" + • • • ) í1 " " ~ + x72 + • • •) a tedy koeficientem u x70 je zřejmě (70+2) _ (70+2-31) _ (70+2-41) _ (70+2-51) = ^ Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooo»ooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fq = 0, Fi = 1, Fn+2 = Fn+i + Fn. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice (podrobně viz http://is.muni.cz/th/41281/prif_d/disertace.pdf). Našim cílem bude (opět) najít formuli pro výpočet n-tého členu posloupnosti. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooo»ooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fq = 0, Fi = 1, Fn+2 = Fn+i + Fn. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice (podrobně viz http://is.muni.cz/th/41281/prif_d/disertace.pdf). Našim cílem bude (opět) najít formuli pro výpočet n-tého členu posloupnosti. Poznámka (Nejen) pro manipulace se sumami používají autoři Concrete mathematics velmi vhodné označení [logický predikát] -výraz je roven 1 v případě splnění predikátu, jinak 0. Např. [n = 1], [2\n] a pod. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooo»ooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fo = 0, Fi = 1, Fn+2 = Fn+i + Fn. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice (podrobně viz http://is.muni.cz/th/41281/prif_d/disertace.pdf). Našim cílem bude (opět) najít formuli pro výpočet n-tého členu posloupnosti. Poznámka (Nejen) pro manipulace se sumami používají autoři Concrete mathematics velmi vhodné označení [logický predikát] -výraz je roven 1 v případě splnění predikátu, jinak 0. Např. [n = 1], [2\n] a pod. Pro vyjádření koeficientu u x" ve vytvořující funkci F(x) se pak často používá zápis [x"]F(x). ■0 0.0 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo»oooooooooooooo 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_*_x2■ Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo»oooooooooooooo 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_*_x2■ Využijeme k tomu rozklad na parciální zlomky a dostaneme x A B 1-2 = - + -' 1 — X — Xz X — X\ X — X2 kde xi,X2 jsou kořeny polynomu 1 — x — x2 a A, B vhodné konstanty odvozené z počátečních podmínek. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooo»oooooooooooooo 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_*_x2■ Využijeme k tomu rozklad na parciální zlomky a dostaneme x A B 1-2 = - + -' 1 — X — Xz X — X\ X — X2 kde xi,X2 jsou kořeny polynomu 1 — x — x2 a A, B vhodné konstanty odvozené z počátečních podmínek. Po substituci Ai = l/xi,A2 = 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 F_ = a • \0 + h ■ \Q Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooo»ooooooooooooo oooooooo Příklad - závěr S využitím počátečních podmínek dostáváme 1 y/E 1 + VŠ 75 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 oooooooooooooooo»ooooooooooooo oooooooo Příklad - závěr S využitím počátečních podmínek dostáváme 1 V5 1 + VŠ 75 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 V5{ 2 ) ■ Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooo»ooooooooooooo oooooooo Příklad - závěr S využitím počátečních podmínek dostáváme Fn 1 VE Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Uvážíme-li navíc, že (1 - y/5)/2 « -0.618, vid íme, že pro všechna přirozená čísla lze Fn snadno spočítat zaokrouhlením čísla ^(^)". Navíc je vidět, že lim^oo Fn/Fn+1 = 1/Ai «0.618, což je poměr známý jako zlatý řez - objevuje se již od antiky v architektuře, výtvarném umění i hudbě. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooo»ooooooooooooo oooooooo Příklad - závěr S využitím počátečních podmínek dostáváme Fn 1 VE Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Uvážíme-li navíc, že (1 - y/5)/2 « -0.618, vid íme, že pro všechna přirozená čísla lze Fn snadno spočítat zaokrouhlením čísla _i^iiA)n Navíc je vidět, že lim,,^ Fn/Fn+1 = 1/Ai «0.618, což je poměr známý jako zlatý řez - objevuje se již od antiky v architektuře, výtvarném umění i hudbě. Analogický postup je možné použít při řešení obecných lineárních diferenčních rovnic /c-tého stupně s konstatními koeficienty. Má-li charakteristická rovnice jednoduché kořeny, je situace jednodušší- viz dříve. 4 □ ► i X — Ot£ Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooo»ooooooooooo 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 a\,..., ai jednoduché, pak P(x) A, | | Ae Q(X) x — a\ x — ot£ • Má-li kořen a násobnost k, pak jsou příslušné parciální zlomky tvaru Ai A2 | Ak (x — a) (x — a)2 (x — a)k Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooo»oooooooooo oooooooo 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.) Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooo»oooooooooo oooooooo 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 bud' 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í Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooo»oooooooooo oooooooo 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 bud' roznásobením a porovnáním koeficientů u jednotlivých mocnin x nebo dosazením jednotlivých kořenů. • Výrazy A/(x — a)k převedeme na výrazy tvaru 6/(1 — (3x)k vydělením čitatele i jmenovatele výrazem {—a)k. Tento výraz již umíme rozvinout do mocninné řady. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooo»ooooooooo oooooooo Pravděpodobnostní vytvořující funkce 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]. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooo»ooooooooo oooooooo Pravděpodobnostní vytvořující funkce 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 b0 = l,b! = = 2,b3 = 5. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooo»ooooooooo oooooooo Pravděpodobnostní vytvořující funkce 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 b0 = l,b! = = 2,b3 = 5. Snadno nahlédneme, že pro n > 1 vyhovuje bn rekurentní formuli bn = bQbn_i + bibn-2 H-----h ón-i^o- Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooo»ooooooooo oooooooo Pravděpodobnostní vytvořující funkce 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 b0 = l,b! = = 2,b3 = 5. Snadno nahlédneme, že pro n > 1 vyhovuje bn rekurentní formuli bn = b0bn-! + bibn-2 H-----h ón-i^o- Vidíme, že jde vlastně o konvoluci posloupností. Vztah upravíme, aby platil pro všechna n G Nq\ bn= bkbn-k-i + [n = 0]. 0o^n-i + + • • • + ^n-i^o vztahem bn = b0bn-i H-----h ^n-i^o + bnb-i + bn+1b_2 H----■ Díky naší konvenci to ale není problém a velmi to usnadňuje práci se sumami (s nekonečnými součty se zde pracuje podstatně snadněji než s konečnými, kdy musíme neustále hlídat meze). Vytvořující funkce a řešení rekurencí oooooooooooooooooooooo»ooooooo Exponenciální vytvořující funkci oooooooo Pravděpodobnostní vytvořující funkci V kroku 3 řešíme kvadratickou rovnici B(x) B{x): xB(x)2 + 1 pro B{x) 1 ± VI - 4x 2x ' Znaménko + ale nepřichází v úvahu, protože pak by pro x B(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í Exponenciální vytvořující funkce oooooooooooooooooooooo»ooooooo 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+ B(x) měla limitu oo, zatímco vytvořující funkce pro naši posloupnost musí mít v 0 hodnotu bo = 1. Zbývá už pouze krok 4, tedy rozvinout B(x) do mocninné řady. Rozvoj získáme pomocí zobecněné binomické věty B(x): B(x) 1 ± VI - 4x 2x a po vydělení 1 — y/1 — 4x výrazem 2x dostaneme Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooooooo«oooooo oooooooo Catalanova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = ^j(2n") _ tato významná posloupnost se nazývá posloupnost Catalanových čísel. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooooooo«oooooo oooooooo Catalanova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = ^j(2n") _ tato významná posloupnost se nazývá posloupnost Catalanových čísel. Kromě toho, že Catalanova čísla vyjadřují počet binárních pěstovaných stromů, vystupují rovněž jako: • počet slov délky 2n obsahujících n znaků X a Y takových, že žádný prefix slova neobsahuje více Y než X Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooooooo«oooooo oooooooo Catalanova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = ^j(2n") _ tato významná posloupnost se nazývá posloupnost Catalanových čísel. Kromě toho, že Catalanova čísla vyjadřují počet binárních pěstovaných stromů, vystupují rovněž jako: • počet slov délky 2n obsahujících n znaků X a Y takových, že žádný prefix slova neobsahuje více Y než X • podobně takové fronty u pokladny (5koruny a lOkoruny), že nezásobená pokladna může vždy vrátit Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooooooo«oooooo oooooooo Catalanova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = ^j(2n") _ tato významná posloupnost se nazývá posloupnost Catalanových čísel. Kromě toho, že Catalanova čísla vyjadřují počet binárních pěstovaných stromů, vystupují rovněž jako: • počet slov délky 2n obsahujících n znaků X a Y takových, že žádný prefix slova neobsahuje více Y než X • podobně takové fronty u pokladny (5koruny a lOkoruny), že nezásobená pokladna může vždy vrátit • počet korektně ozávorkovaných výrazů složených z levých a pravých závorek Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooooooo«oooooo oooooooo Catalanova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = ^j(2n") _ tato významná posloupnost se nazývá posloupnost Catalanových čísel. Kromě toho, že Catalanova čísla vyjadřují počet binárních pěstovaných stromů, vystupují rovněž jako: • počet slov délky 2n obsahujících n znaků X a Y takových, že žádný prefix slova neobsahuje více Y než X • podobně takové fronty u pokladny (5koruny a lOkoruny), že nezásobená pokladna může vždy vrátit • počet korektně ozávorkovaných výrazů složených z levých a pravých závorek • počet monotónních cest z [0,0] do [n, n] podél stran jednotkových čtverců, které nepřekročí diagonálu Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooooooo«oooooo oooooooo Catalanova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = ^j(2n") _ tato významná posloupnost se nazývá posloupnost Catalanových čísel. Kromě toho, že Catalanova čísla vyjadřují počet binárních pěstovaných stromů, vystupují rovněž jako: • počet slov délky 2n obsahujících n znaků X a Y takových, že žádný prefix slova neobsahuje více Y než X • podobně takové fronty u pokladny (5koruny a lOkoruny), že nezásobená pokladna může vždy vrátit • počet korektně ozávorkovaných výrazů složených z levých a pravých závorek • počet monotónních cest z [0,0] do [n, n] podél stran jednotkových čtverců, které nepřekročí diagonálu • počet různých triangulací konvexního (n + 2)-úhelníku. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooo»ooooo oooooooo Ještě jeden příklad Pravděpodobnostní vytvořující funkce ' Příklad * Vyřešte rekurenci 3q = a1 = 1 3n = 3n-l+2an_2 + (-l)" Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce OOOOOOOOOOOOOOOOOOOOOOOOfMDOOOO oooooooo Ještě jeden příklad Příklad Vyřešte rekurenci 3q = a1 = 1 3n = 3n-l+2an_2 + (-l)" Řešení Tato rekurence je opět jiného typu než dosud studované. Jako vždy neuškodí vypsání prvních několika členů posloupnosti (teď ale ani moc nepomůže, snad jen pro kontrolu správnosti výsledku).3 aNarozdíl od tvrzení v Concrete mathematics je již možné tuto posloupnost nalézt v The On-Line Encyclopedia of Integer Sequences. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooooooooo»oooo oooooooo Řešení (pokr.) • Krok 1: a„ = a„_i + 2an_2 + (-1)> > 0] + [n = 1]. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooooooooooooo«oooo oooooooo Pravděpodobnostní vytvořující funkce Řešení (pokr.) • Krok 1: an = a„_i + 2an_2 + (-!)> > 0] + [n • Krok 2: ^(x) = x^(x) + 2x2^(x) + ^ + x. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooooooooooooo«oooo oooooooo Pravděpodobnostní vytvořující funkce Řešení (pokr.) • Krok 1: a„ = a„_i + 2an_2 + (-1)> > 0] + [n = 1]. • Krok 2: ^(x) = x^(x) + 2x2^(x) + ^ + x. • Krok 3: A(x) - 1+x + x2 A[X)- (l-2x)(l+x)2- Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce ooooooooooooooooooooooooo«oooo oooooooo Pravděpodobnostní vytvořující funkce Řešení (pokr.) • Krok 1: an = 3n_i+2an_2 + (-l)>>0] + [n = l]. « Krok 2: ^(x) = xA{x) + 2x2A(x) + + x. « Krok 3: (l-2x)(l+x)2- • Krok 4: an = Í2"+(J»+ »(-1)". Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooooooo»ooo oooooooo Rekurzivně propojené posloupnosti Někdy dokážeme snadno vyjádřit hledaný počet j vzájemně provázaných posloupností. 4 □ ► Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooo»ooo oooooooo Rekurzivně propojené pošlou Pravděpodobnostní vytvořující funkce 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 oooooooooooooooooooooooooo»ooo oooooooo Rekurzivně propojené pošlou Pravděpodobnostní vytvořující funkce Někdy dokážeme snadno vyjádřit hledaný počet jen pomocí více vzájemně provázaných posloupností. Příklad Kolika způsoby můžeme pokrýt (nerozlíšenými) kostkami domina obdélník 3 x n? Řešení Snadno zjistíme, že c\ = 0, C2 = 3, cj = 0, dále klademe cq = 1 (nejde jen o konvenci, má to svou logiku). Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooo»ooo oooooooo Rekurzivně propojené pošlou Pravděpodobnostní vytvořující funkce Někdy dokážeme snadno vyjádřit hledaný počet jen pomocí více vzájemně provázaných posloupností. Příklad Kolika způsoby můžeme pokrýt (nerozlíšenými) kostkami domina obdélník 3 x n? Řešení Snadno zjistíme, že c\ = 0, c2 = 3, cj = 0, dále klademe cq = 1 (nejde jen o konvenci, má to svou logiku). Najdeme rekurzívní vztah - diskusí chování „na kraji" zjistíme, že cn = 2r„_i + c„_2, rn = c„_i + r„_2, = 0, a = 1, kde rn je počet pokrytí obdélníku 3 x n, ze kterého jsme odstranili levý horní roh. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce ooooooooooooooooooooooooooo»oo oooooooo Řešení (pokr.) Hodnoty cn a rn pro několik malých n jsou: n 0 1 2 3 4 5 6 7 Cn 1 0 3 0 11 0 41 0 rn 0 1 0 4 0 15 0 56 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooooooooo»o oooooooo Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = u„_i + r„_2- ■0 0.0 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooo»o oooooooo Pravděpodobnostní vytvořující funkce Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = u„_i + r„_2- • Krok 2: C(x) = 2xR{x) +x2C(x) + 1, /?(x) =xC(x) + x2/?(x). ■0 0.0 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce OOOOOOOOOOOOOOOOOOOOOOOOOOOOftO oooooooo Pravděpodobnostní vytvořující funkce Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = u„_i + r„_2- • Krok 2: C(x) = 2xR{x) +x2C(x) + 1, /?(x) =xC(x) + x2/?(x). • Krok 3: C(x) l-xz 1 - 4x2 + x4' /?(x) 1 - 4x2 + x4' Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooo»o oooooooo Pravděpodobnostní vytvořující funkce Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = u„_i + r„_2. • Krok 2: C(x) = 2xR{x) +x2C(x) + 1, /?(x) =xC(x) + x2/?(x). • Krok 3: C(X) = R{X) = l-4x2+x*- • Krok 4: Vidíme, že obě funkce jsou funkcemi x2, ušetříme si práci tím, že uvážíme funkci D(z) = 1/(1 — 4z + z2), pak totiž C(x) = (1 -x2)D(x2), tj. [x2n]C(x) = [x2n](l -x2)D(x2) = [x"](l -x)D(x), a tedy C2n = dn — dn-i. ■0 0.0 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce 00000000000000000000000000000» oooooooo Řešení (závěr) Kořeny 1 — 4x + x2 jsou 2 + VŠ a 2 — VŠ a již standardním způsobem obdržíme (2 + y/3)n C2n~ 3-V3 | (2-V3)" 3 + VŠ Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce 00000000000000000000000000000» oooooooo Řešení (závěr) Kořeny 1 — 4x + x2 jsou 2 + 73 a 2 — 73 a již standardním způsobem obdržíme = (2 + 73)" (2 - Všy C2n~ 3-VŠ 3+ 73 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 + 73)"" 3-73 Např. c20 = 413403. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooooooooooo oooooooo Plán přednášky Q Vytvořující funkce a řešení rekurencí • Mocninné řady • Operace s vytvořujícími funkcemi • Přehled mocninných řad • Fibonacci ho čísla • Catalanova čísla Q Exponenciální vytvořující funkce Qi Pravděpodobnostní vytvořující funkce 4 S ► < -š ► < - ► Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO »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 OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO »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 oooooooooooooooooooooooooooooo OftOOOOOO • Vynásobením x získáme funkci posloupnosti (nan-i). Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooooooooooo osoooooo • Vynásobením x získáme funkci posloupnosti (na„_i). • Derivací získáme funkci odpovídající posunutí doleva. 4 n * < & > 4 = * 4 = > -š -O^O Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo osoooooo 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í Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo osoooooo Pravděpodobnostní vytvořující funkce • Vynásobením x získáme funkci posloupnosti (na„_i). • Derivací získáme funkci odpovídající posunutí doleva. • Integrací získáme funkci odpovídající posunutí doprava. » Součinem dvou funkcí F(x) a G(x) získáme funkci H(x), která odpovídá posloupnosti hn = J2k (nk)fkgn-k, tzv. binomické konvoluci fn a gn. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo oo»ooooo Pravděpodobnostní vytvořující funkce Příklad Řešte rekurenci danou vztahy go = 0, g\ = 1 a předpisem gn = -2rt£„_i + ( 1 )Skgn-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. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo oo»ooooo Pravděpodobnostní vytvořující funkce Příklad Řešte rekurenci danou vztahy go = 0, g\ = 1 a předpisem gn = -2rt£„_i + ( 1 )Skgn-k- k>0 Vzhledem k rekurentnímu vztahu, který obsahuje binomickou konvoluci posloupností, se zdá vhodné využít exponenciálních vytvořujících funkcí. Označme G(x) příslušnou exponenciální mocninnou řadu. Budeme postupovat v obvyklých čtyřech krocích. o Krok 1: gn = -2ng„_i + Zk>o (k)Skgn-k + [" = !]■ Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo oo»ooooo Pravděpodobnostní vytvořující funkce Příklad Řešte rekurenci danou vztahy go = 0, g\ = 1 a předpisem gn = -2rt£„_i + ( 1 )Skgn-k- k>0 Vzhledem k rekurentnímu vztahu, který obsahuje binomickou konvoluci posloupností, se zdá vhodné využít exponenciálních vytvořujících funkcí. Označme G(x) příslušnou exponenciální mocninnou řadu. Budeme postupovat v obvyklých čtyřech krocích. o Krok 1: gn = -2ng„_i + Zk>o (k)Skgn-k + [" = !]■ • Krok 2: G(x) = -2xG(x) + G{xf+x. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo ooo«oooo 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 Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooooooo Exponenciální vytvořující funkce ooo«oooo 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) =-2-" • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů ■0 0.0 Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooooooo Exponenciální vytvořující funkce ooo«oooo 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) =-2-" • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů ■0 0.0 Vytvořující funkce a řešení rekurencí oooooooooooooooooooooooooooooo Exponenciální vytvořující funkce ooo«oooo 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 - VI + 4x2 G(x) =-2-" • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů ■0 0.0 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo ooo«oooo 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 G(x) 1 + 2x - Vl + 4x2 • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů -1/2 k 2k k 1/2 k 1 2k -1/2 /c - 1 postupně dostaneme Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo ooo«oooo 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 G(x) 1 + 2x - Vl + 4x2 • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů -1/2 k 2k k 1/2 k 1 2k -1/2 k - 1 postupně dostaneme Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooooooooooo oooo»ooo Řešení (dokončení) Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooooooooooo oooo»ooo Řešení (dokončení) ^Tí?=i+x;i-(-i)»-i-2-(2*_-12 k>l V ■x2k. Odtud, protože ^ x" ~ 1 + 2x - VI + 4x2 ^g„- = G(x) =---, n>0 máme g2k+i = 0 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooooooooooo oooo»ooo Řešení (dokončení) vT7^=i + £í.(-i)<-2.(2,<;2 k>l V ■x2k. Odtud, protože ^ x" ~ 1 + 2x - vi + 4x2 ^g„- = G(x) =---, n>0 máme g2k+i = 0 a £2« = ("lf • 7 1 /2/c - 2 /c V /c - 1 •(2/c)! Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo oooo»ooo Pravděpodobnostní vytvořující funkce Řešení (dokončení) y/l + 4x2 = 1 + V \ ■ ( k>í Odtud, protože n>0 1 + 2x - Vl + 4x2 2 máme g2k+i = 0 a =t-1'* • K* -12) • (2/c)! = (-l)^(2/c)!-Q_1, kde Cn je n-té Catalanovo číslo. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooooooooooo ooooo»oo Cayleyho formule Připomeňme, že jsme již dříve dokázali, že počet stromů na n vrcholech je n(Kn) = n"~2. Dokážeme tento výsledek ještě jednou pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = K,(Kn). Již dříve jsme viděli, že ři = Í2 = 1, Í3 = 3. Lze rovněž snadno spočítat t$ = 16. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooooooooooo ooooo»oo Cayleyho formule Připomeňme, že jsme již dříve dokázali, že počet stromů na n vrcholech je n(Kn) = n"~2. Dokážeme tento výsledek ještě jednou pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = K,(Kn). Již dříve jsme viděli, že ŕi = Í2 = 1) r3 = 3. Lze rovněž snadno spočítat t$ = 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í oooooooooooooooooooooooooooooo yleyho formule Exponenciální vytvořující funkcf ooooo«oo Pravděpodobnostní vytvořující funko Připomeňme, že jsme již dříve dokázali, že počet stromů na n vrcholech je n(Kn) = n"~2. Dokážeme tento výsledek ještě jednou pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = K,(Kn). Již dříve jsme viděli, že ŕi = Í2 = 1) r3 = 3. Lze rovněž snadno spočítat t$ = 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 ^ m\ m>0 k\- E ■+kw—n-l n- 1 ki,..., kn k\ ■ ■ ■ km ■ t^ ■ ■ ■ tkm Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooooooooooo ooooo»oo Cayleyho formule Připomeňme, že jsme již dříve dokázali, že počet stromů na n vrcholech je n(Kn) = n"~2. Dokážeme tento výsledek ještě jednou pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = K,(Kn). Již dříve jsme viděli, že ŕi = Í2 = 1) r3 = 3. Lze rovněž snadno spočítat t$ = 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^ E L" \ )ki---km-tkl---tkni m>0m- kl+...+km=n-1 Víi,---, W Např. pro n = 4 máme t$ = 3t% + 6ŕiŕ2 + tf. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo oooooo»o Pravděpodobnostní vytvořující funkce Ošklivě vypadající rekurenci zjednodušíme substitucí un = ntn. Dostáváme pro n > 1 m>0 k!+-+km^n-l 1 m a je vidět, že vnitřní sumu dostaneme jako koeficient u x"-1 v m-té mocnině řady U(x) = Yl un^\- 4 n * < & > 4 = * 4 = > ^ -O^O Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo oooooo»o Pravděpodobnostní vytvořující funkce Ošklivě vypadající rekurenci zjednodušíme substitucí un = ntn. Dostáváme pro n > 1 m>0 k!+-+km^n-l 1 m a je vidět, že vnitřní sumu dostaneme jako koeficient u x"-1 v m-té mocnině řady U(x) = Yl un^\ - Proto je m>0 a tedy U{x) =xe°W. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 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 £t(x) = J2(tk + l) k>0 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 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 k>0 Snadno je vidět, že £q = ex, dále označujeme £(x) = £\{x). Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 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 k>0 Snadno je vidět, že £q = ex, dále označujeme £(x) = £\{x). Fakt: In £t{x) = x ■ £t(x), tj. spec. £{x) = ex£"W . Srovnáním tohoto vztahu s výše uvedeným U(x) = xeyM vidíme, že U{x)=x£(x). Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 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 k>0 Snadno je vidět, že £q = ex, dále označujeme £(x) = £\{x). Fakt: In £t{x) = x ■ £t(x), tj. spec. £{x) = ex£"W . Srovnáním tohoto vztahu s výše uvedeným U(x) = xeyM vidíme, že U{x)=x£(x). Proto tn = — = -[xn]U{x) = {n- íy.ix"-1^) = nn~2. Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce Pravděpodobnostní vytvořující funkce oooooooooooooooooooooooooooooo oooooooo Plán přednášky Q Vytvořující funkce a řešení rekurencí • Mocninné řady • Operace s vytvořujícími funkcemi • Přehled mocninných řad • Fibonacci ho čísla • Catalanova čísla Qi Exponenciální vytvořující funkce Qi Pravděpodobnostní vytvořující funkce Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo 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) = £>(X = k>0 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo 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) = J2pr(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í Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo 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) = J2pr(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) = E * • pr(X = *) = E P0 k>0 Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Podobně pro rozptyl V(X) = E(X2) - E(X)2 = Gx(l) + G'x(l) - (G'x(l)2). Vytvořující funkce a řešení rekurencí Exponenciální vytvořující funkce oooooooooooooooooooooooooooooo oooooooo Pravděpodobnostní vytvořující funkce Podobně pro rozptyl V(X) = E(X2) - E{Xf = Gx(l) + G'x(l) - (G'x(l)2).