Literatura Vytvořující funkce ooooo (Formální) mocninné řady oooooo Operace s vytvořujícími funkcemi OOOOO Diskrétní matematika - 10. týden Vytvořující funkce Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2020 Literatura Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcemi ooooo oooooo 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 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 Programming. • Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994. 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. 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 (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 / 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é? Ř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 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. Věta (binomická) Pro n 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). 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 oooo«o 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 (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 Literatura Vytvořující funkce (Formální) mocninné řady Operace s vytvořujícími funkcemi ooooo 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. 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(ř) 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)- 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 (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 1 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 In T 1—x 1—X 1 Odtud k=i odkud již snadnou úpravou dostaneme požadované.