Matematika III - demonstrační cvičení Michal Bulant 16. prosince 2010 1. demonstrační cvičení Příklad 1. Zobrazte v rovině definiční obory funkcí: a) f(x,y) = ln(^ + 2y), b)f(x,y) = Jl-(f + y- 9 4 ^' C) f(X v) - ^ d) f(x,y) = arccos X x+y' 1 Příklad 2. Určete definiční obor funkcí: a) f{x,y,z) = y^ + lnz, b) f(x,y,z) = arccos^==. 2 Příklad 3. Načrtněte vrstevnice funkci: a) f(x,y) = x2 -y2, b) f(x,y) = xy, c) f(x,y) = y/xy. 3 Příklad 4. Rozhodněte, zda je daná posloupnost cauchyovská: a) {-\)n , kde n e N, b) an, kde n G N (v závislosti na hodnotě parametru a G M). 4 Příklad 5. Určete všechny hromadné body množiny: a) Z, b) Q, c) {1,1,2,1,2,3,1,2,3,4,...}, d;{3(l-i) + 2(-l)»;7ieN}. 5 Příklad 6. Určete tečnu křivky dané předpisem f (t) = (2 cos t + cos 3t, sin 2t, t) v bodět = ^. 6 Příklad 7. Na křivce (t,t2,t3) najděte takový bod, že jím procházející tečna je rovnoběžná s rovinou x + 2y + z = 1. 7 Příklad 8. Vypočtěte limity: a;iim(l>yH(1>1)-^, b) lim(a>y)_(o,o) Vf++f+í_ť c) lim(Xjž/)^(0j0) xy2cos±2, d) lim{x^m ej lim(Xjž/)^(0,o) fš^fš, /; lim(Xjž/H(o0j0o)(:r2 + y2)e-{x- ^lim(Xjž/H(00jl)(l + ^)^. 2. demonstrační cvičení Příklad 9. Dokažte, že následující limity neexistují: a) lim(X;ž/)^(0jo) -Jf^p, l-cos(x2+y2) oj lim(Xjž/)^(0j0) {x2+y2)xy ■ 9 Příklad 10. Vypočtěte všechny parciální derivace (i smíšené) funkce f(x,y) = x4 + 10xV-2y6 až do řádu 3 včetně. 10 Příklad 11. Určete směrovou derivaci funkce f(x,y) = aictg(x2+y2) v bodě [—1,1] ve směru vektoru (1,2). n Příklad 12. Vypočtěte parciální derivace 1. řádu funkcí a) f(x,y) = xxy, b) f(x,y) = aictgf=*-. 12 Příklad 13. Určete diferenciál v daném bodě: a) f(x,y) = xy + ^ v bodě [1,1], b) f(x,y) = arcsin^^== v bodě [1,VŠ]. y/ x2+y2 13 3. demonstrační cvičení Příklad 14. Rozhodněte, zda je funkce f(x,y) = ^/\xy diferencovatelná v [0,0]. 14 Příklad 15. Pomočí diferenčiélu približne vypočtete: a) arcsinj^l, b) l, 042,02. 15 Příklad 16. Určete rovnici tečné nadroviny ke grafu funkce v daném bodě: a) f(x,y) = x2 + xy + 2y2, [x0,y0,zo\ = [1,1,4], b) f(x,y) = arctgf, [x0,y0,zo\ = [1, -1,?]. 16 Příklad 17. Určete Taylorův polynom 2. stupně se středem v daném bodě: a) ln y/x2 + 2/2, [x0,y0} = [1,1], b) x*, [x0,yo,zo] = [1,1,1]. 17 Příklad 18. Pomoci Taylorova polynomu 2. stupně přibližně vypočtěte a) sin 29° tg46°, b) ln(x2 + y2 + 1) v bodě [1,1; 1,2]. 18 Příklad 19. Pomocí vrstevnic funkce f(x,y) = \x\ + \y\ určete její největší a nejmenší hodnotu na množině M : (x — l)2 + (y-l)2■ ~R,f(x,y) = x2y+y2x — xy a rozhodněte, které z těchto bodů jsou lokálními extrémy a jakého druhu. 21 Příklad 22. Ukažte, že funkce f(x, y) = ex sin(y) + ey sin(x) definuje předpisem f(x,y) = 1 pro [x,y] £ (O, |) x (O, |) implicitně proměnnou y jako funkci proměnné x. Určete f'{x). 22 Příklad 23. Rozhodněte, zda křivka x3 + y3 — 2xy = O leží v okolí bodu [1,1] nad (nebo pod) svojí tečnou. 23 Příklad 24. Rozhodněte, zda plocha daná v okolí [1, 0,1] G rovnicí x3 + y3 + z3 — 3rryz — aľ — y — z = 0 Zei/ v k>cřě [1,0,1] nad nebo pod tečnou rovinou. 24 Příklad 25. Najděte lokální extrémy funkce y = y(x) dané implicitně rovnicí ln \J x2 + y2 = arctg K 25 Příklad 26. Určete parametrickou rovnici tečny v bodě [xo,yo, zq] , zq > O ke křivce, jež vznikla jako průsečík kulové plochy K : x2 + y2 + z2 = 4 s válcovou plochou V : x2 + y2 — 2x = O (tzv. Vivianiho křivka^. 26 5. demonstrační cvičení Nechť F = (f, g) : M2 —>■ M2 a předpokládejme, že funkce f, g (tj. složky zobrazení F) mají v bodě [xo,yo] spojité parciální derivace a že Jacobiho matice F'(xo,yo) = (•^x°'ž/0| ^x°^ \ zobrazení F v bodě [xo,yo] je regulární, tj. det F'(xo, yo) ^ 0 (det F'(xo, yo) se nazývá ja-cobián zobrazení F v bodě [xo,yo]). Pak existuje okolí bodu [xo,yo], v němž je zobrazení F prosté, tudíž k němu existuje inverzní zobrazení F~l v okolí bodu F(xo,yo), a pro Jacobiho matici tohoto inverzního zobrazení v bodě [ito,^o] = F(%o,yo) platí (F~ry(uo,vo) = [F'Kž/o)]"1. Příklad 27. Rozhodněte, zda je zobrazení F = (f, g) : M2 —>■ M2, kfe f (x, y) = \fx2~^y2, g(x, y) = xy, prosté v nějakém okolí bodu [0,1]. V kladném, případě určete Jacobiho matici inverzního zobrazení F~l v bodě F(0,1). 27 Příklad 28. Spočítejte jacobián funkce F, která je transformací dvou proměnných do polárních souřadnic, a příslušné inverzní transformace. 28 Příklad 29. Drát délky l je rozdělen na 3 části. Z jedné části je vytvořen kruh, z druhé čtverec a ze třetí rovnostranný trojúhelník (vědy stočením, resp. složením vytvoríme obvod príslusneho útvaru). Určete delky jednotlivých částí tak, aby celková pločha omezená temito utvary byla maximálni. 29 Příklad 30. Rozhodněte, zda existují maxima a minima funkce f : M2 —>■ K, f(x, y) = x — 2y na křivce dané rovnicíy — x2, — 2x — 1 = 0. Případné extrémy určete. Uvažujte křivku omezenou na interval x £ (0,5). 30 Příklad 31. Pomocí metody Lagrangeových multiplikátorů nalezněte body na průniku ploch z2 = x2 + y2 a z = 1 + x + y, které leží nejblíze počátku. Zdůvodnete, že jde skutecne o minimum. 31 Příklad 32. Zjistěte, zda existuji maxima a minima funkce f(x, y, z) = x + 2y + 3z na elipse z2 = x2 + y2,x — y + z + \ = Q. 32 Příklad 33. Výrobce uvažuje možnost produkce dvou výrobků V\ a V2.Pro jejich výrobu mUže počítat s využitím 180 kg surovin, 240 hodin prace speciálních stroju a náklady jsou pritom omezený castkou 160 tis. Kč. Na zaklade predpokladaných tržeb býl stanoven ocekavaný žisk ža 1 kus výrobku V na 7 tis. Kc a ža 1 kus výrobku V2 na 9 tis. Kč. Z predbežného průžkumu žajmu výplýnulo, že oba výrobký lže prodat v libovolném množství. V mmci prápravý produkce býla stanovena narocnost obou výrobku ž hlediska spotřebý ždrojů na 1 kus: Výrobek spotřeba surovin [kg] spotřeba času [hj náklady [tis. Kč] Vi 3 5 10 v2 5 4 2 Vžhledem k uvedenáým skute cnostem napláanujte váýrobu tak, abý váýrobci přinesla nejvýssá žisk. 33 6. demonstrační cvičení Příklad 34. Vypočtěte jjMxyáxáy, kde M je oblast 1 < x < 4, ^ < y < V%- 34 Příklad 35. Převeďte dvojný integrál JjAf(x,y)áA na dvojnásobný (obě možnosti pořadí integrace) pro množinu A ohraničenou přímkami y = x, y = x — 3, y = 2, y = 4. Ověřte (přímo nebo s využitím SW např. MAW) rovnost výsledku pro konkrétní funkci f (x, y) = y. 35 Příklad 36. Zaměňte pořadí integrace J0 f2* f{x,y) áy áx. 36 Příklad 37. Vypočtěte integrál ^9 9 y sinx áxáy. 37 Příklad 38. Vypočtěte objem tělesa ohraničeného souřadnými rovinami a plochami z = x2 + y2,x + y = 1. 38 Příklad 39. Vypočtěte integrál J J 2{x2 + y2)áA kde A = {[x,y] G M2 : 1 < x2 + y2 < 4,y > 39 Příklad 40. Spočtěte integrál •1 f\/l— x2 / I J — \/x—X1 40 7. demonstrační cvičení Příklad 41. Pomocí vhodné transformace souřadnic vypočtěte integrál ffA^/xyáxáy, kde množina A je ohraničena křivkami y2 = 2x, y2 = x, xy = 1, xy = 2. 41 Příklad 42. Vypočtěte 1. teziste, 2. momenty setrvačnosti vzhledem k souřadným osám tenké homogenní rovinné lichoběžníkové desky s vrcholy v bodech [—1,0], [2,0], [2,2] a [-1,1]. Řešení. Hustota p(x,y) = 1 pro libovolná x,y. Integrujeme přes množinu A : —1 < x < 2,0 < y < \{x + 4). Dostaneme M = JfAdA = \,TX = ffAx ■ IdA = \,Ty = ±ffAy.ldA = l JX(A) = UaV2dA = f, Jy(A) = JJAx2cL4 = f. 42 Příklad 43. Hodnotu integrálu L l+x: 1 odhadněte pomoct (a) obdélníkového pravidla, (b) lichoběžníkového pravidla (c) Simpsonova pravidla, přičemž zadaný interval rozdělte na 3 intervaly téže délky. Dosažené výsledky porovnejte s přesnou hodnotou a pomocí obrázku zdůvodněte míru nepřesnosti jednotlivých pravidel. 43 Příklad 44. Pomočí matiče souslednosti určete počet sledů délky 4 z vrčholu 0 do vrčholu 1 v nasledujíčím grafu: 44 Příklad 45. Overte, zda dana posloupnost je skore nejakeho grafu. Pokud ano, nčejakíy grafs tíímto skíore nakreslete. (a) (1, 2, 3, 4, 5, 6, 7,8,9), (b) (1,1,1, 2, 2, 3,4, 5, 5). 45 Příklad 46. V grafu na obrízku najdete vsečhny mosty a artikulače. 46 Příklad 47. Udejte príklad grafu, ktery obsahuje pravč (a) 8 artikulačí a 5 mostu, (b) 3 artikulače a 0 mostu, (č) 2 artikulače a 11 mostu. 47 Příklad 48. Rozhodněte, zda jsou zobrazené grafy (vrcholově) 2-souvislé. 48 Příklad 49. Užijte Dijkstrův algoritmus k nalezení nejkratších cest z vyznačeného vrcholu do všech ostatních vrcholu. 49 Příklad 50. Udejte príklad (a) grafu s alespon 4 vrcholý, který neobsahuje cýklus žaporne delký a na nemž dá Dijkstrův algoritmus chýbný výsledek. (b) grafu s alespon 4 vrcholý, který obsahuje (alespon jednu) nežapornou hranu a presto na nem da Dijkstrův algoritmus správný výsledek. 50 Příklad 51. Užijte Bellman-Fordův algoritmus k nalezení nejkratších cest z vyznačeného vrcholu do všech ostatních vrcholu. Hrany procházejte v poradí dle pocatecního (příp. koncového) vrcholu zprava doleva a shola dolu . Zmente ohodnocení hrany z 18 na -18, algoritmus proveďte s tímto novym grafem a ukazte, jak se detekují zaporne cykly. 18 1 2 1 8 51 8. demonstrační cvičení Příklad 52. Uveďte Floydův algoritmus pro nalezeni nejkratšich cest mezi všemi dvojicemi vrcholů. Tento algoritmus použijte na orientovaný graf na obrázku. Jednotlivé mezivýpočty zapisujte do matic. Uveďte, jak se v průběhu výpočtu detekují cykly záporné délky. 52 Příklad 53. Rozhodněte, zda jsou následující grafy eulerovské. Pokud nejsou, doplňte je přidáním hran na eulerovské (je-li to mozné). Nalezněte eulerovske tahy pomocí 1. algoritmu prodlužovaní cyklu; 2. Fleuryho algoritmu (prodlužování tahu s vyhýbáním se mostum). (Očíslujte vrcholy a pri průchodu algoritmu Číslovaní dodržujte.) 53 Příklad 54. Problém čínského pošťáka v hranové ohodnoceném neorientovaném grafu je problémem nalezení nejkratšího uzavéeného sledu, která obsahuje kazdou hranu v grafu. Naleznete resení tohoto problému pro grafna obríazku. 54 Příklad 55 (Nutná podmínka toho, aby graf mohl být hamilto-novský). Je-li G = (V, E) hamiltonovský a 0 ^ W C V, pak G\W má nejvýše \W\ komponent souvislosti. Ukažte na konkrétním příkladu grafu, že opak obecně neplatí. 55 Příklad 56 (Postačující podmínky pro to, aby graf byl hamilto-novský). Dirac: stupeň každého vrcholu je aspoň \V\/2. Ore: součet stupňů libovolných dvou nesousedních vrcholů je aspoň 1^1- B ondy-Chvátal: G je hamiltonovský právě když G + uv je hamilto-novský (u,v jsou nesousední vrcholy, jejichž součet stupňů je aspoň \y\ - opakováním přidáváním takových hran, dokud to jde, získáme tzv. uzávěr grafu cl(G)). 1. Dokažte, že z B ondy-Chvátalovy věty plyne Oreho a z ní Diracova. 2. Udejte příklad hamiltonovského grafu, který splňuje podmínku Oreho věty ale ne věty Diracovy. 3. Udejte příklad hamiltonovského grafu, jehož uzávěr není úplný graf. 56 Příklad 57. Rozhodněte (a zdůvodněte), zda v Petersenově grafu existuje 1. hamiltonovska cesta, 2. hamiltonovska kružnice. 57 Příklad 58. Rozhodněte, zda je daný graf 58 Příklad 59. Rozhodnete, zda existuje graf mající skore (6, 6, 6, 7, 7, 7, 7,8, 8,8). Pokud ano, existuje i rovinný graf daného skore ? 59 Příklad 60. Rozhodnete, zdaje daný rovinný graf maximílní. Doplnte co nejvííce hran pžri zachovaíníí rovinnosti. 60 9. demonstrační cvičení Příklad 61. Každé z následujících tvrzení dokažte nebo ukažte vhodný protipříklad. (a) Každý graf s mene než 9 hranami je rovinný. (b) Graf, který není rovinný, není hamiltonovský. (c) Graf, který není rovinný, je hamiltonovský. (d) Graf, kteríý neníí rovinníý, neníí eulerovskíý. (e) Graf, kteríý neníí rovinníý, je eulerovskíý. (f) Kažzdíý hamiltonovskíý grafje rovinníý. (g) žaídníý hamiltonovskíý grafneníí rovinníý. (h) Kažzdíý eulerovskíý grafje rovinníý. (i) žaídníý eulerovskíý grafneníí rovinníý. 61 Příklad 62. Určete všechny (neizomorfni) stromy 1. na čtyřech vrcholech. 2. na šesti vrcholech. 62 Příklad 63. Určete kod grafu na obrízku jako 1. p est eníeho stromu, 2. stromu 63 Příklad 64. Rozhodněte, zda existují stromy s následujícími kódy. V případě, že ano, potom, daný strom, nakreslete. • 00011001111001, • 00000110010010111110010100001010111111. 64 Příklad 65. Určete počet koster 1. K4, K5 2- C2010? 3. vějíře Vn ( kde vějířem, vn řádu n nazveme graf nan + l vrcholech 0,1,... ,n, který má následujících 2n — 1 hran: vrchol O je spojen hranou s každým ze zbylách vrcholů a každý vrchol k je spojen hranou s vrcholem k+l pro 1 < k < n), z odvozeného rekurentního vztahu vypočtěte několik prvních hodnot, všimněte si souvislosti s Fibonacciho posloupností a tuto souvislost dokažte; 4- žebříku Žn (tvořeného děma cestami délky n a příslušnými dvojicemi vrcholů spojenými hranou) - odvoďte pouze rekurentní vztah. [Návod: Uvažte vrchol n a jeho napojení na "zbytek" kostry. Rekurence je fn = /n. —1 + Ax—1+Ax —2+Ax —3 + ** * + fi +1 = fn — i + Y2k 0]? odkud dostaneme později fn = F2n> kde Fk je k-té Fibonacciho číslo. ] 65 10. demonstrační cvičení Příklad 66. Pomocí kódu dokažte izomorfismus stromu: 66 Příklad 67. Huffmanovo kódování Pracujeme s pěstěnými binárními stromy, kde máme navíc každou hranu obarvenou některým symbolem z dané výstupní abecedy A (často A = {0,1}). Kódovými slovy C jsou slova nad abecedou A, na která převádíme symboly vstupní abecedy. Našim úkolem je reprezentovat daný text pomocí vhodných kódových slov nad výstupní abecedou. Je snadno vidět, že je užitečné chtít, aby seznam kódových slov byl bezprefixový (v opačném případě může nastat problém s dekódováním). Ke konstrukci binárních prefixových kódů (tj. nad abecedou A = {0,1}) využijeme binárních stromů. Označíme-li hrany vycházející z každého uzlu O, resp. 1, a označíme-li navíc listy stromu symboly vstupní abecedy, dostaneme prefixový kód nad A pro tyto symboly zřetězením označení hran na cestě z kořene do příslušného listu. Takto vytvořený kód je zřejmě prefixový. Uděláme-li tuto konstrukci navíc tak, abychom odrazili četnost symbolů vstupní abecedy v kódovaném textu, dosáhneme tak dokonce bezztrátové komprese dat. Nechť M je seznam četností symbolů vstupní abecedy v textu. Algoritmus postupně zkonstruuje optimální binární strom (tzv. minimum-weight binary tree) a přiřazení symbolů listům. • Vyber dvě nejmenší četnosti w\,W2 z M. Vyrob strom se dvěma listy označenými příslušnými symboly a kořenem označeným u>\ + W'i , odeber z M hodnoty w\,W2 a nahraď je hodnotou u>\ +W2- • Tento krok opakuj; pouze v případě, že vybraná hodnota z M je součtem,, pak nevyráběj nový list, ale "připoj"příslušný již existující podstrom,. • Kód každého symbolu urči cestou od kořene (např. vlevo="0", vpravo="1"). Nalezněte Huffmanův kód pro vstupní abecedu s frekvencemi ['A':16, >B>:13, >C>:9, >D>:12, }E':^5, 'F':5]. 67 Příklad 68. Najdete minimální kostru grafu na obrázku pomocí (a) Kruskalova (b) Jarníkova (Primova) algoritmu. (c) Borluvkova algoritmu. Jak se výpočet zmení, pokud hledame maximalní kostru? ^37\ A K 4 12 17 1 3 1 1 1 5 3 2 2 5 68 Příklad 69. Najděte minimální kostru pomocí maticové verze Jarník-Primova algoritmu v grafu zadaném maticí ohodnocení hran /— 12 — 16 — — — 13\ 12 — 16 — — — 14 — — 16 — 12 — 14 — — 16 — 12 — 13 — — — - - - 13 - 14 - 15 — — 14 — 14 — 15 — - 14 - - - 15 - 14 v13 - - - 15 - 14 -j 69 Příklad 70. Udejte príklad, na nrmrukazete nefunkčnost "naivního"algoritmu pro nalezení nejkratsí cesty: 1. naleznete minimalní kostru, 2. za nejkratsí cestu prohlasíme tu jedinou cestu spojující zadane 2 vrcholy, ktera lezí v nalezení minimílní kostre. 70 Příklad 71. Maximální párování v bipartitním grafu • perfektní párování v obecném grafu (viz CPP - chinese postman problém) • Tutteho věta - graf má perfektní párování, právě když pro každé S C V počet lichých komponent G\S nepřevyšuje \S\. Maďarský algoritmus (König, Egerváry, Kuhn) Označujme kvůli jednoduchosti popisu vrcholy jedné skupiny v bipartitním grafu jako červené, vrcholy druhé skupiny jako modré. Budeme předpokládat, že vrcholy jsou obarveny tak, že počet červených vrcholů nepřevyšuje počet modrých. Nechť je dán bipartitní graf G = (V, E) a párování MCE. M-alternující cestou v G nazveme takovou cestu v G, jejíž hrany tvoří střídavě hrany z M a z E \ M. M-rozšiřující cestou v G nazveme M-alternující cestu, která spojuje dosud nepřiřazený červený vrchol u s dosud nepřiřazeným modrým vrcholem v. 1. Nalezneme libovolné párování M. Označíme všechny červené vrcholy jako přípustné. 2. Vyberme některý dosud nepřiřazený přípustný červený vrchol v (pokud neexistuje, jsme hotovi) a nalezněme pro něj (např. prostřednictvím prohledávání do hloubky) M-alternující strom s kořenem ve v (pokud neexistuje, označme v jako nepřípustný a proces opakujme s jiným vrcholem). Pokud strom obsahuje nějakou M-rozšiřující cestu, odstraníme M-hrany v této cestě z M a ostatní hrany této cesty do M přidáme. Označme všechny červené vrcholy jako přípustné a proces opakujme. V bipartitním grafu na obrázku najděte takovou maximální podmnožinu hran, že žádné dvě z nich nesdílejí společný vrchol. 71 Příklad 72. Určete hodnotu maximálního toku a najděte minimální řez v síti dané mMicí kapacit A, kde vrchol 1 je zdroj a vrchol 8 stok. I- 16 24 12 - - - -\ ----30-------96 12- -----9-15 -------9 -------18 \--" "----/ 72 Příklad 73. Na obmzku je uveden tok v dane síti (Čísla f/c udavají současný tok a kapacitu dane hraný). Zjistěte, je-li uvedený tok ma-ximalní, pokud ano, sve tvrzení zdůvodnete. Pokud maximalním tokem není, maximílní tok najdete a svůj postup podrobne popište. Uved'te nžekteríý minimíalníí žrez v daníe sííti. 8/14 2/10+(66ŕ 18/18 6/6 6/16 ^y- 12/16+(5 10/10^ 12/20- 73 11. demonstrační cvičení Příklad 74. Naleznete maximální tok a minimální rez v síti na obrázku (zdroj=1,stok=14 ). 74 Příklad 75. Pomocí Ford-Fulkersonova algoritmu (prohledáváni do hloubky, vrcholy volte vzestupně podle čísel) nalezněte maximální tok v síti na množině vrcholů {1, 2,..., 9} se zdrojem 1 a stokem, 9. Nalezněte minimální řez v této síti. Jednotlivé kroky svého postupu podrobně popište. Hrany e G E , dolní omezení, resp. horní omezení na tok danou hranou (d(e), resp. h(e)) a současný tok na dané hraně f(e) jsou uvedeny v tabulce: e d(e) h(e) /(e) e d(e) h(e) /(e) (W) (1,3) (1,6) (2.3) (2.4) (3.4) (3.5) (4,5) (4,8) 0 6 0 0 6 0 0 4 0 0 2 0 0 3 0 0 4 0 0 4 0 3 5 4 0 3 0 (5,1) (5.6) (5.7) (5.8) (6.9) (7,4) (7,9) (8,9) 0 3 0 0 6 0 0 5 4 0 5 0 0 5 0 1 6 4 0 3 0 0 9 0 75 Příklad 76. Kolika způsoby je mozne koupit 12 balícků kívy, mají-li v prodejne kavu peti druhu? Dale tuto ulohu reste s nasledujícími modifikacemi: (a) od kazde kavy je treba koupit aspon 2 balícky; (b) od kazde kavy ma byt koupen sudy pocet balícků; (c) jedne z kav (napr. arabske) jsou k dispozici pouze 3 balícky. 76 12. demonstrační cvičení Příklad 77. Určete kolika způsoby je možné naplnit tašku n kusy uvedených druhů ovoce, přičemž jednotlivé kusy téhož druhu nerozlišujeme, nemusí být využity všechny druhy a navíc: • jablek může být libovolný počet, • banánů musí být sudý počet, • hrušek musí být násobek 4, • pomeranče mohou být nejvýše 3 a • pomelo může být pouze jedno (nebo žádné), 77 Příklad 78. Rozviňte do mocninné řady funkci fL ) X2+X+í \Us 2x3+3x2+r 78 Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (ai + bi) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení (a • clí) 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>k-i, 0,...) a poté podělíme vytvořující funkci xk. • Substituci polynomu f(x) — oíx za x odpovídá vynásobení £-tého členu posloupnosti skalárem ak, podobně dosazení f(x) = xn nám do posloupnosti mezi každé dva členy vloží n — 1 nul. Příklad 79. (a) Určete vytvořující funkci posloupnosti (1,2,3,4,5,...). (b) Určete vytvořující funkci posloupnosti (1,4,9,16,...). (c) Určete vytvořující funkci posloupnosti (1,1,2,2,4,4,8,8,...). (d) Určete vytvořující funkci posloupnosti (9,0,0,2-16,0,0,4-25,0,0,8-36,...). (e) Určete vytvořující funkci posloupnosti (9,1, -9, 32,1, -32,100,1, -100,...,). 79 Příklad 80. Vyřešte rekurenci ao = cl\ = 1 0"a = 0"a-l + 2an_2 + (~ [Návod: • Krok 1: an = a„_i + 2a„_2 + (-l)"[n > 0] + [n = 1] • ífrofc 2: a(x) = íA(i) + 2x2A(x) + + x. • Krok 3: A{x) (1 - 2x){l + a;)2 ' Krok 4: an = f 2™ + (In + f) (-1)™. 80 Příklad 81. Řešte rekurenci 3 1 an = öfln-i - ößn-3> ao = O, ai = 1, a2 = 13/2. 81 Příklad 82. S využitím vytvořující funkce pro Fibonacciho posloupnost F{x) = x/(l — x — x2) určete vytvořující funkci "poloviční" Fibonacciho posloupnosti (Fq, F2, F4,...). [Odpověď: xf (1 — 3x -\- x2)] ] 82 Příklad 83 (viz. Př. 65). Vějířem řádu n nazveme graf na n + 1 vrcholech 0,1,... ,n, který má následujících 2n — 1 hran: vrchol O je spojen hranou s každým ze zbylách vrcholů a každý vrchol k je spojen hranou s vrcholem k + 1 (pro 1 < k < n). Kolik koster má takový graf? (Návod: Využijte dříve odvozené rekurence n—í k=í 83