Matematika III - 14. přednáška Aplikace vytvořujících funkcí - další úlohy Michal Bulant Masarykova univerzita Fakulta informatiky 18. 12. 2007 = Obsa. Řešení rekurencí Q Exponenciální vytvořující funkce 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. Řešení reku rend □ g - = -E-OQ^O" Mocninné rady jsou velmi silným nástrojem pro resení 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é rady jsou velmi silným nástrojem pro resení 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é rady jsou velmi silným nástrojem pro resení 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é rady jsou velmi silným nástrojem pro resení 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) . Někdy dokážeme snadno vyjádřit hledaný počet jen pomocí více vzájemně provázaných posloupností. 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 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). □ s 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). Najdeme rekurzívní vztah - diskusí chování „na kraji" zjistíme, že cn = 2r„_i + c„_2, rn = c„_i + r„_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. □ s Hodnoty cn a rn pro několik malých n jsou: n 0 1 2 3 4 5 6 7 Cn 1 0 3 0 11 0 41 0 rn 0 1 0 4 0 15 0 56 □ s - = -E -o^o Řešení (pokr.) Krok 1: c„ = 2r„_i + c„_2 + [n = 0], rn = u„_i + r„_2. □ S - = .= -f)<\(> a 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). □ S - = -E -O^O" Ř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 ' □ g - = • 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: C(X) = 1-4X2+X4' ^W = i.4,2+,4- • Krok 4: Vidíme, že obě funkce jsou funkcemi x2, ušetříme si práci tím, že uvážíme funkci D(z) = 1/(1 — 4z + z2), pak totiž C(x) = (1 - 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 □ s - = Ř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. Plán Q Exponenciální vytvořující funkce □ g - = -E-OQ^O" Někdy mívá vytvořující funkce posloupnosti (an) komplikované vlastnosti, přičemž posloupnost (an/n\) má vytvořující funkci daleko jednodušší. V takových případech raději pracujeme s tzv. exponenciálními vytvořujícími funkcemi n>0 Jméno vychází z toho, že vytvořující funkcí základní posloupnosti (1,1,1,1,...) je e\ Někdy mívá vytvořující funkce posloupnosti (an) komplikované vlastnosti, přičemž posloupnost (an/n\) má vytvořující funkci daleko jednodušší. V takových případech raději pracujeme s tzv. exponenciálními vytvořujícími funkcemi n>0 Jméno vychází z toho, že vytvořující funkcí základní posloupnosti (1,1,1,1,...) je e\ Zdůrazněme, že exponenciální vytvořující funkce se od obyčejných liší i standardními operacemi. u S ~ = ■= -00*0 Vynásobením x získame funkci posloupnosti (na„_i). • Vynásobením x získáme funkci posloupnosti (na„_i). • Derivací získáme funkci odpovídající posunutí doleva. • Vynásobením x získáme funkci posloupnosti (na„_i). • Derivací získáme funkci odpovídající posunutí doleva. • Integrací získáme funkci odpovídající posunutí doprava. • Vynásobením x získáme funkci posloupnosti (na„_i). • Derivací získáme funkci odpovídající posunutí doleva. • Integrací získáme funkci odpovídající posunutí doprava. • Součinem dvou funkcí F(x) a G(x) získáme funkci H(x), která odpovídá posloupnosti hn = J2k (£)fkgn-k, tzv. binomické konvoluci fn a gn. Příklad ' Řešte re kurenci danou vztahy go = 0, gl = = la předpisem gn = -2ngn. i + E k>0 c: Igfcgr -k- Vzhledem k rekurentnímu vztahu, který obsahuje binomickou konvoluci posloupností, se zdá vhodné využít exponenciálních vytvořujících funkcí. Označme G(x) příslušnou exponenciální mocninnou řadu. Budeme postupovat v obvyklých čtyřech krocích. Příklad ' Řešte re kurenci danou vztahy go = 0, gl = = la předpisem gn = -2ngn. i + E k>0 c: IgTcgV -k- Vzhledem k rekurentnímu vztahu, který obsahuje binomickou konvoluci posloupností, se zdá vhodné využít exponenciálních vytvořujících funkcí. Označme G(x) příslušnou exponenciální mocninnou řadu. Budeme postupovat v obvyklých čtyřech krocích. • Krok 1: gn = -2ngn_x + Y,k>o {"k)gkgn-k + [n = 1] . Příklad ' Řešte re kurenci danou vztahy go = 0, gl = = la předpisem gn = -2ngn. i + E k>0 c: IgTcgV -k- Vzhledem k rekurentnímu vztahu, který obsahuje binomickou konvoluci posloupností, se zdá vhodné využít exponenciálních vytvořujících funkcí. Označme G(x) příslušnou exponenciální mocninnou řadu. Budeme postupovat v obvyklých čtyřech krocích. • Krok 1: gn = -2ngn_x + ^>o {k)gkgn-k + [n • Krok 2: G(x) = -2xG(x) + G(x)2 +x. 1] Řešení (pokr.) • Krok 3: Řešením kvadratické rovnice dostaneme G(x) = 1/2(1 + 2x ± Vl + 4x2). Dosazením x = odpovídá znaménko —, proto je řešením funkce 0 vidíme, že G(x) = 1 + 2x - Vl + 4x2 Řešení (pokr.) • Krok 3: Řešením kvadratické rovnice dostaneme G(x) = 1/2(1 + 2x ± Vl + 4x2). Dosazení m x = 0 vidíme, že odpovídá znaménko —, proto je řešením funkce ~ , 1 + 2x - VI + 4x2 G{x) =--------------------------. • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů Řešení (pokr.) • Krok 3: Řešením kvadratické rovnice dostaneme G(x) = 1/2(1 + 2x ± Vl + 4x2). Dosazení m x = 0 vidíme, že odpovídá znaménko —, proto je řešením funkce ~ , 1 + 2x - VI + 4x2 G{x) =--------------------------. • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů Řešení (pokr.) • Krok 3: Řešením kvadratické rovnice dostaneme G(x) = 1/2(1 + 2x ± Vl + 4x2). Dosazení m x = 0 vidíme, že odpovídá znaménko —, proto je řešením funkce G(x) 1 + 2x - Vl + 4x2 • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů -1/2 k 2/c k Řešení (pokr.) • Krok 3: Řešením kvadratické rovnice dostaneme G(x) = 1/2(1 + 2x ± Vl + 4x2). Dosazení m x = 0 vidíme, že odpovídá znaménko —, proto je řešením funkce G(x) 1 + 2x - Vl + 4x2 • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů -1/2 k 2/c k 1/2 k 1 Ik -1/2 k-\ postupně dostaneme Řešení (pokr.) • Krok 3: Řešením kvadratické rovnice dostaneme G(x) = 1/2(1 + 2x ± Vl + 4x2). Dosazení m x = 0 vidíme, že odpovídá znaménko —, proto je řešením funkce G(x) 1 + 2x - Vl + 4x2 • Krok 4: Pomocí zobecněné binomické věty rozvineme G(x) do mocninné řady. S využitím vztahů -1/2 k 2/c k 1/2 k 1 Ik -1/2 k-\ postupně dostaneme Řešení (dokončení) Řešení (dokončení) TT^ + Eff-i)-^). k>l v 7 x2k. Odtud, protože n>0 máme g2k+i = 0 £«4 = gw 1 + 2x - Vl + 4x2 Řešení (dokončení) TT^ + Eff-i)-^). k>l v 7 x2k. Odtud, protože n>0 máme g2k+i = 0 a £«4 = gw 1 + 2x - Vl + 4x2 to=(-i)'-K2*-"iVp*)' Řešení (dokončení) TT^ + Eff-i)-^). k>l v 7 x2k. Odtud, protože £«4 = gw 1 + 2x - Vl + 4x2 n>0 máme g2/c+i = 0 a &k = (~l)k -k{^kkZl) ■ (2lí)! = (-'1)k • (2*)! ' Ck-i. kde Cn je n-té Catalanovo číslo. Připomeňme, že jsme již dříve dokázali, že počet stromů na n vrcholech je n{Kn) = nn~2. Dokážeme tento výsledek ještě jednou pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = n{Kn). Již dříve jsme viděli, že ři = Í2 = 1, Í3 = 3. Lze rovněž snadno spočítat U = 16. Připomeňme, že jsme již dříve dokázali, že počet stromů na n vrcholech je n{Kn) = nn~2. Dokážeme tento výsledek ještě jednou pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = n{Kn). Již dříve jsme viděli, že ři = Í2 = 1, Í3 = 3. Lze rovněž snadno spočítat U = 16. Rekurentní vztah získáme tak, že zafixujeme jeden vrchol v a možné případy rozdělíme podle počtu komponent v grafu, který dostaneme z koster Kn tak, že odstraníme vrchol v a hrany s ním incidentní. Připomeňme, že jsme již dříve dokázali, že počet stromů na n vrcholech je n{Kn) = nn~2. Dokážeme tento výsledek ještě jednou pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = n{Kn). Již dříve jsme viděli, že ři = Í2 = 1, Í3 = 3. Lze rovněž snadno spočítat U = 16. Rekurentní vztah získáme tak, že zafixujeme jeden vrchol v a možné případy rozdělíme podle počtu komponent v grafu, který dostaneme z koster Kn tak, že odstraníme vrchol v a hrany s ním incidentní. Pak pro n > 1 m>0 k1+-+km=n-l V X' ' m/ Připomeňme, že jsme již dříve dokázali, že počet stromů na n vrcholech je n{Kn) = nn~2. Dokážeme tento výsledek ještě jednou pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = n{Kn). Již dříve jsme viděli, že ři = Í2 = 1, Í3 = 3. Lze rovněž snadno spočítat U = 16. Rekurentní vztah získáme tak, že zafixujeme jeden vrchol v a možné případy rozdělíme podle počtu komponent v grafu, který dostaneme z koster Kn tak, že odstraníme vrchol v a hrany s ním incidentní. Pak pro n > 1 m>0 k1+-+km=n-l V Ll ' m/ Např. pro n = 4 máme U = 3ř3 + 6řiÍ2 + íf. Ošklivě vypadající rekurenci zjednodušíme substitucí un = ntn. Dostáváme pro n > 1 un _ ^-^ 1 ^-^ m>0 ki-\-----\-km=n-l Uki kX\ ^krr k J a je vidět, že vnitřní sumu dostaneme jako koeficient u x" 1 v m-té mocnině řady U{x) = J2un^\- = Ošklivě vypadající rekurenci zjednodušíme substitucí un = ntn. Dostáváme pro n > 1 un _ ^-^ 1 ^-^ m>0 ki-\-----\-km=n-l ^q Ukm ki\" km\ a je vidět, že vnitřní sumu dostaneme jako koeficient u x" 1 v m-té mocnině řady U{x) = J2un^\- Proto je ÍH'-'iEi.oM" m>0 a tedy U{x) = e x U (x) = Pro dokončení výpočtu budeme potřebovat tvzení, které uvedeme bez důkazu. Definice Zobecněnou exponenciální mocninnou řadou £t{x) nazýváme řadu £t(x) = Y^{tk + I)*"1 k>0 k\ □ s - = ■€. -o<\(y Pro dokončení výpočtu budeme potřebovat tvzení, které uvedeme bez důkazu. Definice Zobecněnou exponenciální mocninnou řadou £t{x) nazýváme řadu £t(x) = Y^{tk + I)*"1 k>0 k\ Snadno je vidět, že £q = ex, dále označujeme £{x) = £\{x). a S - = -E -0a*0 Pro dokončeni výpočtu budeme potřebovat tvzení, které uvedeme bez důkazu. Definice Zobecněnou exponenciální mocninnou řadou £t{x) nazýváme řadu k\' et{x) = Y,{tk + i)k-lX k>0 Snadno je vidět, že £q = ex, dále označujeme £{x) = £\{x). Fakt: In £t{x) = x ■ £t{x), tj. spec. £(x) = ex£W . Srovnáním tohoto vztahu s výše uvedeným U(x) = exU^ vidíme, že U{x)=x£{x). Pro dokončeni výpočtu budeme potřebovat tvzení, které uvedeme bez důkazu. Definice Zobecněnou exponenciální mocninnou řadou £t{x) nazýváme řadu £t(x) = Y^{tk + I)*"1 k>0 k\ Snadno je vidět, že £q = ex, dále označujeme £{x) = £\{x). Fakt: In £t{x) = x ■ £t{x), tj. spec. £(x) = ex£W . Srovnáním tohoto vztahu s výše uvedeným U(x) = exU^ vidíme, že U{x)=x£{x). Proto Un n\ tn = -f = -[xn]U(x) = {n- l)\[xn-l\S{x) = n n-2