Generující řady Buď IR. těleso všech reálných čísel. Označme symbolem M[[x] algebru formálních mocninných řad nad tělesem IR. v proměnné x. Prvky této algebry jsou všechny posloupnosti {3n}^0 reálných čísel, které však budeme zapisovat formálně jako mocninné řady Yl^Lo anxľl- Algebra IR[x] tedy v sobě obsahuje okruh polynomů IR[x]. Obvyklé operace sčítání polynomů, násobení polynomů reálnými čísly a násobení polynomů mezi sebou přeneseme přímočaře na celý obor IR[x]. Pro libovolné mocninné řady Yl^Lo a"x"> J2^Lo ^n*" a Pro libovolné reálné číslo r tak klademe oo oo oo A7=0 A7=0 A7=0 OO oo A7=0 A7=0 OO oo oo n 5ľ 3nX" ' 5ľ bnX" = 5ľ Ca7X"' kde pro každé n -íe Cn = 5ľ a'6"-' A7=0 A7=0 A7=0 /'=0 Tím se z oboru IR[x] stává vektorový prostor nad tělesem IR a současně komutativní okruh s jednotkovým prvkem 1. Je vidět, že celkem je M[x] algebrou nad tělesem Pro mocninnou řadu a"x" ^ále definujeme formálně její derivaci předpisem oo \ oo oo 5>„x" =^A7anx"-1 = ^(n + l)an+1x". ,A7=0 / n=l n=0 Pro takto definovanou derivaci aplikovanou na součet či součin mocninných řad pak platí obvyklá pravidla známá z kurzu matematické analýzy. Na mocninnou řadu Yl^Lo a"x" 'ze ovšem pohlížet také jako na řadu reálných funkcí. Z kurzu matematické analýzy víme, že její poloměr konvergence je r = 1/u, kde u = lim sup^^ \Z|a„|. Je-li r > 0, pak na intervalu (—r, r) je tato řada absolutně konvergentní, takže zde můžeme uvažovat její součet a(x). Pak píšeme a(x) = Yl^Lo anx>1'■ V tom případě je součet a(x) funkcí, která má na intervalu (—r, r) všechny derivace. Také víme, že máme-li konvergentní mocninné řady a jejich součty a(x) = a"x" a ^(x) = S^lo ^n^n. pak uvnitř konvergenčních intervalů těchto mocninných řad platí vztahy oo \ / oo \ £>nX" + X>nXn =a(x) + b(x), 77=0 / \A7=0 / OO \ / oo 2 anx" E 6nx" = a(x) • 6(x) A7=0 / \A7=0 77=0 / kde nalevo vystupují výše definované formální operace na mocninných řadách, zatímco napravo jsou obvyklé operace sčítání, násobenia derivace příslušných reálných funkcí. Derivovaná řada má přitom tentýž poloměr konvergence jako řa původní. Pro libovolnou mocninnou řadu YľkLo ak)(k ^ále definujeme její mocninu (YľkĹo akxk)" indukcí vzhledem k exponentu n následovně. Klademe ^ 0 2>x* =1 k=0 a pro každé nezáporné celé číslo n dále klademe oo \ nJr^- / OO \ " / oo k=0 / \k=0 / \k=0 Nyní můžeme pro každou mocninnou řadu Yl^Lo a"x" a Pro každou mocninnou řadu J2T=o bk*k, ve které je bo = 0, definovat složení těchto mocninných řad ja mocninnou řadu OO / OG x 11 12a"[YlbkX> n=0 \k=0 Podmínka bo = 0 zde zaručuje, že v takto definované mocninné řadě u každé mocniny proměnné x se sčítá jenom konečný počet nenulových keoficientů. Jsou-li navíc mocninné řady Yl^Lo a"x" a ^T=o bk*k konvergentní a jsou-li a(x) a b(x) jejich součty, pak také jejich složení je konvergentní mocninnou řadou a platí rovnost oo / oo N n 5> =a(ů(x)). A7=0 \k=0 Z kurzu matematické analýzy víme například, že platí x' 00 ,n ex = —j- pro všechna x 0, pak má tato řada na intervalu (—r, r) svůj součet a(x), což je nějaká reálná funkce určená dotyčnou mocninnou řadou. Naopak zase ale tato reálná funkce a(x) plně určuje výchozí mocninnou řadu ^2^L0 3nxn, neboť pak očividně platí an = a( ^[°^ pro všechna nezáporná celá čísla n. Z kurzu matematické analýzy známe rovněž následující fakt. Tvrzení. Pro libovolné reálné číslo r a pro libovolná x £ (—1,1) platí A7=0 V 7 A7=0 Generující řadou posloupnosti {an}^0 reálných čísel rozumíme formální mocninnou řadu Yl^Lo a"x"'■ Generující funkcí posloupnosti {an}^0 reálných čísel rozumíme součet a(x) mocninné řady J2^Lq 3nxn, má-li tato mocninná řada kladný poloměr konvergence. Exponenciální generující řadou posloupnosti {an}^0 reálných čísel rozumíme generující řadu posloupnosti {7^} 0, to jest formální mocninnou řadu J2^Lo ^tx"- Exponenciální generující funkcí posloupnosti {an}^0 reálných čísel rozumíme součet a(x) mocninné řady ^x"> má-li tato poslední mocninná řada kladný poloměr konvergence. Jako příklad uveďme, že jsme v předchozím tvrzení viděli, že pro libovolné reálné číslo r je funkce (1 + x)r generující funkcí posloupnosti {(„)}^0 a současně je exponenciální generující funkcí posloupnosti {[r]n}^o- Všimněme si, že je-li a(x) = X^=o ^tx" exponenciální generující funkcí posloupnosti {an}(£LQ reálných čísel, pak platí, že an = a^^(0) pro všechna nezáporná celá čísla n. Všimněme si v této souvislosti také toho, že jsou-li YI^Lq ^tx" a YI^Lq ^tx" dvě exponenciální generující řady, pak platí Pomocí generujících funkcí lze dokázat například tzv. Vandermondovu konvoluční formuli. Tvrzení. Pro libovolná reálná čísla p,q a pro libovolné nezáporné celé číslo m platí Ve vztahu (l + x)p+q = (l + x)p{l + x)q nejprve rozvineme všechny tři závorky podle předcházejícího tvrzení do mocninných řad. Tak dostaneme oo p + q m=0 oo (i+*)p=£ r. m P xm x1 i=0 oo Pak poslední dvě závorky a jim příslušné mocninné řady vynásobíme. Tak obdržíme OO / \ \ / oo (i+x)"(i+xr=(5:^x'-j.í j:^? X> takže po vynásobení mocninných řad vyjde m=0 \k=0 V 7 V 7 / Zbývá pak už jen porovnat koeficienty u xm ve výše uvedeném rozvoji závorky (1 + x)p+q a v posledně získaném rozvoji součinu závorek (1 + x)p(l + x)q. □ Vandermondova konvoluční formule se hodí k dokazování některých kombinatorických identit. Jako příklad ukážeme, že pro každé nezáporné celé číslo n platí rovnost K tomu účelu vynásobíme levou stranu této rovnosti převrácenou hodnotou pravé strany a ukážeme, že takto vzniklý výraz je roven 1. Skutečně postupně dostáváme 1 _ (n\y A7 + /c + l ~ (2n + l)!' (2n + l)! vr ,y< (n\ 1 ("O2 'tC '\k)'n + k + l jak bylo požadováno. Vr_i^ "! (2n+l)! 1 ^ ; k\-(n-k)\ n\-n\ n + k + 1 k=0 K ' STl-XÝ {2n + 1)- {n + k)- ' (n-k)\-(n + k + l)\ n\ ■ k\ k=0 n k J \n-k -n-l\ Í2n+1\ (n /c=0 Generující funkce mohou být použity k řešení některých rekurentních formulí. Klasickým příkladem takového užití je následující úloha. Nechť yi,y2,... ,ym kde a? je nějaké kladné celé číslo, jsou prvky nějaké pologrupy, takže je definován jejich součin yi • 3/2.....yn- Kolika způsoby je možno tento součin uzávorkovat tak, aby postup násobení tím byl jednoznačně určen? Označme an hledaný počet těchto uzávorkování. Je jasné, že a\ = 1, B2 = 1, as = 2. Klademe dále ao = 0. Pro libovolné n > 1 lze nejvíce vnější uzávorkování, tedy volbu posledního násobení provést n — 1 způsoby: yi • (y2Yn), (yi.....yk) • (y/c+i.....Yn), (yiYn-l) • Yn- Přitom pro dané k lze prvních k prvků dále uzávorkovat a^ způsoby a posledních n — k prvků an-k způsoby. Celkem to dává, že n-l an = ^2 3k'3n-k pro všechna n > 1. k=i Posloupnost hodnot {an}^0 je tedy řešením této rekurentní formule při výše uvedených počátečních podmínkách. Vezměme generující řadu oo anxn této posloupnosti hodnot. Očekávejme, že tato mocninná řada bude mít kladný poloměr konvergence, a označme a(x) její součet. Poněvadž ao = 0, uvedená rekurentní formule říká, že pro n > 1 koeficient u mocniny xn v součinu řad (Yl^Lo a"x") ' (zC^lo a"x") Je roven hodnotě an. Koeficient u x v tomto součinu je ovšem roven 0, zatímco a\ = 1. Absolutní člen je také roven 0. Celkem to dává, že Pro očekávaný součet a(x) generující řady J2n=o a"x" dostáváme rovnici n 1 ± VI -4x 2 Poněvadž a(0) = 0, ježto ao = 0, v úvahu připadá pouze funkce i-v/r^4x~ 3(x) =-j-' Ale rozvoj této funkce do mocninné řady konverguje pro x £ i i 4' 4 Poněvadž tato funkce splňuje danou kvadratickou rovnici, vyhovují koeficienty jejího rozvoje stanovené rekurentní formuli. Navíc počáteční koeficienty jsou a(0) = 0 a = 1, neboť ^(x) = -j==. Je tedy posloupnost koeficientů rozvoje nalezené funkce a(x) skutečně řešením {an}^0 naší úlohy. Jsme schopni tyto koeficienty rozvoje funkce a(x) do mocninné řady vypočítat pomocí prvního z předcházejících dvou tvrzení: oo = l-(l-4x)i = 1 ~ Eľ=o (l) (~4x)" = _ 1 _ v ) 2 2 2 ^-^ n=l 1 2 n (-4x)n oo = B-ir1 n=l odkud úpravou vychází {i 77-1 ' 2in 22n-lxn A7 *n = ("I)' 2 J A7 o2A7-l n = (-1) „-íl- (-1) ■(-§)•• -(^) k2/i—l i„_1l-3---(2n-l) (2n-l)n! (2n) takže dostáváme n\ (2n-2)! 2(2n- l)(n!)2 ~ n((n- l)!)2 1 /2n-2 3n = n n-1 pro všechna kladná celá čísla n. Tato čísla an bývají pojmenovávána jako Catalanova čísla.