Vytvořující fun ooooooooo Matematika III - 12. přednáška Vytvořující funkce Michal Bulant Masarykova univerzita Fakulta informatiky 4. 12. 2007 Q Vytvořující funkce Q Operace s vytvořujícími funkcemi • Přehled mocninných řad Q Aplikace vytvořujících funkcí • Martin Panák, Jan Slovák, Drsná matematika, e-text. 9 Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. H. S. Wilf, Generatingfunctionology, Academie Press, druhé vydání, 1994 , (rovněž http://www.math.upenn.edu/~wilf/DownldGF.html) • R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, druhé vydání, Addison-Wesley, 1994. ajemi Příklad Máme v peněžence 4 korunové mince, 5 dvou kor u nový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 /', jak taková, že i + j + k = 22 a zároveň / G {0,1, 2, 3,4}, j G {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+xl5) 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. Vytvořující fun o«ooooooo 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 G N počet řešení (i, j) rovnice / +j = r splňujících / G I, j G J roven koeficientu u xr v polynomu (S/e/x')(Sjejx'/)- 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 a\, 32, 35, 3io, 320 a 350 taková, že a-, je násobkem / pro všechna / G {1,2,5,10,20,50} a zároveň 3i + 32 + 35 + 3io + 320 + ^50 = 100. Podobně jako výše je vidět, že požadovaný počet lze získat jako koeficient u x100 v (l+x + x2 + ...)(l + x2+x4 + ...)(l + x5+x10 + ...) (1 +x10 +x20 + . .)(1 + x20 +x40 + )(1 +x50 +x100 + ) Vytvořující fun oo«oooooo Podobným způsobem můžeme znovu velmi snadno odvodit 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 M platí ■+C>" Na levou stranu se můžeme dívat jako na součin n polynomů, pravá 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 Vytvořující fun ooo«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 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 Ylk=i ^(/D*^-1- Dosazením x = 1 dostaneme tvrzení. D Vytvořující funkce oooo»oooo (Formáh Aplikace vytvořujících funkc oooooo mé řaď Definice Buď dána nekonečná posloupnost a = (ao, ai, 32,.. .)■ JeJ' vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru £ 3/x' = a0 + 3ix + a2x2 + 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. Vytvořující fun ooooo«ooo 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 e (0,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 Vytvořující fun oooooo»oo 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 asymptotické chování. Vytvořující funkce ooooooo«o /ořující funkce Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciální varianty. g(x) = J2gn n>0 Poznámka Jméno vychází z toho, že exponenciální funkce ex je (exponenciální) vytvořuj ícífu n kcí pro základní posloupnost (1,1,1,1,...). Později ukážeme některé příklady (např. Cayleyho větu), kdy je použití exponenciálních vytvořujících funkcí výhodnější. Vytvořující funkce oooooooo» Dosazov; icninný Následující větu znáte z matematické analýzy z loňského semestru: Buď(ao, 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 a"x" 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, neboť má a{x) v 0 derivace všech řádů a platí _ a(")(0) a n — 1 • Vytvořující fun ooooooooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (a, + £>,) 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. • 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 (a 1 je člen s indexem k je \ak-\ (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 i+j=k (tj. členy v součinu až po Ck jsou stejné jako v součinu (30 + 3ix + 32x2 H--------h akxk){bo + faix + b2x2 -\------bkxk). Posloupnost c bývá také nazývána konvolucí posloupností 3, b. Vytvořující funkce ooooooooo Příklad Jaká je vytvořující funkce pro posloupnost druhých mocnin (12,22,32,...)? Lze očekávat, že bude snazší bude nejprve určit vytvořující funkce pro (1, 2,3,...). Podle předchozího víme, že 1/(1 — x) vytvoří posloupnost samých jedniček a její derivace 1/(1 — x)2 pak posloupnost (1,2,3,...). Jak ale zjistit funkci odpovídající druhým mocninám? Druhou derivací dostaneme 2/(1 — x)3, k ní odpovídající posloupnost je (1 x 2,2 x 3, 3 x 4,...), jejíž člen s indexem k je (/c + 2)(/c + 1). Snadno vidíme, že výslednou vytvořující funkcí je tedy a(x) (l-x)3 (1-x) 2- Vytvořující fun ooooooooo Příklad Uvažme jeden speciální případ násobení vytvořujících funkcí a(x) a b(x), je-li a(x) = 1/(1 — x). Pak konvolucí příslušných posloupností je posloupnost, jejíž vytvořující funkce je dána mocninnou řadou (1 + x + x2 + x3 + • • • ){b0 + bix + b2x2 + = bo + (fao + bx)x + {bo + b1 + ^x2 + • • • ) Vyjádřeno slovy, vynásobením funkce b{x) funkcí 1/(1 — x) dostaneme vytvořující funkci posloupnosti částečných součtů původní posloupnosti (bo, b\, í>2, • • • )■ Vytvořující fun ooooooooo Přehled mocninných řad: 1 In 1-x 1 smx cosx (l+x)' E*" n>0 E ri>\ E x" n n>0 B-1)" „2n+l n>0 B-1)" (2n + l)! ,2n n>0 (2n)!' Eír xÉ /c>0 Vytvořující fun ooooooooo Poznámka • Posled ní vzorec (1 + x)' = k>0 ;> k je tzv. zobecněná binomická věta, kde pro r G M je binomický koeficient def nová n vztahem fr\ r{r- -l)(r -2). ■■(r -k + 1) W" k\ Speciá ně klademe {£) = 1. • Pro n G N z uvedeného i/ztahu snad no dostaneme 1 -(n-r\ + ( n-l/ K ■■+( 'n + k-ľ\ < + •••• (1-x )"-{n-l) + { Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fo = 0, Fi = 1, F„_|_2 = /-n+i + Fn. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice. Našim cílem bude (opět) najít formuli pro výpočet n-tého členu posloupnosti. Uvažme vytvořující funkci F{x) Fibonacciho posloupnosti. Pak zřejmě F(x) - xF(x) - x2F(x) = x, a tedy x Našim cílem je odvodit vztah pro n-tý člen posloupnosti odpovídající vytvořující funkci F(x) = ._*_ 2. Využijeme k tomu rozklad na parciální zlomky a dostaneme x _ ^ ß 1 — X — X2 X — Xl X — X2 ' kde xi,X2 jsou kořeny polynomu 1 — x — x2 a A, B vhodné konstanty odvozené z počátečních podmínek. Po substituci Ai = 1/xi, A2 = 1/x2 dostáváme vztah x ab 1 — x — x2 1 — Aix 1 —A2X' odkud snadno pomocí znalostí o vytvořujících funkcích Fn = a ■ X" + b ■ A2- Vytvořující funkce Operace s vytvořujícími funkcemi ooooooooo ooooooo Aplikace vytvořujíc oo»ooo ch funkci Příklad - závěr S využitím počátečních podmínek dostáváme Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Uvážíme-li navíc, že (1 — v/5)/2 ~ —0.618, vidíme, že pro všechna přirozená čísla lze Fn snadno spočítat zaokrouhlením čísla i (Ü^l)« Navíc je vidět, že lim„^oo Fn/Fn+1 = 1/\1 « 0.618, což je poměr známý jako zlatý řez - objevuje se již od antiky v architektuře, výtvarném umění i hudbě. Analogický postup je možné použít při řešení obecných lineárních diferenčních rovnic /c-tého stupně s konstatními koeficienty. Má-li charakteristická rovnice jednoduché kořeny, je situace jednodušší -viz dříve. Vytvořující funkce ooooooooo Pěstoval stromy S využitím vytvořujících funkcí určíme formuli pro počet bn pěstovaných binárních stromů na n vrcholech. Prozkoumáním případů pro malá n vidíme, že b0 = 1, bi = 1, b2 = 2, b3 = 5. Snadno nahlédneme, že pro n > 1 vyhovuje bn rekurentní formuli bn = b0bn-i + b\bn-2 H---------h bn-ibo. Nechť b{x) je odpovídající vytvořující funkce. Pravá strana uvedené rekurence je vlastně koeficientem u xn_1 v součinu b{x) ■ b{x), tj. členem u x" v xŕ>(x)2. Je tedy xŕ>(x)2 vytvořující po tutéž posloupnost jako b{x) s výjimkou prvního členu. Tedy b{x) = 1 +xr>(x)2, z čehož dostaneme (pro x pevně zvolené) b(x) 1 ± VI - 4x 2x ' Vytvořující funkce ooooooooo Pěstoval Ve vzorci stromy b(x) 1 ± VI - 4x 2^ ale znaménko + nepřichází v úvahu, protože pro x —> 0+ má limil oo, zatímco vytvořující funkce pro naši posloupnost musí mít v 0 hodnotu bo = 1. Pomocí zobecněné binomické věty pak získáme rozvoj (l-4x) 1/2 oo /U fc=o v 7 a po vydělení 1 — i/l — 4x výrazem 2x (tj. posunem vlevo a vydělením 2) dostaneme Ön 2V ; Vn + 1 2n n + l\ n což jsou známá (a významná) Catalanova čísla 4 Kromě toho, že Catalanova čísla vyjadřují počet binárních pěstovaných stromů, vystupují rovněž jako: • počet slov délky 2n obsahujících n znaků X a V takových, že žádný prefix slova neobsahuje více Y než X • podobně fronty u pokladny (5koruny a lOkoruny) tak, aby nezásobená pokladna mohla vždy vrátit (zároveň dostaneme pravděpodobnost, že náhodná fronta „projde") • počet korektně ozávorkovaných výrazů složených z levých a pravých závorek • počet monotónních cest z [0,0] do [n, n] podél stran jednotkových čtverců, které nepřekročí diagonálu • počet různých triangulací konvexního (n + 2)-úhelníku.