Vytvořující funkce ooooooooo Matematika III - 11. přednáška Toky v sítích, párování Michal Bulant Masarykova univerzita Fakulta informatiky 9. 12. 2009 □ S Q Toky v sítích Q Problém maximálního toku v síti Q Další aplikace • Bipartitní párování • Stromové datové struktury a prefixové kódy Q Vytvořující funkce Q Operace s vytvořujícími funkcemi • Přehled mocninných řad ooooooooooooo Vytvořující funkce ooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU n S - = -E -00*0 • Martin Panák, Jan Slovák, Drsná matematika, e-text. a Předmětové záložky v IS MU 9 Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. • Petr Hliněný, Teorie grafů, studijní materiály, http://www.fi.muni.cz/~-Qhlineny/Vyuka/GT/ • Martin Panák, Jan Slovák, Drsná matematika, e-text. a Předmětové záložky v IS MU 9 Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. • Petr Hliněný, Teorie grafů, studijní materiály, http://www.fi.muni.cz/~-Qhlineny/Vyuka/GT/ • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest a Clifford Stein , Introduction to Algorithms, MIT Press, 2001. H. S. Wilf, Generatingfunctionology, Academic Press, druhé vydání, 1994 , (rovněž http://www.math.upenn.edu/~wilf/DownldGF.html) • Martin Panák, Jan Slovák, Drsná matematika, e-text. a Předmětové záložky v IS MU 9 Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. • Petr Hliněný, Teorie grafů, studijní materiály, http://www.fi.muni.cz/~-Qhlineny/Vyuka/GT/ • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest a Clifford Stein , Introduction to Algorithms, MIT Press, 2001. H. S. Wilf, Generatingfunctionology, Academic Press, druhé vydání, 1994 , (rovněž http://www.math.upenn.edu/~wilf/DownldGF.html) • R. Graham, D. Knuth, 0. Patashnik, Concrete Mathematics, druhé vydání, Addison-Wesley, 1994. Q Toky v sítích Q Problém maximálního toku v síti • Bipartitni párováni • Stromové datové struktury a prefixové kódy Q Vytvořující funkce Q Operace s vytvořujícími funkcemi • Přehled mocninných řad ooooooooooooo Vytvořující funkce ooooooooo Další významná skupina aplikací jazyka teorie grafů se týká přesunu nějakého měřitelného materiálu v pevně zadané síti. Vrcholy v orientovaném grafu představují body, mezi kterými lze podél hran přenášet předem známá množství, která jsou zadána formou ohodnocení hran. Některé vybrané vrcholy představují zdroj sítě, jiné výstup ze sítě. Podle analogie potrubní sítě pro přenos kapaliny říkáme výstupním vrcholům stok sítě). Síť je tedy pro nás orientovaný graf s ohodnocenými hranami a vybranými vrcholy, kterým říkáme zdroje a stoky. □ s ooooooooooooo Vytvořující funkce ooooooooo Je zřejmé, že se můžeme bez újmy na obecnosti omezit na orientované grafy s jedním zdrojem a jedním stokem. V obecném případě totiž vždy můžeme přidat jeden stok a jeden zdroj navíc a spojit je vhodně orientovanými hranami se všemi zadanými zdroji a stoky tak, že ohodnocení přidaných hran bude zároveň zadávat maximální kapacity jednotlivých zdrojů a stoků. Situace je naznačena na obrázku, kde černými vrcholy nalevo jsou zobrazeny všechny zadané zdroje, zatímco černé vrcholy napravo jsou všechny zadané stoky. Nalevo je jeden přidaný (virtuální) zdroj jako bílý vrchol a napravo jeden stok. Označení hran není v obrázku uvedeno. □ s ooooooooooooo Vytvořující fun ooooooooo Definice Síť (flow network)]e orientovaný graf G = (V, E) s vybraným jedním vrcholem z nazvaným zdroj a jiným vybraným vrcholem s nazvaným stok, spolu s nezáporným ohodnocením hran w : E —> RÍ~, nazývaným kapacita hran. ooooooooooooo Vytvořující fun ooooooooo Definice Síť (flow network)]e orientovaný graf G = (V, E) s vybraným jedním vrcholem z nazvaným zdroj a jiným vybraným vrcholem s nazvaným stok, spolu s nezáporným ohodnocením hran w ', nazývaným kapacita hran. Tokem v síti S = (V, E,z,s, w) rozumíme ohodnocení hran f : E —> R takové, že součet hodnot u vstupních hran u každého vrcholu v kromě zdroje a stoku je stejný jako součet u výstupních hran z téhož vrcholu (někdy nazýváno Kirchhofíův zákon), tj. v^z,s => y, f^= E f(e) eelN(v) eeOUT(v) a tok splňuje kapacitní omezení f (e) < w(e). ooooooooooooo Vytvořující fun ooooooooo Definice Síť (flow network)]e orientovaný graf G = (V, E) s vybraným jedním vrcholem z nazvaným zdroj a jiným vybraným vrcholem s nazvaným stok, spolu s nezáporným ohodnocením hran w ', nazývaným kapacita hran. Tokem v síti S = (V, E,z,s, w) rozumíme ohodnocení hran f : E —> R takové, že součet hodnot u vstupních hran u každého vrcholu v kromě zdroje a stoku je stejný jako součet u výstupních hran z téhož vrcholu (někdy nazýváno Kirchhofíův zákon), tj. v^z,s => y, f^= E f(e) eelN(v) eeOUT(v) a tok splňuje kapacitní omezení f (e) < w(e). Velikost toku f je dána celkovou balancí hodnot u zdroje \f\= E f(e)- E f(e)- eeOUT(z) e€/A/(z) ooooooooooooo Vytvořující funkce ooooooooo Z definice je zřejmé, že velikost toku můžeme stejně dobře vypočíst jako hodnotu \f\= E f(e)- E f(e)- eelN(s) eeOUT(s) □ g - = ooooooooooooo Vytvořující funkce ooooooooo Z definice je zřejmé, že velikost toku můžeme stejně dobře vypočíst jako hodnotu \f\= E f(e)- E f(e)- eelN(s) eeOUT(s) Na obrázku máme nakreslenu jednoduchou síť se zvýrazněným bílým zdrojem a černým stokem. Součtem maximálních kapacit hran vstupujících do stoku vidíme, že maximální možný tok v této síti je 5. □ g - = Q Toky v sítích Q Problém maximálního toku v síti • Bipartitni párováni • Stromové datové struktury a prefixové kódy Q Vytvořující funkce Q Operace s vytvořujícími funkcemi • Přehled mocninných řad •oooooooooooo Vytvořující funkce ooooooooo Naší úlohou bude pro zadanou síť na grafu G určit maximální možný tok. Jde vlastně o speciální případ úlohy lineárního (celočíselného) programování, kde neznámými jsou toky na hranách a omezení plynou z podmínek na tok. Ukáže se, že pro řešení této úlohy existují jednoduché a přitom rychlé algoritmy. □ s •oooooooooooo Vytvořující funkce ooooooooo Naší úlohou bude pro zadanou síť na grafu G určit maximální možný tok. Jde vlastně o speciální případ úlohy lineárního (celočíselného) programování, kde neznámými jsou toky na hranách a omezení plynou z podmínek na tok. Ukáže se, že pro řešení této úlohy existují jednoduché a přitom rychlé algoritmy. Definice Řezem v síti S = (V, E,z,s, w) rozumíme takovou množinu hran C C E, že po jejím odebrání nebude v grafu G = (V, E\C) žádná (orientovaná) cesta z z do s. Číslo Kl = 5>(e) eec nazýváme kapacita (velikost) řezu C. □ s o«ooooooooooo Vytvořující funkce ooooooooo Evidentně platí, že nikdy nemůžeme najít větší tok, než je kapacita kteréhokoliv z řezů. Na dalším obrázku máme zobrazen tok sítí s hodnotou 5 a čárkovanými lomenými čarami jsou naznačeny řezy o hodnotách 12, 8 a 5. Poznámka Tok a kapacitu hran v síti obvykle zapisujeme v obrázku ve tvaru f/c, kde f je hodnota toku na dané hraně a c její kapacita. □ s oo»oooooooooo Vytvořující funkce ooooooooo Sestavíme algoritmus, který pomocí postupných konstrukcí vhodných cest najde řez s minimální možnou hodnotou a zároveň najde tok, který tuto hodnotu realizuje. Tím dokážeme následující větu: Maximální velikost toku v dané síti S minimální kapacitě řezu v této síti. (V, E, z, s, w) je rovna □ s ooo«ooooooooo Vytvořující funkce ooooooooo Myšlenka algoritmu - prohledáváme cesty mezi uzly grafu a snažíme se je nasytit co největším tokem. Zavedeme si za tímto účelem terminologii. □ s ooo«ooooooooo Vytvořující funkce ooooooooo Myšlenka algoritmu - prohledáváme cesty mezi uzly grafu a snažíme se je nasytit co největším tokem. Zavedeme si za tímto účelem terminologii. O neorientované cestě v síti S = (V, E,z,s, w) z vrcholu v do vrcholu w řekneme, zeje nenasycená, jestliže pro všechny hrany této cesty orientované ve směru z v áo w platí f(e) < w{é) a f(e) > 0 pro hrany orientované opačně. Za rezervu kapacity hrany e pak označujeme číslo w(e) — f{e) pro případ hrany orientované ve směru z v áo w a číslo f(e) při orientaci opačné. Pro zvolenou cestu bereme za rezervu kapacity minimální rezervu kapacity z jejích hran. □ s 0000*00000000 Vytvořující funkce ooooooooo Ford-Fulkersonův algoritmus (1956) Vstupem je síť S = (V, E,z,s, w) a výstupem maximální možný tok f : E -»■ R. • Inicializace: zadáme f(e) = O pro všechny hrany e G E a najdeme množinu vrcholů Ľ C V, do kterých existuje nenasycená cesta ze zdroje z. □ s 0000*00000000 Vytvořující funkce ooooooooo Ford-Fulkersonův algoritmus (1956) Vstupem je síť S = (V, E,z,s, w) a výstupem maximální možný tok f : E -»■ R. • Inicializace: zadáme f(e) = O pro všechny hrany e G E a najdeme množinu vrcholů Ľ C V, do kterých existuje nenasycená cesta ze zdroje z. • Hlavní cyklus: Dokud s G Ľ opakujeme □ s 0000*00000000 Vytvořující funkce ooooooooo Ford-Fulkersonův algoritmus (1956) Vstupem je síť S = (V, E,z,s, w) a výstupem maximální možný tok f : E -»■ R. • Inicializace: zadáme f(e) = O pro všechny hrany e G E a najdeme množinu vrcholů Ľ C V, do kterých existuje nenasycená cesta ze zdroje z. • Hlavní cyklus: Dokud s G Ľ opakujeme • zvolíme nenasycenou cestu P ze zdroje z do s a zvětšíme tok f u všech hran této cesty o její minimální rezervu □ s 0000*00000000 Vytvořující funkce ooooooooo Ford-Fulkersonův algoritmus (1956) Vstupem je síť S = (V, E,z,s, w) a výstupem maximální možný tok f : E -»■ R. • Inicializace: zadáme f(e) = O pro všechny hrany e G E a najdeme množinu vrcholů Ľ C V, do kterých existuje nenasycená cesta ze zdroje z. • Hlavní cyklus: Dokud s G Ľ opakujeme • zvolíme nenasycenou cestu P ze zdroje z do s a zvětšíme tok f u všech hran této cesty o její minimální rezervu • aktualizujeme li. □ s Vstupem je síť S = (V, E,z,s, w) a výstupem maximální možný tok f : E -»■ R. • Inicializace: zadáme ŕ~(e) = 0 pro všechny hrany e G E a najdeme množinu vrcholů U C V, do kterých existuje nenasycená cesta ze zdroje z. • Hlavní cyklus: Dokud s G Ľ opakujeme • zvolíme nenasycenou cestu P ze zdroje z do s a zvětšíme tok f u všech hran této cesty o její minimální rezervu • aktualizujeme li. • na výstup dáme maximální tok f a minimální řez C tvořený všemi hranami vycházejícími z Ľ a končícími v doplňku V\U. n 3 - = -E -00*0 Jak jsme viděli, velikost každého toku je nejvýše rovna kapacitě kteréhokoliv řezu. Stačí nám tedy ukázat, že v okamžiku zastavení algoritmu jsme vygenerovali řez i tok se stejnou hodnotou. Algoritmus se zastaví, jakmile neexistuje nenasycená cesta ze zdroje z do stoku s. To znamená, že U neobsahuje s a pro všechny hrany e z Ľ do zbytku je f(e) = w(e), jinak bychom museli koncový vrchol e přidat k Ľ. Jak jsme viděli, velikost každého toku je nejvýše rovna kapacitě kteréhokoliv řezu. Stačí nám tedy ukázat, že v okamžiku zastavení algoritmu jsme vygenerovali řez i tok se stejnou hodnotou. Algoritmus se zastaví, jakmile neexistuje nenasycená cesta ze zdroje z do stoku s. To znamená, že U neobsahuje s a pro všechny hrany e z Ľ do zbytku je f(e) = w(e), jinak bychom museli koncový vrchol e přidat k Ľ. Zároveň ze stejného důvodu všechny hrany e, které začínají v komplementu V\ U a končí v U musí mít tok f(e) = 0. oooooo«oooooo Vytvořující funkce ooooooooo Pro velikost toku celé sítě jistě platí \f\= E f(e)- E f(e)- hrany z U do V \ U hrany z V \ U do U Tento výraz je ovšem v okamžiku zastavení roven E f(e)= E *"(0 n S - = -E -00*0 ooooooooooooo Exponenciální vytvoř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. sM = J2gn n>0 Poznámka Jméno vychází z toho, že exponenciální funkce ex je (exponenciální) vytvořujícífunkcí 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ší. □ g - = Následující větu znáte z matematické analýzy z loňského semestru: nsn Bucf (a0, 3\, 32 ...) posloupnost reálných čísel. P latí-li pro nějaké Kel, íe pro všechna n > 1 je N < K" , pak řada a(x) = n>0 konverguje pro každé x e (—^, ^). Součet této řady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a(x). Vytvořující funkce ooooooooooooo Dosazování do mocninných řad 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 anx" 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, nebot má a{x) v 0 derivace všech řádů a platí a(")(0) Q Toky v sítích Q Problém maximálního toku v síti • Bipartitni párováni • Stromové datové struktury a prefixové kódy Q Vytvořující funkce Q Operace s vytvořujícími funkcemi • Přehled mocninných řad ooooooooooooo Vytvořující funkce ooooooooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: □ s ooooooooooooo Vytvořující funkce ooooooooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (aj + b;) posloupností člen po členu odpovídá součet a(x) + b{x) příslušných vytvořujících funkcí. □ s ooooooooooooo Vytvořující funkce ooooooooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (aj + b;) 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. □ s ooooooooooooo Vytvořující funkce ooooooooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (aj + b;) 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. • Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. □ s ooooooooooooo Vytvořující funkce ooooooooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (aj + b;) 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. • 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 (ao,..., a^-1,0,...) a poté podělíme vytvořující funkci xk. □ s ooooooooooooo Vytvořující funkce ooooooooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (aj + b;) 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. • 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 (ao,..., a^-1,0,...) a poté podělíme vytvořující funkci xk. 9 Substitucí polynomu f(x) s nulovým absolutním členem za x vytvoříme specifické kombinace členů původní posloupnosti. Jednoduše je vyjádříme pro f(x) = ax, což odpovídá vynásobení k-tého členu posloupnosti skalárem ak. Dosazení f(x) = x" nám do posloupnosti mezi každé dva členy vloží 1 nul. □ S ooooooooooooo Vytvořující fun ooooooooo Příklad Viděli jsme, že 1/(1 — x) je vytvořující funkcí posloupnosti ze samých jedniček. Substitucí 2x za x tak dostaneme tvrzení, že 1/(1 — 2x) je vytvořující funkcí posloupnosti (1, 2,4, 8,...). □ s ooooooooooooo Vytvořující fun ooooooooo Příklad Viděli jsme, že 1/(1 — x) je vytvořující funkcí posloupnosti ze samých jedniček. Substitucí 2x za x tak dostaneme tvrzení, že 1/(1 — 2x) je vytvořující funkcí posloupnosti (1, 2,4, 8,...). S využitím substituce —x za x dostaneme, že je-li a(x) vytvořující pro (ao, ai,...), je (a(x) + a(—x))/2 vytvořující pro a0,0,a2,0,...). □ S ooooooooooooo Vytvořující fun ooooooooo Příklad Viděli jsme, že 1/(1 — x) je vytvořující funkcí posloupnosti ze samých jedniček. Substitucí 2x za x tak dostaneme tvrzení, že 1/(1 — 2x) je vytvořující funkcí posloupnosti (1, 2,4, 8,...). S využitím substituce —x za x dostaneme, že je-li a(x) vytvořující pro (ao, ai,...), je (a(x) + a(—x))/2 vytvořující pro a0,0,a2,0,...). Příklad Určete vytvořující funkci posloupnosti (1,1,2,2,4,4,8,8,...). □ s ooooooooooooo Vytvořující fun ooooooooo Příklad Viděli jsme, že 1/(1 — x) je vytvořující funkcí posloupnosti ze samých jedniček. Substitucí 2x za x tak dostaneme tvrzení, že 1/(1 — 2x) je vytvořující funkcí posloupnosti (1, 2,4, 8,...). S využitím substituce —x za x dostaneme, že je-li a(x) vytvořující pro (ao, ai,...), je (a(x) + a(—x))/2 vytvořující pro a0,0,a2,0,...). Příklad Určete vytvořující funkci posloupnosti (1,1,2,2,4,4,8,8,...). Podle předchozího příkladu je 1/(1 — 2x) vytvořující funkcí posloupnosti (1,2,4,8,...). Substitucí x2 za x dostaneme vytvořující funkci 1/(1 — 2x2) pro (1, 0,2,0,4,0,...) a celkem pak je (1 + x)/(l — 2x2) hledanou vytvořující funkcí. ooooooooooooo Vytvořující funkce ooooooooo Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: • Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, 2a2,3a3,...), člen s indexem k je (k + l)a/c+i (tj. mocninnou řadu derivujeme člen po členu). □ s ooooooooooooo Vytvořující funkce ooooooooo Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: • Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, 2a2,3a3,...), člen s indexem k je (k + l)a/c+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce Jq a(t)dt vytvořuje posloupnost (0, ao, \a\, 132, ^33,...), pro k > 1 je člen s indexem k je \sk-\ (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce 3(x)). □ s ooooooooooooo Vytvořující funkce ooooooooo Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: • Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, 2a2,3a3,...), člen s indexem k je (k + l)a/c+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce J0xa(ř)dř vytvořuje posloupnost (0, ao, \a\, 132, ^33,...), pro k > 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 Ck Y, aibJ- i+j=k (tj. členy v součinu až po c k jsou stejné jako v součinu (a0 + a\x + 32x2 H--------h akxk)(bQ + b\x + b^x2 -\------bkxk). Posloupnost c bývá také nazývána konvolucí posloupností a, b. n i^D — = "= ^)0,O Příklad Jaká je vytvořující funkce pro posloupnost druhých mocnin (12,22,32,...)? Řešení 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? Příklad Jaká je vytvořující funkce pro posloupnost druhých mocnin (12,22,32,...)? Řešení 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 (k + 2)(/c + 1). Snadno vidíme, že výslednou vytvořující funkcí je tedy a(x) (l-x)3 (1-x) 2- ooooooooooooo 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 + • • • ){bo + bix + Ó2X2 + = bo + (bo + bx)x + {b0 + b1 + k)*2 + • • • ) 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\, bi, ■ ■ ■ )■ □ s Přehled mocninných řad: 1 In 1-x 1 smx cosx (l+x)r Vytvořující funkce ooooooooo E*" n>0 E n>l E x" n n>0 D-1)" „2n+l n>0 (2n + l)! ,2n S(-1,:W' □ s - = ■€. -o<\(y ooooooooooooo Vytvořující funkce ooooooooo Poznámka • Posled ní vzorec (1 + xy = k>0 ;> k je tzv. binom zobecněná binomická věta, kde cký koeficient definován vztahem pro r G M je (0- r(r - -l)(r -2). k\ ■■(r -k + ľ) Speciá lně klademe (o) = 1. ooooooooooooo Vytvořující funkce ooooooooo Poznámka • Posled ní vzorec (1 + xy = k>0 ;> k je tzv. zobecněná binomická věta, kde pro r G M je binom cký koeficient def nová n vztahem fr\ r{r- -l)(r -2). ■■(r -k + ľ) \k)- k\ Speciá lně klademe (£) = 1. • Pro n G N z uvedeného vztahu snad no dostaneme 1 -("-^t n-1, K ..+( 'xvy-- (1-* )"-{n-l) + { Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fo = 0, Fi = 1, F„_|_2 = Fn+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. Vytvořující funkce ooooooooooooo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fo = 0, Fi = 1, F„_|_2 = Fn+i + F„. 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. Poznámka (Nejen) pro manipulace se sumami používají autoři Concrete mathematics velmi vhodné označení [logický predikát} -výraz je roven 1 v případě splnění predikátu, jinak 0. Např. [n = l],[2|n] a pod. Vytvořující funkce ooooooooooooo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fo = 0, Fi = 1, F„_|_2 = Fn+i + F„. 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. Poznámka (Nejen) pro manipulace se sumami používají autoři Concrete mathematics velmi vhodné označení [logický predikát} - výraz je roven 1 v případě splnění predikátu, jinak 0. Např. [n = l],[2|n] a pod. Pro vyjádření koeficientu u x" ve vytvořující funkci F(x) se pak často používá zápis [x"]F(x). Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Pak zřejmě F(x) - xF(x) - x2F(x) = x, a tedy Našim cílem je tedy odvodit vztah pro n-tý člen posloupnosti odpovídající vytvořující funkci F(x) = 1_x_ 2. Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Pak zřejmě F(x) - xF(x) - x2F(x) = x, a tedy Našim cílem je tedy odvodit vztah pro n-tý člen posloupnosti odpovídající vytvořující funkci F(x) = 1_*_x2 ■ Využijeme k tomu rozklad na parciální zlomky a dostaneme x _ A B 1 — X — X2 X — X\ 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. □ g - = ^ -00*0 Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Pak zřejmě F(x) - xF(x) - x2F(x) = x, a tedy Našim cílem je tedy odvodit vztah pro n-tý člen posloupnosti odpovídající vytvořující funkci F(x) = 1_*_x2 ■ Využijeme k tomu rozklad na parciální zlomky a dostaneme x _ A B 1 — X — X2 X — X\ 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 — x 1 — Aix 1 — A2X a ooooooooooooo Vytvořující funkce ooooooooo Příklad - závěr S využitím počátečních podmínek dostáváme 1 (1 + VšY /l-\/5N V5 Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. □ g - = ooooooooooooo Vytvořující funkce ooooooooo Příklad - závěr S využitím počátečních podmínek dostáváme 1 (1 + VšY /l-\/5N V5 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 1 (\+y/Š\n V5{ 2 ) ■ □ s ooooooooooooo Vytvořující funkce ooooooooo Příklad - závěr S využitím počátečních podmínek dostáváme 1 (1 + VšY /l-\/5N V5 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 ■\{l±fi)n- Navíc je vidět, že lim,^«, 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ě. □ s ooooooooooooo Vytvořující funkce ooooooooo Příklad - závěr S využitím počátečních podmínek dostáváme 1 (1 + VšY /l-\/5N V5 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 ■\{l±fi)n- Navíc je vidět, že lim,^«, 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 k-tého stupně s konstatními koeficienty. Má-li charakteristická rovnice jednoduché kořeny, je situace jednodušší- viz dříve. □ s