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 • 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. 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) . 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. Řešení (pokr.) 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 • 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 +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. 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. • 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: 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 = 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í) TT^ + Eff-i)-^). k>l v 7 x2k. Odtud, protože ^ xn -, , 1 + 2x - Vl + 4x2 ^g„- = G(x) =------------------------, máme g2k+i = 0 a ^2/c = (-l)fc \^kkZl) ■ W\ = (-l)k • (2/c)! ■ Q_1; 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. 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 "k! ukir 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\ 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