Diskrétní matematika - 10. týden Vytvořující funkce
kcemi
Lukáš Vokřínek
Masarykova univerzita Fakulta informatiky
podzim 2020
Literatura
Vytvořující funkce ooooo
(Formální) mocninné řady oooooo
Operace s vytvořujícími funkcemi OOOOO
Obsah 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
Literatura Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcemi
ooooo oooooo ooooo
Doporučené zdroje
• Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne.
□ s
=
Literatura
Vytvořující funkce ooooo
(Formální) mocninné řady oooooo
Operace s vytvořujícími funkcemi OOOOO
Doporučené zdroje
• 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
Vytvořující funkce ooooo
(Formální) mocninné řady oooooo
Operace s vytvořujícími funkcemi OOOOO
Plán prednášky
Q Vytvořující funkce
• Přehled mocninných řad
J J
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í.
□ s
Literatura Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcemi
•oooo oooooo 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 dvou korunový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?
Literatura Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcemi
•oooo oooooo 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 dvou korunový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 i: + j: + k = 22 a zároveň
i 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 +x15 )
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 (Formální) mocninné řady Operace s vytvořujícími funkcemi
•oooo oooooo ooooo
Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují.
Máme v peněžence 4 korunové mince, 5 dvou korunový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 i: + j: + k = 22 a zároveň
i 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 +x15 )
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.
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.
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 £ N počet řešení (ij) rovnice / + j — r splňujících / £ IJ £ J roven koeficientu u xr v polynomu x')(S/eJ x"0-
Literatura	Vytvořující funkce	(Formální) mocninné řady	Operace s vytvořujícími 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 £ N počet řešení (ij) rovnice / + j — r splňujících / £ IJ £ J roven koeficientu u xr v polynomu x')(S/eJ x"0-
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	(Formální) mocninné řady	Operace s vytvořujícími 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 £ N počet řešení (ij) rovnice / + j — r splňujících / £ IJ £ J roven koeficientu u xr v polynomu x')(S/eJ x"0-
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 ai, a2, 35, aio, ^20 a a50 taková, že a/je násobkem / pro všechna / e {1,2,5,10,20,50} a zároveň ai + a2 + a5 + ai0 + a2o + a50 = 100.
Literatura	Vytvořující funkce	(Formální) mocninné řady	Operace s vytvořujícími 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 £ N počet řešení (ij) rovnice / + j — r splňujících / £ IJ £ J roven koeficientu u xr v polynomu x')(ž2jeJ x"0
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 ai, a2, 35, aio, ^20 a a50 taková, že a/je násobkem / pro všechna / G {1,2,5,10,20,50} a zároveň ai + a2 + 35 + aio + a2o + ^50 = 100. Podobně jako výše je vidět, že požadovaný počet lze získat jako koeficient u x100 v
(1 + x + x2 + ... )(1 + x2 + x4 + ... )(1 + x5 + x10 + . . . ) (l+x10+x20 + ...)(l + x20 + x40 + ...)(l+x50 +x100 + ...)
Literatura
Vytvořující funkce OOtOO
(Formální) mocninné řady oooooo
Operace s vytvořujícími funkcemi OOOOO
Příklad
V krabici je 5 červených, 10 modrých a 15 bílých míčků, míčky stejné barvy přitom nelze rozeznat. Kolika způsoby je možné vybrat soubor 7 míčků k vyzkoušení? A o kolik míň to bude, když chceme aspoň 1 červený, aspoň 2 modré a aspoň 3 bílé?
Literatura
Vytvořující funkce OOtOO
(Formální) mocninné řady oooooo
Operace s vytvořujícími funkcemi ooooo
Příklad
V krabici je 5 červených, 10 modrých a 15 bílých míčků, míčky stejné barvy přitom nelze rozeznat. Kolika způsoby je možné vybrat soubor 7 míčků k vyzkoušení? A o kolik míň to bude, když chceme aspoň 1 červený, aspoň 2 modré a aspoň 3 bílé?
Řešení
Hledaný počet je roven koeficientu u x7 v součinu
(1+x + x^H-----hxD)(l+x + x^H-----hx10)(l+x + x^H-----hx1D).
.15
Literatura
Vytvořující funkce OOtOO
(Formální) mocninné řady oooooo
Operace s vytvořujícími funkcemi OOOOO
Příklad
V krabici je 5 červených, 10 modrých a 15 bílých míčků, míčky stejné barvy přitom nelze rozeznat. Kolika způsoby je možné vybrat soubor 7 míčků k vyzkoušení? A o kolik míň to bude, když chceme aspoň 1 červený, aspoň 2 modré a aspoň 3 bílé?
Řešení
Hledaný počet je roven koeficientu u x7 v součinu
(1+x + x^H-----r-xD)(l+x + x^H-----r-x10)(l+x + x^H-----hx1D).
.15
Když máme předepsaný nějaký počet jako nejmenší možný, prostě začneme až od příslušných mocnin.
Literatura
Vytvořující funkce OOOtO
(Formální) mocninné řady oooooo
Operace s vytvořujícími funkcemi ooooo
Využitím operací s polynomy lze velmi snadno odvodit také některé kombinatorické vztahy, které známe již z dřívějška. Využijeme přitom binomickou větu.
Literatura
Vytvořující funkce OOOtO
(Formální) mocninné řady oooooo
Operace s vytvořujícími funkcemi ooooo
Využitím operací s polynomy lze velmi snadno odvodit také některé kombinatorické vztahy, které známe již z dřívějška. Využijeme přitom binomickou větu.
Věta (binomická)
Pro n G N a r G R platí
£ ("v = a+x)».
k=0 V J
Na pravou stranu se můžeme dívat jako na součin n polynomů, levá je zápisem polynomu vzniklého jejich roznásobením.
Literatura
Vytvořující funkce OOOtO
(Formální) mocninné řady oooooo
Operace s vytvořujícími funkcemi ooooo
Využitím operací s polynomy lze velmi snadno odvodit také některé kombinatorické vztahy, které známe již z dřívějška. Využijeme přitom binomickou větu.
Věta (binomická)
Pro n eN a r eR platí
£ ("v = a+x)»
k=0 V J
Na pravou stranu se můžeme dívat jako na součin n polynomů, levá 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(-i)*ffi = 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í		
	e<; H"_1 /c=0    V 7	
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í		
	e<; H"_1 /c=0    V 7	
Důkaz.
Na obě strany binomické věty se podíváme jako na polynomiální funkce. Derivací levé strany dostaneme n(l +x)n_1, derivací pravé strany (člen po členu) pak J2k=i ^(/c)*^1- Dosazením x = 1 dostaneme tvrzení. □
Vytvořující funkce ooooo
(Formální) mocninné řady oooooo
Operace s vytvořujícími funkcemi OOOOO
Plán prednášky
\ /   .       v   ■ /   / r
Q (Formální) mocninné řady • Přehled mocninných řad
Literatura	Vytvořující funkce	(Formální) mocninné řady	Operace s vytvořujícími funkcemi
	ooooo	•OOOOO	OOOOO
(Formální}	mocninné	řady	
Definice
Buď dána nekonečná posloupnost a = (ao, ai, a2,.. .)■ JeJí vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru
oo
3kxk = a0 + aix + a2x2 H----.
k=0
Literatura
Vytvořující funkce OOOOO
(Formální) mocninné řady •OOOOO
Operace s vytvořujícími funkcemi 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
3kxk = a0 + aix + a2x2 H----.
k=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.
^~^^) c^ o
Literatura
Vytvořující funkce ooooo
(Formální) mocninné řady •OOOOO
Operace s vytvořujícími funkcemi 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
3kxk = a0 + aix + a2x2 H----.
k=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
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 £ (—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 £ (—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
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 £ (—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 ooooo
(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 /c-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
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 /c-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
Vytvořující funkce ooooo
(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 /c-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
Vytvořující funkce ooooo
(Formální) mocninné řady OOO0OO
Operace s vytvořujícími funkcemi OOOOO
Dosazování do mocninných rad
Následující větu znáte z matematické analýzy z loňského semestru:
Věta
Buď (ao, ai, a2,...) posloupnost reálných čísel. Platí-li pro nějaké R £ IR, že pro všechna k ^> 0 je \a^\ < Rk, pak rada
a(X) = ^2 a*x* k>0
konverguje pro každé x £ (—^, j^). Součet této řady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a(x).
Literatura
Vytvořující funkce ooooo
(Formální) mocninné řady OOO0OO
Operace s vytvořujícími funkcemi OOOOO
Dosazování do mocninných rad
Následující větu znáte z matematické analýzy z loňského semestru
Buď (ao, ai, a2,...) posloupnost reálných čísel. Platí-li pro nějaké R £ IR, že pro všechna k ^> 0 je \ak\ < Rk, pak rada
a(X) = ^2 a*x* k>0
konverguje pro každé x £ (—^, j^). 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í
aW(0)
3k =
k\
Literatura
Vytvořující funkce ooooo
(Formální) mocninné řady OOOO0O
Operace s vytvořujícími funkcemi OOOOO
Přehled mocninných řad
n
1 -x 1
1 -x
E
=   > X
e =
k>0
E
k>l
E
k>0
k\
sin x =
E(-d
X
2/c+l
/c>0
(2/c + l)!
cosx =
E(-d
X
2/c
/c>0
(2/c)!'
/c>0
Literatura
Vytvořující funkce ooooo
(Formální) mocninné řady 00000«
Operace s vytvořujícími funkcemi OOOOO
Poznámka
• Poslední vzorec
■
(l + x)' = £
X'
k>0
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
Literatura Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcemi
OOOOO 00000« ooooo
• Poslední vzorec
(l + x)' = £
X
k>0
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 (0j = 1. 9 Pro íigNz uvedeného vztahu snadno dostaneme
(l-x)
—=y
k>0
k + n-1 n-1
>0 Q,o
Literatura
Vytvořující funkce OOOOO
(Formální) mocninné řady oooooo
Operace s vytvořujícími funkcemi OOOOO
Plán prednášky
• Přehled mocninných řad
Operace s vytvořujícími funkcemi
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:
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í (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
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í (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
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í (a; + b i) 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
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í (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.
Literatura	Vytvořující funkce	(Formální) mocninné řady	Operace s vytvořujícími funkcemi
	ooooo	oooooo	otooo
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
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:
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, ^3,...), 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
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:
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, ^3,...), 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	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
Y^a(x) je v.f.p. (a0, a0 + aÍ5 a0 + a1 + a2,...)
□
=
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
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
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
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
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
11
-In- je v.f.p. harmonických čísel H{
1 — x    1 — x
Příklad
Protože       = J2n>QXn, dostáváme konvoluci posloupnosti (1,1,...) se sebou vztahy
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   v součinu (l+x + x2 + - • -+x30)(l + x + x2 + - • -+x40)(l + x + x2 + - • - + x50).
Literatura Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcemi
ooooo oooooo ooot>o
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 koeficientem u x70 je zřejmě
(70+2) _ (70+2-31) _ (70+2-41) _ (70+2-51) = 1Q6L
Literatura
Vytvořující funkce ooooo
(Formální) mocninné řady oooooo
Operace s vytvořujícími funkcemi oooo*
r Příklad_		J
Dokažte, že	n	
	Y,Hk = (n + l)(Hn+1-l).	
	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
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	Vytvořující funkce	(Formální) mocninné řady	Operace s vytvořujícími funkcemi
	OOOOO	oooooo	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
1—x      1—x 1—x
n
[*1(TÍFlniÍ? = e(" + 1-/0i'
k=l
odkud již snadnou úpravou dostaneme požadované