Matematika III - 13. přednáška Aplikace vytvořujících funkcí Michal Bulant Masarykova univerzita Fakulta informatiky 11. 12. 2007 = Obsai Vytvořující funkce Q Řešení reku renci a S - = -E -0a*0 • H. S. Wilf, Generatingfunctionology, Academie Press, druhé vydaní, 1994 , (rovněž http://www.math.upenn.edu/~wilf/DownldGF.html) • R. Graham, D. Knuth, 0. Patashnik, Concrete Mathematics, druhé vydání, Addison-Wesley, 1994. • H. S. Wilf, Generatingfunctionology, Academie 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. • Martin Panák, Jan Slovák, Drsná matematika, e-text. • H. S. Wilf, Generatingfunctionology, Academie Press, druhé vydaní, 1994 , (rovněž http://www.math.upenn.edu/~wilf/DownldGF.html) • R. Graham, D. Knuth, 0. Patashnik, Concrete Mathematics, druhé vydání, Addison-Wesley, 1994. • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. lán přei Q Vytvořující funkce oooooooooooo □ s ~ = ■€. -o<\(y 0paková Definice (Obyčejnou) vytvořující funkcí posloupnosti a = (• Jo, ai ,^2 • ••) rozumíme mocninnou řadu oo y^ anx" = a0 + a\ n=0 x + a2x2 + a3x3 + • Exponenc iální vytvořující fun ccí posloupnosti a = = (a0, 31, 32,...) pak rozumíme mocninnou řadu °° x" /3n—r = a0 + ai n=Q 2 3 X X X l!+a22!+3! + • □ g - = Poznámka Používají se i další typy vytvořujících funkcí (např. v teorii čísel se používají Dirichletovy vytvořující funkce, kde roli faktoru x" hraje n~x), ale těmi se zde zabývat nebudeme. Poznámka Používají se i další typy vytvořujících funkcí (např. v teorii čísel se používají Dirichletovy vytvořující funkce, kde roli faktoru x" hraje n~x), ale těmi se zde zabývat nebudeme. 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, 0 v případě jeho nesplnění. Např. [n = l],[2|n] apod. Poznámka Používají se i další typy vytvořujících funkcí (např. v teorii čísel se používají Dirichletovy vytvořující funkce, kde roli faktoru x" hraje n~x), ale těmi se zde zabývat nebudeme. 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, 0 v případě jeho nesplnění. Např. [n = 1], [2|n] apod. Pro vyjádření koeficientu u x" ve vytvořující funkci F(x) se pak často používá zápis [x"]F(x). • Sčítání dvou posloupností člen po členu. • Vynásobení všech členů posloupnosti stejným skalárem. • Posunutí posloupnosti doprava. • Posunutí posloupnosti doleva. • Vynásobení n-tého členu posloupnosti skalárem a". • „Nafouknutí" posloupnosti nulami. • Vynásobení n-tého členu posloupnosti číslem n. • Vydělení n-tého členu posloupnosti číslem n. a Konvoluce posloupností cn = J2o0 n>l v—«, x" n>0 smx cosx B-i>"i£ ,2n+l n>0 (2/1 + 1)!' Ec-1)" ,2n n>0 (2n)ľ (1,1,1,... Ill (0,1,-,-,-... (1'1'2'6'24"" (0,1,0,-jU^,... (1,0,-i,o,— ),0,... *+"-£&• 0 —[— = X>|n]xn, (1, O,..., 0,1, O,..., 0,1,... (l_1x)2=E(n + 1)x"' (1,2,3,4,5,... (1, r,r2,r2,r3,... 111 1 — rx ^—' ln(l+x) = J]-(-!)"+V (0,1 ' r\ 5 O 5 yl 1 • ' ' 2'3' 4' □ g - = Plán přei Q Řešení reku renci □ g - = -E-OQ^O" Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí. Tím je míněno vyjádření členu an jako funkci n. Často se s pomocí řad podaří vyřešit na první pohled velmi složité rekurence. Obvyklý (takřka mechanický) postup pro řešení rekurencí se skládá ze 4 kroků: O Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n G No (předpokládajíce a_i = a_2 = • • • = 0). Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí. Tím je míněno vyjádření členu an jako funkci n. Často se s pomocí řad podaří vyřešit na první pohled velmi složité rekurence. Obvyklý (takřka mechanický) postup pro řešení rekurencí se skládá ze 4 kroků: O Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n G No (předpokládajíce a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme x" a sečteme přes všechna n G No- Na jedné straně tak dostaneme J2n anx", což je vytvořující funkce A(x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí. Tím je míněno vyjádření členu an jako funkci n. Často se s pomocí řad podaří vyřešit na první pohled velmi složité rekurence. Obvyklý (takřka mechanický) postup pro řešení rekurencí se skládá ze 4 kroků: O Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n G No (předpokládajíce a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme x" a sečteme přes všechna n G No- Na jedné straně tak dostaneme J2n anx", což je vytvořující funkce A(x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). O Zjištěná rovnice se vyřeší vzhledem k A(x). Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí. Tím je míněno vyjádření členu an jako funkci n. Často se s pomocí řad podaří vyřešit na první pohled velmi složité rekurence. Obvyklý (takřka mechanický) postup pro řešení rekurencí se skládá ze 4 kroků: O Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n G No (předpokládajíce a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme x" a sečteme přes všechna n G No- Na jedné straně tak dostaneme J2n anx", což je vytvořující funkce A{x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A{x). O Zjištěná rovnice se vyřeší vzhledem k A(x). O Výsledné A(x) se rozvine do mocninné řady, přičemž koeficient u x" udává an, tj. an = [x"]A(x) . Jak jsme již viděli na příkladu Fibonacciho posloupnosti, v kroku 4 často s výhodou využijeme rozkladu na parciální zlomky. Ten jsme již viděli dříve (často se používá při integraci racionálních lomených funkcí), proto připomeneme jen stručně: • Předpokládáme, že P(x)/Q(x) je podíl polynomů, kde st P < st Q (jinak vydělíme se zbytkem) a P(x), Q(x) nemají společné kořeny. Jak jsme již viděli na příkladu Fibonacciho posloupnosti, v kroku 4 často s výhodou využijeme rozkladu na parciální zlomky. Ten jsme již viděli dříve (často se používá při integraci racionálních lomených funkcí), proto připomeneme jen stručně: • Předpokládáme, že P(x)/Q(x) je podíl polynomů, kde st P < st Q (jinak vydělíme se zbytkem) a P(x), Q(x) nemají společné kořeny. • Polynom Q(x) rozložíme na kořenové činitele. Jak jsme již viděli na příkladu Fibonacciho posloupnosti, v kroku 4 často s výhodou využijeme rozkladu na parciální zlomky. Ten jsme již viděli dříve (často se používá při integraci racionálních lomených funkcí), proto připomeneme jen stručně: • Předpokládáme, že P(x)/Q(x) je podíl polynomů, kde st P < st Q (jinak vydělíme se zbytkem) a P(x), Q(x) nemají společné kořeny. • Polynom Q(x) rozložíme na kořenové činitele. » Jsou-li všechny kořeny ai,...,ag jednoduché, pak Q(X) x — ot\ x — a/ Jak jsme již viděli na příkladu Fibonacciho posloupnosti, v kroku 4 často s výhodou využijeme rozkladu na parciální zlomky. Ten jsme již viděli dříve (často se používá při integraci racionálních lomených funkcí), proto připomeneme jen stručně: • Předpokládáme, že P(x)/Q(x) je podíl polynomů, kde st P < st Q (jinak vydělíme se zbytkem) a P(x), Q(x) nemají společné kořeny. • Polynom Q(x) rozložíme na kořenové činitele. » Jsou-li všechny kořeny ai,... ,ag jednoduché, pak 1 vyhovuje bn rekurentní formuli bn = bobn-i + b\bn-2 H---------h bn-ibo. 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, fc = 2, b3 = 5. Snadno nahlédneme, že pro n > 1 vyhovuje bn rekurentní formuli bn = bobn-i + b\bn-2 H---------h bn-ibo. Vidíme, že jde vlastně o konvoluci posloupností. Vztah upravíme, aby platil pro všechna n G Nq\ bn = Y^ bkbn_k_x + [n = 0]. 0 = °K = n n,k n,k = J>fcxMJ>n_k_1xfl-M+i = = Y bkxk(xB(x)) + 1 = ß(x) • xß(x) + 1. k □ s ~ V kroku 2 vynásobíme obě strany x" a sečteme. Je-li B{x) odpovídající vytvořující funkce, pak: B{x) = J2 bnx" = Y, bkbn-k-ix" + J> = °K -- n,k n,k Y,bkxk ľ^bn-k-ix"-^ +1 = : Y, bkxk(xB(x)) + 1 = B(x) ■ xB(x) + 1. k Pozorný čtenář si jistě povšiml, že ve výše uvedeném výpočtu jsme nahradili konvoluci bn = bobn-\ + b\bn-i + • • • + bn-\bo vztahem bn = bobn-i H--------h bn-ibo + bnb-\ + bn+1b-2 H------. Díky naší konvenci to ale není problém a velmi to usnadňuje práci se sumami (s nekonečnými součty se zde pracuje podstatně snadněji než s konečnými, kdy musíme neustále hlídat meze). V kroku 3 řešíme kvadratickou rovnici B{x) = xB{x)2 + 1 pro E(x) : = 1±VTHÍE v ' 2x Znaménko + ale nepřichází v úvahu, protože pak by pro x —> 0_| B{x) měla limitu oo, zatímco vytvořující funkce pro naši posloupnost musí mít v 0 hodnotu bo = 1. = 4 V kroku 3 řešíme kvadratickou rovnici B{x) = xB{x)2 + 1 pro E(x) : = 1±VTHÍE v ' 2x Znaménko + ale nepřichází v úvahu, protože pak by pro x —> 0_| B{x) měla limitu oo, zatímco vytvořující funkce pro naši posloupnost musí mít v 0 hodnotu bo = 1. Zbývá už pouze krok 4, tedy rozvinout B{x) do mocninné řady. Rozvoj získáme pomocí zobecněné binomické věty ^ OL ElY) (-<>*)' (l-4x)"2 = k>0 v " / k>\ a po vydělení 1 — \/I — 4x výrazem 2x dostaneme 2k\k-l (-4x)A n>0 n>0 2n n J n + 1 = 4 Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = -^ (2n") - tato významná posloupnost se nazývá posloupnost Catalanových čísel. Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = -^ (2n") - tato významná posloupnost se nazývá posloupnost Catalanových čísel. 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 Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = -^ (2n") - tato významná posloupnost se nazývá posloupnost Catalanových čísel. 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ě takové fronty u pokladny (5koruny a lOkoruny), že nezásobená pokladna může vždy vrátit Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = -^ (2n") - tato významná posloupnost se nazývá posloupnost Catalanových čísel. 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ě takové fronty u pokladny (5koruny a lOkoruny), že nezásobená pokladna může vždy vrátit • počet korektně uzávorkovaných výrazů složených z levých a pravých závorek Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = -^ (2n") - tato významná posloupnost se nazývá posloupnost Catalanových čísel. 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ě takové fronty u pokladny (5koruny a lOkoruny), že nezásobená pokladna může vždy vrátit • počet korektně uzá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 Catal Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = -^ (2n") - tato významná posloupnost se nazývá posloupnost Catalanových čísel. 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ě takové fronty u pokladny (5koruny a lOkoruny), že nezásobená pokladna může vždy vrátit • počet korektně uzá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. ' Příklad ' Vyřešte rekurenci 30 = 3i = 1 a„ = a„_i + 2a„_2 + (-!)" Vytvořující funkce ooooo Ještě Příklad Vyřešte rekurenci ■?0 = 3\ = 1 a„ = a„_i + 2a„_2 + (-!)" Tato rekurence je opět jiného typu než dosud studované. Jako vždy neuškodí vypsání prvních několika členů posloupnosti (teď ale ani moc nepomůže, snad jen pro kontrolu správnosti výsledku).3 "Narozdíl od tvrzení v Concrete mathematics je již možné tuto posloupnost nalézt v The On-Line Encyclopedia of Integer Sequences. Řešení (pokr.) • Krok 1: an = a„_i + 2a„_2 + (-1)> > 0] + [n = 1]. • Krok 2: A(x) = xA(x) + 2x2A(x) + ^ + x. Řešení (pokr.) • Krok 1: an = a„_i + 2a„_2 + (-1)> > 0] + [n = 1]. • Krok 2: A(x) = xA(x) + 2x2A(x) + ^ + x. • Krok 3: (l-2x)(l+x)2- Řešení (pokr.) _________________________________________1 • Krok 1: an = a„_i + 2a„_2 + (-l)"[n > 0] + [n = = !]• • Krok 2: A(x) = xA(x) + 2x2A(x) + ^ + x. • Krok 3: ^Xj-(l-2x)(l+x)2- • Krok 4: a„ = |2" + (±n + §) (-1)". = Někdy dokážeme snadno vyjádřit hledaný počet jen pomocí více vzájemně provázaných posloupností. Reku Někdy dokážeme snadno vyjádřit hledaný počet jen pomocí více vzájemně provázaných posloupností. Příklad Kolika způsoby můžeme pokrýt (nerozlíšenými) kostkami domina obdélník 3 x n? □ s Reku Někdy dokážeme snadno vyjádřit hledaný počet jen pomocí více vzájemně provázaných posloupností. Příklad Kolika způsoby můžeme pokrýt (nerozlíšenými) kostkami domina obdélník 3 x n? Snadno zjistíme, že c\ = 0, c-i = 3, C3 = 0, dále klademe cq = 1 (nejde jen o konvenci, má to svou logiku). Reku Někdy dokážeme snadno vyjádřit hledaný počet jen pomocí více vzájemně provázaných posloupností. Příklad Kolika způsoby můžeme pokrýt (nerozlíšenými) kostkami domina obdélník 3 x n? Snadno zjistíme, že c\ = 0, c2 = 3, C3 = 0, dále klademe cq = 1 (nejde jen o konvenci, má to svou logiku). Najdeme rekurzívní vztah - diskusí chování „na kraji" zjistíme, že cn = 2r„_i + c„_2, rn = c„_2 + rn_2, r0 = 0, rx = 1, kde rn je počet pokrytí obdélníku 3 x n, ze kterého jsme odstranili levý horní roh. Řešení (pokr.) Krok 1: c„ = 2r„_i + c„_2 + [n = 0], rn = u„_i + r„_2. □ S - = .= -f)<\(> Řešení (pokr.) • Krok 1: c„ = 2r„_i + c„_2 + [n = 0], r„ = un_i + rn_2. • Krok 2: C(x) = 2x/?(x) + x2 C(x) + 1, R(x) = xC(x) + x2 /?(x). □ g - = Řešení (pokr.) • Krok 1: cn = 2r„_ • Krok 2: C(x) = 2x/?(x) + a Krok 3: -i + cn-2 + [n x2C(x) + l, 1-x2 { ' ~ i _ - 4x2 + x4 ' 1 1 = 0], rn — un-i + rn_2. Rix)- = xC(x) + x2/?(x). R(x) X 1 - 4x2 + x4 ' □ S - = .= -f)<\o Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = u„_i + r„_2. • Krok 2: C(x) = 2x/?(x) + x2 C(x) + 1, R(x) = xC(x) + x2 /?(x). • Krok 3: .2 C(x) 1-x^ /?(x) l-4x2+x4' "vv l-4x2+x4' • Krok 4: Vidíme, že obě funkce jsou funkcemi z2, ušetříme si práci tím, že uvážíme funkci D(x) = 1/(1 — 4x + x2), pak totiž C(x) = (l-x2)D(x2), tj. [x2"]C(x) = [x2"](l -x2)D(x2) = [x"](l -x)D(x), a tedy Qn = dn — dn-\. = Řešení (závěr) Kořeny 1 — 4x + x2 jsou 2 + a/3 a 2 — a/3 a již standardním způsobem obdržíme = (2 + vgr | (2 - Všy C2n 3-a/3 3 +a/3 = Řešení (závěr) Kořeny 1 — 4x + x2 jsou 2 + a/3 a 2 — a/3 a již standardním způsobem obdržíme (2 +a/3)" (2-a/3)" Qn = —-------— + V^ 3 + a/3 Podobně jako u Fibonacciho posloupnosti je druhý sčítanec pro velká n zanedbatelný a pro všechna n leží mezi 0 a 1, proto Qn (2 +a/3)" 3-a/3 Např. C20 = 413403.