Literatura (Formální) mocninné řady oooooooooooo Diskrétní matematika B - 12. (zkrácený) týden Kombinatorické výpočty Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2014 Literatura (Formální) mocninné řady oooooooooooo Ql (Formální) mocninné řady • Přehled mocninných řad • Operace s vytvořujícími funkcemi Literatura (Formální) mocninné řady oooooooooooo • Jan Slovák, Martin Panák, Michal Bulant, Matematika drsně a svižně, MU Brno, 2013, 774 s. (též jako e-text). • Předmětové záložky v IS MU • Donald E. Knuth, The Art Of Computer Programming. • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, MIT Press, 2009. • Robert Sedgewick, Philippe Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 1995. • Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994. • H. S. Wilf, Generatingfunctionology, Academic Press, 1994, (rovněž http://www.math.upenn.edu/~wilf/DownldGF.html) (Formální) mocninné řady •ooooooooooo (Formální) mocninné řady Definice Buď dána nekonečná posloupnost a = (so, ai, 32,.. .). Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru oo ^ 3/x' = 30 + 3lX + 32X2 -\----. /=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»oooooooooo 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 (Formální) mocninné řady oo»ooooooooo 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 ooo»oooooooo Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciální varianty1. Jméno vychází z toho, že exponenciální funkce ex je (exponenciální) vytvořující funkcí pro základní posloupnost V některých případech (např. v důkazu Cayleyho věty) je použití exponenciálních vytvořujících funkcí výhodnější. 1Používají se i další typy vytvořujících funkcí (např. v teorii čísel se používají Dirichletovy vytvořující funkce, kde roli faktoru x" hraje n~x), ale těmi se zde zabývat nebudeme. n>0 (1,1,1,1,...). Literatura (Formální) mocninné řady oooo»ooooooo 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 (Formální) mocninné řady ooooo»oooooo t^-B" n>0 1 - x ^ n n>l sin x cosx x" ^ n! n>0 x2n+l (2/j + l)!' n>0 n>0 k>0 v Literatura (Formální) mocninné řady oooooo»ooooo Poznámka • Poslední vzorec u+*>' = Sil k>0 je tzv. zobecněná binomická věta, kde pro r G 1 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 _ ÍO + n-1 (1 - x)" ~ V n-1 + ... + k + n-1 n - 1 xk + Literatura (Formální) mocninné řady 0000000*0000 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ží n — 1 nul. Literatura (Formální) mocninné řady OOOOOOOO^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 + 1)3^+1 (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 jsou stejné jako v součinu (s0 + 3ix + s2x2 H-----h akxk)(b0 + faix + t^x2 H----bkxk). Posloupnost (cn) bývá také nazývána konvolucí posloupností {an), {bn)- i+j=k Literatura (Formální) mocninné řady ooooooooo^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 v ' n>0 v ' n>0 v 7 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 oooooooooo»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 (Formální) mocninné řady ooooooooooo* 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 M(TJx7lnT^ = Éi("+1-^)' k=l odkud již snadnou úpravou dostaneme požadované.