Diskrétní matematika - 10. týden Vytvořující funkce ikcemi Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2020 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 zdroje ^^^^^^H^^^^^^^|^^^^^^| • 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 Doporučené zdroje 9 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 ooooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi OOOOO Plán přednášky Q Vytvořující funkce ^ I I I I I W>l I I I I J III \^ I I I I I I I I ťl J • Přehled mocninných řad 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í. 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 •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 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ň / G {0,1, 2, 3,4}, j G {0, 2,4, 6,8,10}, k G {0,5,10,15}. * i1 Uvažme součin polynomů (třeba nad reálnými čísly) £ (x0+xl+x2^x3+x4)(^ X1 X* Xk . . Mělo by být zřejmé, že hledaný počet řešení je díky X*-XJ.X (Cauchyovskému) způsobu násobení polynomů právě koeficient VV . ^ u x22 ve výsledném polynomu. X1^/"* 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 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 e {0,1,2, 3,4}, j e {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 +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 9*5 + 4*9 + 4*1 < □ ► > < i ► < i ► i* Literatura Vytvořující funkce O0OOO (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 O0OOO (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 O0OOO 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č? Literatura Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcemi O0OOO 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 350 taková, že a/je násobkem / pro všechna / e {1,2,5,10,20,50} a zároveň ai + a2 + a5 + a10 + a2o + a50 = 100. Literatura Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcemi O0OOO 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 350 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 (l+x + x2H-----hx5)(l+x + x2H-----hx10)(l+x + x2H-----hx15). Když máme předepsaný nějaký počet jako nejmenší možný, prostě začneme až od příslušných mocnin. 3- c 6 c 6 ó 0 □ ťnP - = 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 (Formální) mocninné řady Operace s vytvořujícími funkcemi OOO0O oooooo 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 e R platí £(fK = (i+*r. 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í k=0 w * ^-4 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é vzprce ĽJU(-i)*ffi = o. ► < = *■ 4 = ► 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. ^f2)^ ^ f^-tX.}^ J r i Důsledek Platí n / \ /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í k=0 w Důkaz. Na obě strany binomické věty se podíváme jako na polynomiální funkce. Derivací levé strany dostaneme r?(l + x)n_1, derivací pravé strany (člen po členu) pak J2k=i ^(I!)*^-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 přednášky \ / . v ■ / / r Q (Formální) mocninné řady • Přehled mocninných řad v y w v □ 3 ► < ► 4 = >0 Q,o Literatura Vytvořující funkce ooooo (Formální) mocninné řady •OOOOO Operace s vytvořujícími funkcemi OOOOO (Formální) mocninné rady 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 + k=0 ^r *ríu.- p«sä- f»r^«v.W " 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 ooo«oo Operace s vytvořujícími funkcemi OOOOO Dosazování do mocninných řad 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 e K, že pro všechna k ^> 0 je laJ < Rk, pak rada a(X) = ^2 akx' k>0 f.*t.rm Ur konverguje pro každéxg(-^). 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ůaplatí lW(o) pA*z2$r ak = Literatura Vytvořující funkce ooooo (Formální) mocninné řady OOOO0O Operace s vytvořujícími funkcemi OOOOO Přehled mocninných řad Literatura Vytvořující funkce ooooo (Formální) mocninné řady OOOOO* 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 R je binomický koeficient definován vztahem r(r-l)(r-2)..-(r-/c + l) 4 ít^j f<.-5 Speciálně klademe u) = 1 Literatura Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcemi ooooo ooooo* ooooo • Poslední vzorec (i+*>' = E(> k k>0 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 ^ (l-x)n n-1 Q v ) k>o v Literatura Vytvořující funkce OOOOO (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi OOOOO Plán přednášky í Fnrms ni 1 mnrninnp ř^Hv ^ i vy i i i i 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 (Formální) mocninné řady Operace s vytvořujícími 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: o Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, 2a2, 3a3,...), člen s indexem k je (/c + 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)). • Násobení řad: součin a(x)b(x) je vytvořující funkcí posloupnosti (co, ci, c2,...), kde 1 . / tj. členy v součinu až po q jsou stejné jako v/součinu (ao + aix + a2x2 H-----hbix + fox2 +;j_--bkxk_) Posloupnost (cn) bývá také nazývána konvolucí posloupností 1/ {3n),(b„) >0 Q,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 t3^a(x) je v.f.p. (a0, a0 + ai, a0 + a\ + a2,.. .)■ 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_ i-xa(x) Je v-f-P- (ao, 30 + ai, a0 + ai + a2,.. .)■ Odtud např. dostáváme, že 11 -In- je v.f.p. harmonických čísel Hn- 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 = X]n>ox"' dostáváme konvoluci posloupnosti (1,1,...) se sebou vztahy ----ŕ 7 i " = 5> + l)x", n>0 (l-x): 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 + ai, a0 + a\ + a2,...) Odtud např. dostáváme, že -In- 1 -x 1 -x je v.f.p. harmonických čísel Hn Příklad = ^2n>0xn, dostáváme konvoluci posloupnosti • sebou vzta hv k 01 (Hj-ít**^ * " * l £<"+i)*". ,(1_x)3 n+ 2' x r? 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í :-). ) 9 0,0 Literatura Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcemi OOOOO OOOOOO OOO0O 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 (Formální) mocninné řady Operace s vytvořujícími funkcemi OOOOO OOOOOO OOO0O 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 90,0 Literatura Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcemi OOOOO 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 (1 _ 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 (Formální) mocninné řady Operace s vytvořujícími funkcemi ooooo oooooo 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 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^- # t^- In j-^. I . ŕ l—x l—x l—X m odtud ****** „ i—i«-1 odkud již snadnou úpravou dostaneme požadované. \č