Literatura (Formální) mocninné řady Operace s vytvořujícími funkcemi oooooo ooooo Matematika IV - 8. týden Odvozování kombinatorických identit Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2017 Literatura (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi ooooo Obsah přednášky Q (Formální) mocninné řady • Přehled několika mocninných řad Q Operace s vytvořujícími funkcemi Operace s vytvořujícími funkcemi ooooo Doporučené zdroje Literatura (Formální) mocninné řady oooooo • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. Operace s vytvořujícími funkcemi ooooo Doporučené zdroje Literatura (Formální) mocninné řady oooooo • 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 Programmi • Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994. Literatura Plán přednášky (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi ooooo (Formální) mocninné řady • Přehled několika mocninných řad Literatura (Formální) mocninné řady Operace s vytvořujícími funkcemi •ooooo OOOOO (Formální) mocninné rady Definice Buď dána nekonečná posloupnost a = (ao, ai, a2,.. .)■ JeJí vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru oo a,x' = a0 + aix + a2x2 H----. i=0 Operace s vytvořujícími funkcemi ooooo (Formální) mocninné rady Literatura (Formální) mocninné řady •OOOOO Definice Buď dána nekonečná posloupnost a = (ao, ai, a2,.. .)■ JeJí vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru oo a,x' = a0 + aix + a2x2 H----. i=0 Poznámka O formální mocninné řadě hovoříme proto, že se zatím na tuto řadu díváme čistě formálně jako na jiný zápis dané posloupnosti a nezajímáme se o konvergenci. Na druhou stranu to ale znamená, že formální mocninná řada není funkce a nemůžeme do ní dosazovat. Operace s vytvořujícími funkcemi ooooo (Formální) mocninné rady Literatura (Formální) mocninné řady •OOOOO Definice Buď dána nekonečná posloupnost a = (ao, ai, a2,.. .)■ JeJí vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru oo a,x' = a0 + aix + a2x2 H----. i=0 Poznámka O formální mocninné řadě hovoříme proto, že se zatím na tuto řadu díváme čistě formálně jako na jiný zápis dané posloupnosti a nezajímáme se o konvergenci. Na druhou stranu to ale znamená, že formální mocninná řada není funkce a nemůžeme do ní dosazovat. To ovšem vzápětí napravíme, když s využitím znalostí z analýzy nekonečných řad přejdeme od formálních mocninnných řad k příslušným funkcím. Literatura (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 £ (—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 (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 £ (—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 Literatura (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 £ (—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 (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é; Literatura (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); Literatura (Formální) mocninné řady OO0OOO 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í. Literatura (Formální) mocninné řady OOO0OO Dosazování do mocninných rad Operace s vytvořujícími funkcemi ooooo Následující větu znáte z matematické analýzy z předloňského semestru: Buď (ao, ai, a2,...) posloupnost reálných čísel. Platí-li pro nějaké K g IR, že pro všechna n > 1 je \an\ < Kn, pak rada a(x) = ^ anxn konverguje pro každé x £ (—^, Součet této rady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a(x). Literatura (Formální) mocninné řady OOO0OO Dosazování do mocninných rad Operace s vytvořujícími funkcemi ooooo Následující větu znáte z matematické analýzy z předloňského semestru: Buď (ao, ai, a2,...) posloupnost reálných čísel. Platí-li pro nějaké K g IR, že pro všechna n > 1 je \an\ < Kn, pak rada a(x)= ^2 n>0 konverguje pro každé x £ (—^, 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\ Literatura (Formální) mocninné řady OOOO0O Přehled mocninných řad Operace s vytvořujícími funkcemi ooooo n 1 -x 1 1 -x e = n>0 E n>l E n>0 X" 1 n xn sin x = x 2n+l n>0 (2n + l)!' cosx = X 2n n>0 (2n) k>0 Literatura (Formální) mocninné řady 00000« Operace s vytvořujícími funkcemi ooooo Poznámka • Poslední vzorec k>0 v 7 X je tzv. zobecněná binomická věta, kde pro r e IR je binomický koeficient definován vztahem r\ _ r(r-l)(r-2)-"(r- k + 1) k " k\ ' Speciálně klademe (q) = 1 i—i m1 >0 Q,o Literatura (Formální) mocninné řady 00000« Operace s vytvořujícími funkcemi ooooo Poznámka • Poslední vzorec k>0 v 7 X je tzv. zobecněná binomická věta, kde pro r g IR je binomický koeficient definován vztahem r\ _ r(r-l)(r-2)-"(r- k + 1) k) " k\ ' Speciálně klademe (q) = 1. • Pro íigNz uvedeného vztahu snadno dostaneme _J__(0 + n-l\ (k + n-l\ k (l-x)"~^ n-1 )+ +V n-1 ' + i—i m1 >0 Q,o Operace s vytvořujícími funkcemi ooooo Plán prednášky Literatura (Formální) mocninné řady oooooo • Přehled několika mocninných řad Q Operace s vytvořujícími funkcemi Literatura (Formální) mocninné řady Operace s vytvořujícími funkcemi oooooo •oooo Některým jednoduchým operacím s posloupnostmi odpovídaj jednoduché operace nad mocninnými řadami: Literatura (Formální) mocninné řady Operace s vytvořujícími funkcemi OOOOOO •OOOO Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (a; + b i) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. Literatura (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í (a; + bj) 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 (Formální) mocninné řady Operace s vytvořujícími funkcemi oooooo •oooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (a; + bj) 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. o 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 (Formální) mocninné řady Operace s vytvořujícími funkcemi oooooo •oooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (a; + bj) 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. o Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. 9 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,..., 3k-i, 0,...) a poté podělíme vytvořující funkci xk. -írnJ^ < >• e O Q, O Literatura (Formální) mocninné řady Operace s vytvořujícími funkcemi oooooo •oooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (a; + bj) 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. o Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. 9 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,..., 3k-i, 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) — xn nám do posloupnosti mezi každé dva členy vloží n — 1 nul. Literatura (Formální) mocninné řady Operace s vytvořujícími funkcemi 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: o Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, 2a2, 3a3,...), člen s indexem k je (k + l)ak+i (tj. mocninnou řadu derivujeme člen po členu). Literatura (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: o Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, 2a2, 3a3,...), člen s indexem k je (/c + l^+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce JQX a(t) dt vytvořuje posloupnost (0, ao, |ai, |a2, • • •), pro /c > 1 je člen s indexem k roven \dk-\ (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce a(x)). Literatura (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: o Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, 2a2, 3a3,...), člen s indexem k je (k + l)ak+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce JQX a(t) dt vytvořuje posloupnost (0, ao, |ai, |a2, • • •), pro /c > 1 je člen s indexem k roven \dk-\ (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce a(x)). • Násobení řad: součin a(x)b(x) je vytvořující funkcí posloupnosti (cq, ci, c2,...), kde tj. členy v součinu až po jsou stejné jako v součinu (a0 + aix + a2x2 H-----h a/cx/c)(b0 + bix + b2x2 H----b*x*). Posloupnost (cn) bývá také nazývána konvolucíposloupností i+j=k {an)Abn)- Literatura (Formální) mocninné řady Operace s vytvořujícími funkcemi oooooo oo«oo Ukažme si důležitý příklad využívající konvoluci posloupností: Příklad Y^a(x) je v.f.p. (a0, a0 + ai, a0 + a1 + a2,...) □ S1 Literatura (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 Y^a(x) je v.f.p. (a0, a0 + ai, a0 + a\ + a2,.. .)■ Odtud např. dostáváme, že 11 -In- je v.f.p. harmonických čísel H{ 1 — x 1 — x Ukažme si důležitý příklad využívající konvoluci posloupností: Příklad Y^a(x) je v.f.p. (a0, a0 + ai, a0 + ai + a2,.. .)■ Odtud např. dostáváme, že 11 -In- je v.f.p. harmonických čísel H{ 1 — x 1 — x Příklad Protože = J2n>oxľ1' dostáváme konvoluci posloupnosti (1,1,...) se sebou vztahy (l-x) n>0 Ukažme si důležitý příklad využívající konvoluci posloupností: Příklad Y^a(x) je v.f.p. (a0, a0 + ai, a0 + ai + a2,...) Odtud např. dostáváme, že -In- 1 -x 1 -x je v.f.p. harmonických čísel Hn Příklad Protože = J2n>oxľ1' dostáváme konvoluci posloupnosti (1,1,...) se sebou vztahy 1 =5> + l)x", 1 (1-x) n>0 (1-xV n>0 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 (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi ooo0o 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 (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi ooo0o 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)(l + x + x2 + - • -+x40)(l + x + x2 + - • - + x50). Literatura (Formální) mocninné řady Operace s vytvořujícími funkcemi OOOOOO OOOt>0 V krabici je 30 červených, 40 modrých a 50 bílých míčků, míčky stejné barvy přitom nelze rozeznat. Kolika způsoby je možné vybrat soubor 70 míčků? Řešení Hledaný počet je roven koeficientu u x70 v součinu (l+x + xz + - • -+x30)(l+x + x2 + - • -+x4U)(l+x + x^ + - • -+x*u). 40 30 Tento součin upravíme na tvar (1 — x)_3(l — x31)(l — x41)(l — x51), odkud pomocí zobecněné binomické věty dostaneme (l_x31_x41_x51+x72+ } a tedy koeficient u x70 je zřejmě (70+2) _ (70+2-31) _ (70+2-41) _ (70+2-51) = 1Q6L Literatura (Formální) mocninné řady Operace s vytvořujícími funkcemi oooooo oooo« Příklad 1 Dokažte, že n Y/Hk = (n + l){Hn+1-l). k=l □ s Literatura (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi oooo* Příklad Dokažte, že n Y,Hk = {n + l){Hn+1-l). k=l Řešení Potřebnou konvoluci získáme součinem řad t^- a t^- In t^- Literatura (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi oooo* Příklad Dokažte, že n Y,Hk = {n + l){Hn+1-l). k=l Řešení Potřebnou konvoluci získáme součinem řad t-^- a t-^- In Odtud 1t_j -i 11 i i —x 1—x 1—x n [-n](iÍFlni^ = EK"-^ + i) k=l a snadnou úpravou dostaneme požadované.