Literatura Vytvořující funkce (Formální) mo cninné řady Operace s vytvořujícíi ni funkcemi ooooo oooooo OOOOO Matematika IV - 8. týden Odvozování kombinatorických identit Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2015 Literatura Vytvořující funkce ooooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi OOOOO Ql Vytvoř uj íc í fu n kce Qf (Formální) mocninné řady • Přehled mocninných řad Q Operace s vytvořujícími funkcemi Literatura Vytvořující funkce (Formální) mo cninné řady Operace s vytvořujícíi ni funkcei ooooo oooooo OOOOO • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. Literatura Vytvořující funkce ooooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi OOOOO • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. • Donald E. Knuth, The Art Of Computer Programming. • Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994. Literatura Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcemi ooooo oooooo OOOOO Plán přednášky Q Vytvořující funkce Q| (Formální) mocninné řady • Přehled mocninných řad Q Operace s vytvořujícími funkcemi Vytvořující funkce •oooo (Formální) OOOOOO Operace s vytvořujícími funkcerr OOOOO Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují. _ Literatura Vytvořující funkce •oooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi ooooo 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 Literatura Vytvořující funkce •oooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi ooooo Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují. Příklad Máme v peněžence 4 korunové mince, 5 dvoukorunových a 3 pětikorunové. Z automatu, který nevrací, chceme minerálku za 22 Kč. Kolika způsoby to umíme, aniž bychom ztratili přeplatek? Hledáme zjevně čísla /', j a k taková, že /+_/' + k = 22 a zároveň / G {0,1, 2, 3,4}, j G {0,2,4, 6, 8,10}, k e {0,5,10,15}. Uvažme součin polynomů (třeba nad reálnými čísly) (X0+Xl+X2+X3+X4)(x0+X2+X4+X6+X8+X10)(x0+X5+X10+Xl5)- Mělo by být zřejmé, že hledaný počet řešení je díky (Cauchyovskému) způsobu násobení polynomů právě koeficient u x22 ve výsledném polynomu. Literatura Vytvořující funkce •oooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi ooooo 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> Literatura Vytvořující funkce (Formální) mo cninné řady Operace s vytvořujícíi ni funkcemi o»ooo oooooo ooooo 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. Literatura Vytvořující funkce (Formální) mo cninné řady Operace s vytvořujícíi ni funkcemi o»ooo oooooo ooooo 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'/) Literatura Vytvořující funkce o»ooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi ooooo 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č? Literatura Vytvořující funkce o»ooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi ooooo 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. Literatura Vytvořující funkce o»ooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi ooooo 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 + )(1 +x20 +x40 + _ )(1 +x50 +x100 + } +(^+-+C)^ Na levou stranu se můžeme dívat jako na součin n polynomů, pravá je zápisem polynomu vzniklého jejich roznásobením. Dosazením čísel x = 1, resp. x = —1 dostáváme známé vzorce: Důsledek • ĽJU (Z) = 2", •E2=o(-i)fc(2)=o. Literatura Vytvořující funkce oooo» (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi ooooo Podíváme se teď na obě strany v binomické větě „spojitýma očima" a s využitím vlastností derivací odvodíme další vztah mezi kombinačními čísly. Důsledek Platí k=0 w Literatura Vytvořující funkce oooo» (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi ooooo Podíváme se teď na obě strany v binomické větě „spojitýma očima" a s využitím vlastností derivací odvodíme další vztah mezi kombinačními čísly. Důsledek Platí k=0 w Důkaz. Na obě strany binomické věty se podíváme jako na polynomiální funkce. Derivací levé strany dostaneme n(l + x)"~1, derivací pravé strany (člen po členu) pak Yl"k=i ^(k)xkl- Dosazením x = 1 dostaneme tvrzení. □ 4Ľ3*4l3*4 = k4 = * ^ -O^O Literatura Vytvořující funkce (Formální) m ocninné řady Operace s vytvořujícími funkcemi ooooo oooooo OOOOO Plán přednášky Q Vytvoř uj íc í f u n kce Q (Formální) mocninné řady • Přehled mocninných řad Q| Operace s vytvořujícími funkcemi Literatura Vytvořující funkce ooooo (Formální) mocninné řady •OOOOO Operace s vytvořujícími funkcemi OOOOO Definice Buď dána nekonečná posloupnost a = (so, ai, 32,...). Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru oo ^ a/x' = a0 + 3iX + a2x2 H----. /=0 Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcemi OOOOO »00000 ooooo Definice Buď dána nekonečná posloupnost a = (ao, ai, 32,.. .). Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru oo ^ a/x' = a0 + 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. ■0 0.0 Literatura Vytvořující funkce ooooo (Formální) mocninné řady •OOOOO Operace s vytvořujícími funkcemi OOOOO Buď dána nekonečná posloupnost a = (ao, ai, 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. oo ■0 0.0 Literatura Vytvořující funkce ooooo (Formální) mocninné řady o«oooo Operace s vytvořujícími funkcemi OOOOO 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 G (—1,1) a její součet je roven funkci 1/(1 — x). Stejně tak obráceně, rozvineme-li tuto funkci do Taylorovy řady v bodě 0, dostaneme zřejmě původní řadu. Takovéto „zakódování" posloupnosti čísel do funkce a zpět je klíčovým obratem v teorii vytvořujících funkcí. Literatura Vytvořující funkce ooooo (Formální) mocninné řady o«oooo Operace s vytvořujícími funkcemi OOOOO 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 G (—1,1) a její součet je roven funkci 1/(1 — x). Stejně tak obráceně, rozvineme-li tuto funkci do Taylorovy řady v bodě 0, dostaneme zřejmě původní řadu. Takovéto „zakódování" posloupnosti čísel do funkce a zpět je klíčovým obratem v teorii vytvořujících funkcí. Jak jsme již zmínili, tento obrat lze ale použít pouze tehdy, pokud víme, že řada alespoň v nějakém okolí 0 konverguje. Často ale „diskrétní" matematici používají následující „podvod": • pomocí formálních mocninných řad odvodí nějaký vztah (formuli, rekurenci,...) bez toho, aby se zajímali o konvergenci 4Ľ3k4l3*4 = k4 = * -š -O^O Literatura Vytvořující funkce ooooo (Formální) mocninné řady o«oooo Operace s vytvořujícími funkcemi OOOOO 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 G (—1,1) a její součet je roven funkci 1/(1 — x). Stejně tak obráceně, rozvineme-li tuto funkci do Taylorovy řady v bodě 0, dostaneme zřejmě původní řadu. Takovéto „zakódování" posloupnosti čísel do funkce a zpět je klíčovým obratem v teorii vytvořujících funkcí. - Jak jsme již zmínili, tento obrat lze ale použít pouze tehdy, pokud víme, že řada alespoň v nějakém okolí 0 konverguje. Často ale „diskrétní" matematici používají následující „podvod": • pomocí formálních mocninných řad odvodí nějaký vztah (formuli, rekurenci,...) bez toho, aby se zajímali o konvergenci • jinými prostředky (často matematickou indukcí) tento vztah dokážou Literatura Vytvořující funkce (Formální) mo cninné řady Operace s vytvořujícíi ni funkcemi ooooo oo»ooo OOOOO 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é; 4Ľ3k4l3*4 = k4 = * -š -O^O Literatura Vytvořující funkce ooooo (Formální) mocninné řady oo»ooo Operace s vytvořujícími funkcemi OOOOO 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); 4Ľ3k4l3*4 = k4 = * -š -O^O Literatura Vytvořující funkce ooooo (Formální) mocninné řady oo»ooo Operace s vytvořujícími funkcemi OOOOO 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í. 4Ľ3k4l3*4 = k4 = * -š -O^O Literatura Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcem ooooo ooo»oo ooooo 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). Literatura Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcem ooooo ooo»oo ooooo 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) Literatura Vytvořující funkce (Formální) mo cninné řady Operace s vytvořujícíi ni funkcei ooooo oooo»o OOOOO t^-B" n>0 1 - x ^ n n>l sin x cosx x" ^ n! n>0 x2n+l (2/j + l)! n>0 fc>0 v X Literatura Vytvořující funkce OOOOO (Formální) mocninné řady 00000» Operace s vytvořujícími funkcemi OOOOO Poznámka • Poslední vzorec u+*>' = Eli k>0 je tzv. zobecněná binomická věta, kde pro r £ M. je binomický koeficient definován vztahem r(r- l)(r-2)---(r-/c + l) ~k\ ' Speciálně klademe (£) = 1. Literatura Vytvořující funkce ooooo (Formální) mocninné řady 00000» Operace s vytvořujícími funkcemi OOOOO Poznámka • Poslední vzorec u+*>' = Eli k>0 je tzv. zobecněná binomická věta, kde pro r G M je binomický koeficient definován vztahem r\ _ r(r- l)(r - 2) • • • (r - k + 1) k) ~ k\ ' Speciálně klademe (£) = 1. • Pro n G N z uvedeného vztahu snadno dostaneme 1 /o + i)-l\ fk + n-i\ (í^=( „-1 )+-+{ n-1 ]x + 3 -00.0 Literatura Vytvořující funkce ooooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi OOOOO Ql Vytvoř uj íc í fu n kce Q (Formální) mocninné řady • Přehled mocninných řad Q Operace s vytvořujícími funkcemi Literatura Vytvořující funkce (Formální) mo cninné řady Operace s vytvořujícír tií funkcemi OOOOO oooooo •oooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: Literatura Vytvořující funkce (Formální) mo cninné řady Operace s vytvořujícír tií funkcemi ooooo oooooo •oooo 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í. Literatura Vytvořující funkce ooooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi •oooo 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. Literatura Vytvořující funkce (Formální) mo cninné řady Operace s vytvořujícír tií funkcemi ooooo oooooo •oooo 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. Literatura Vytvořující funkce (Formální) mo cninné řady Operace s vytvořujícír tií funkcemi ooooo oooooo •oooo 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. Literatura Vytvořující funkce (Formální) mo cninné řady Operace s vytvořujícír tií funkcemi ooooo oooooo •oooo 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ží Literatura Vytvořující funkce (Formální) mo cninné řady Operace s vytvořujícír tií funkcemi ooooo oooooo o»ooo 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). Literatura Vytvořující funkce ooooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi o»ooo 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 (si, 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, \a\, ^32, \a-i-, ■ ■ ■), pro k > 1 je člen s indexem k roven \sk-\ (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce s(x)). Literatura Vytvořující funkce ooooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi o»ooo 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 (si, 2a2, 333,...), člen s indexem k je (k + l)a/(+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce f* a(t)dt vytvořuje posloupnost (0, 3o, \a\, ^32, \a-i-, ■ ■ ■), pro k > 1 je člen s indexem k roven \sk-\ (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce s(x)). • Násobení řad: součin a{x)b{x) je vytvořující funkcí posloupnosti (cq, ci, C2,...), kde tj. členy v součinu až po ck jsou stejné jako v součinu (s0 + aix + s2x2 H-----h akxk)(b0 + faix + t^x2 H----bkxk). Posloupnost (c„) bývá také nazývána konvolucí posloupností i+j=k (3n), {t>n)- Literatura Vytvořující funkce (Formální) mo cninné řady Operace s vytvořující tií funkcemi ooooo oooooo oo»oo Ukažme si důležitý příklad využívající konvoluci posloupností: Příklad j^a(x) je v.f.p. (a0, a0 + ai, a0 + ax + a2,.. .)■ Literatura Vytvořující funkce ooooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi OOftOO Ukažme si důležitý příklad využívající konvoluci posloupností: Příklad j-^a(x) je v.f.p. (a0, a0 + ai, a0 + ax + a2,.. .). Odtud např. dostáváme, že —-—In—-— je v.f.p. harmonických čísel Hn. 1 — x 1 — x 4Ľ3k4l3*4 = k4 = * ^ -O^O Literatura Vytvořující funkce ooooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi oo»oo Ukažme si důležitý příklad využívající konvoluci posloupností: Příklad j^a(x) je v.f.p. (a0, a0 + ai, a0 + ax + a2,.. .)■ Odtud např. dostáváme, že —-—In—-— je v.f.p. harmonických čísel Hn. 1 — x 1 — x Příklad Protože = ^n>ox"' dostáváme konvoluci posloupnosti (1,1,...) se sebou vztahy v ' n>0 Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcemi ooooo oooooo oo»oo Ukažme si důležitý příklad využívající konvoluci posloupností: Příklad j^a(x) je v.f.p. (a0, a0 + ai, a0 + ax + a2,.. .)■ Odtud např. dostáváme, že —-—In—-— je v.f.p. harmonických čísel Hn. 1 — x 1 — x Příklad Protože = J2n>oxn' dostáváme konvoluci posloupnosti (1,1,...) se sebou vztahy (1 ' n>0 v ' n>0 n + 2 což již sice máme dokázáno z dřívějška (dokonce dvakrát - jednou díky zobecněné binomické větě a podruhé díky derivaci řady), ale další důkaz jistě nezaškodí © Literatura Vytvořující funkce ooooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi ooo»o 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ů? Literatura Vytvořující funkce ooooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi ooo»o Příklad V krabici je 30 červených, 40 modrých a 50 bílých míčků, míčky stejné barvy přitom nelze rozeznat. Kolika způsoby je možné vybrat soubor 70 míčků? Řešení Hledaný počet je roven koeficientu u x 0 v součinu (l+x + x2 + ---+x30)(l+x + x2 + ---+x40)(l+x + x2 + ---+x50). 00.0 Literatura Vytvořující funkce ooooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi ooo»o Příklad V krabici je 30 červených, 40 modrých a 50 bílých míčků, míčky stejné barvy přitom nelze rozeznat. Kolika způsoby je možné vybrat soubor 70 míčků? Řešení Hledaný počet je roven koeficientu u x 0 v součinu (l+x + x2 + ---+x30)(l+x + x2 + ---+x40)(l+x + x2 + ---+x50). Tento součin upravíme na tvar (1 — x)~3(l — x31)(l — x41)(l — x51), odkud pomocí zobecněné binomické věty dostaneme ( Q + Q x + Q x" + • • • ) í1 " " ~ + x72 + • • •) a tedy koeficientem u x70 je zřejmě (70+2) _ (70+2-31) _ (70+2-41) _ (70+2-51) = 1Q6L Literatura Vytvořující funkce (Formální) mo cninné řady Operace s vytvořující tií funkcemi ooooo oooooo oooo» Příklad Dokažte, že n ^2 Hk = {n+ 1)^^-1). k=l Literatura Vytvořující funkce ooooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi oooo» ' Příklad * Dokažte, že n ^2 Hk = {n+ 1)^^-1). k=l Řešení Potřebnou konvoluci získáme součinem řad a In Literatura Vytvořující funkce ooooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi oooo» Příklad Dokažte, že n ^2 Hk = {n+ 1)^^-1). k=l Řešení Potřebnou konvoluci získáme součinem řad v^- a -r^- In 1—x 1—x 1—X Odtud Mrrix7lnr^ = Éi(" + 1-^' k=l odkud již snadnou úpravou dostaneme požadované.