Diskrétní matematika - 12. týden Příklady řešení rekurencí Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2020 Obsah přednášky Doporučené zdroje • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. Doporučené zdroje • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. • Donald E. Knuth, The Art Of Computer Programming. • Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994. Plán přednášky S využitím standardních vytvořujících funkcí určíme formuli pro počet bn tzv. pěstovaných binárních stromů na n vrcholech, které je pro naše účely možné definovat jako kořen s uspořádanou dvojicí [levý binární podstrom, pravý binární podstrom]. S využitím standardních vytvořujících funkcí určíme formuli pro počet bn tzv. pěstovaných binárních stromů na n vrcholech, které je pro naše účely možné definovat jako kořen s uspořádanou dvojicí [levý binární podstrom, pravý binární podstrom]. Prozkoumáním případů pro malá n vidíme, že bo = l.£>i = 1, £>2 = 2, £>3 = 5. S využitím standardních vytvořujících funkcí určíme formuli pro počet bn tzv. pěstovaných binárních stromů na n vrcholech, které je pro naše účely možné definovat jako kořen s uspořádanou dvojicí [levý binární podstrom, pravý binární podstrom]. Prozkoumáním případů pro malá n vidíme, že bo = 1, b\ — 1, £>2 = 2, £>3 = 5. Dělením problému na levý a pravý strom dostaneme pro n > 1 bn = b0bn-i + b\bn-2 H-----V bn-ib0. S využitím standardních vytvořujících funkcí určíme formuli pro počet bn tzv. pěstovaných binárních stromů na n vrcholech, které je pro naše účely možné definovat jako kořen s uspořádanou dvojicí [levý binární podstrom, pravý binární podstrom]. Prozkoumáním případů pro malá n vidíme, že Dělením problému na levý a pravý strom dostaneme pro n > 1 Vidíme, že jde vlastně o konvoluci posloupností. Vztah upravíme, aby platil pro všechna n £ A/q: bo = l.£>i = 1, £>2 = 2, £>3 = 5. b bobn-i + bibn-2 H-----h bn-ib0. 0 = = n n,k n,k = 5>X/C (^bn^^-^j +1 = = bkxk(xB(x)) + 1 = B(x) • xB(x) + 1. k Pravá strana rekurence na prvním řádku je koeficientem u xn v součinu B(x) • B(x), tj. členem u xn v xB(x)2. Je tedy x6(x)2 vytvořující po tutéž posloupnost jako 6(x) s výjimkou prvního členu u x°. V kroku 3 řešíme kvadratickou rovnici 6(x) = xB(x)2 + 1 pro B{x): DX = -. ^ ; 2x V kroku 3 řešíme kvadratickou rovnici B(x) = xB(x) + 1 pro Znaménko + ale nepřichází v úvahu, protože pak by pro x —>> 0+ 6(x) měla limitu oc, zatímco vytvořující funkce pro naši posloupnost musí mít v 0 hodnotu bo = 1. Naopak pro znaménko — to tak dostaneme. Pro vytvořující funkci B(x) tedy platí Zbývá už pouze krok 4, tedy rozvinout B(x) do mocninné řady. B(x): B(x) 1 ± VI -4x 2x B(x) 1 - y/1 -4x 2x Rozvoj získáme pomocí zobecněné binomické věty d - 4*>1/2 = E T <-4*>' =1+E i U í) (-4x) /c>0 V 7 k>l v a po vydělení 1 — Vl 4x výrazem 2x dostaneme /c>l V 7 ^ /-l/2\ (-4x)" = y, Í2n\ >0 Q,o Cata la nova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = 7^3 (2^)- 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 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 monotónních cest z [0,0] do [r?, n] podél stran jednotkových čtverců, které nepřekročí diagonálu vrcholech je roven Dokázali jsme, že počet binárních pěstovaných stromů na n 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 monotónních cest z [0,0] do [r?, n] podél stran jednotkových čtverců, které nepřekročí diagonálu o počet slov délky 2n obsahujících n znaků X a Y takových, že žádný prefix slova neobsahuje více Y než X vrcholech je roven Dokázali jsme, že počet binárních pěstovaných stromů na n 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 monotónních cest z [0,0] do [r?, n] podél stran jednotkových čtverců, které nepřekročí diagonálu o počet slov délky 2n obsahujících n znaků X a Y takových, že žádný prefix slova neobsahuje více Y než X 9 podobně takové fronty u pokladny (n lidí má 5korunu a m lOkorunu, lístek stojí 5 Kč.), že nezásobená pokladna může vždy vrátit vrcholech je roven Dokázali jsme, že počet binárních pěstovaných stromů na n 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 monotónních cest z [0,0] do [r?, n] podél stran jednotkových čtverců, které nepřekročí diagonálu o počet slov délky 2n obsahujících n znaků X a Y takových, že žádný prefix slova neobsahuje více Y než X 9 podobně takové fronty u pokladny (n lidí má 5korunu a m lOkorunu, lístek stojí 5 Kč.), že nezásobená pokladna může vždy vrátit • počet korektně ozávorkovaných výrazů složených z levých a pravých závorek vrcholech je roven Cata la nova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = 7^3 (2^)- 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 monotónních cest z [0,0] do [r?, n] podél stran jednotkových čtverců, které nepřekročí diagonálu o počet slov délky 2n obsahujících n znaků X a Y takových, že žádný prefix slova neobsahuje více Y než X 9 podobně takové fronty u pokladny (n lidí má 5korunu a m lOkorunu, lístek stojí 5 Kč.), že nezásobená pokladna může vždy vrátit • počet korektně ozávorkovaných výrazů složených z levých a pravých závorek • počet různých triangulací konvexního (n + 2)-úhelníku. Plán přednášky 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í varianty1. xn n>0 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 x11 hraje n~x), ale těmi se zde zabývat nebudeme. Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciální varianty1. 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,...). V zápětí v důkazu Cayleyho věty uvidíme, že je použití exponenciálních vytvořujících funkcí výhodné. 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 x11 hraje n~x), ale těmi se zde zabývat nebudeme. n>0 Opět standardním operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami (coby exponenciálními vytvořujícími funkcemi): Opět standardním operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami (coby exponenciálními vytvořujícími funkcemi): • Sčítání (a/ + b\) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. Opět standardním operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami (coby exponenciálními vytvořujícími funkcemi): • Sčítání (a; + 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. Opět standardním operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami (coby exponenciálními vytvořujícími funkcemi): • Sčítání (a; + 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. • Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, a2, a3,...), tj. derivování odpovídá posuvu doleva o jedno místo . ^iS^ <■€.*■ < -E Opět standardním operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami (coby exponenciálními vytvořujícími funkcemi): • Sčítání (a; + 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. • Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, a2, a3,...), tj. derivování odpovídá posuvu doleva o jedno místo . • Integrování JQX a(t) dt vytvořuje posloupnost (0, an, ai, a2, a3,...), tj. odpovídá posuvu doprava o jedno místo. ^iS^ <■€.*■ < -E >0 Q,o Opět standardním operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami (coby exponenciálními vytvořujícími funkcemi): • Sčítání (a; + 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. • Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, a2, a3,...), tj. derivování odpovídá posuvu doleva o jedno místo . • Integrování JQX a(t) dt vytvořuje posloupnost (0, ao, ai, a2, a3,...), tj. odpovídá posuvu doprava o jedno místo. Součin vytvořujících funkcí vytvořuje posloupnost se členy Cayleyho formule Cayleyho formule je vztah z kombinatorické teorie grafů, který udává, že počet stromů (tj. grafů, v nichž jsou libovolné dva vrcholy spojené právě jednou cestou) na n vrcholech je tv(Kn) = nn~2. Dokážeme tento výsledek pomocí exponenciálních vytvořujících funkcí. Cayleyho formule Cayleyho formule je vztah z kombinatorické teorie grafů, který udává, že počet stromů (tj. grafů, v nichž jsou libovolné dva vrcholy spojené právě jednou cestou) na n vrcholech je tv(Kn) = nn~2. Dokážeme tento výsledek pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = tv(Kn). Lze snadno spočítat, že t\ — t2 = 1, h — 3, U — 16. (Např. víme, že v případě stromů na 4 vrcholech musíme z (3) = 20 potenciálních grafů s právě 3 hranami odebrat ty možnosti, kde tyto hrany tvoří trojúhelník. Těch je ale právě (3) = 4). ^iS^ <■€.*■ < -E 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í. 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 El v-^ (r?-l)! ^ Z. kí\...kmikl"'km'tkí"'tk» m>0 /ciH-----|-/cm=n—1 >0 Q,o 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 El v-^ (r?-l)! ^ Z. kí\...kmikl"'km'tkí"'tk» m>0 /ciH-----|-/cm=n—1 Např. pro n = 4 máme £4 = 3r3 + 6ŕiŕ2 + th < □ ► < [3P ► < -E ► < -E 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 El v-^ (r?-l)! ^ Z. kí\...kmikl"'km'tkí"'tk» m>0 /ciH-----|-/cm=n—1 Např. pro n = 4 máme £4 = 3r3 + 6ŕiŕ2 + . Ošklivě vypadající rekurenci zjednodušíme substitucí un = r?rn (uvědomte si přitom, že un udává počet tzv. kořenových stromů). Dostáváme pro n > 1 _ Uk±_ ukm n\~ ^ m\ ^ ki\"' km\ m>0 /ciH-----\-km=n—l a je vidět, že vnitřní sumu dostaneme jako koeficient u xn_1 v m-té mocnině řady U(x) — ^ un^\- Dostáváme pro n > 1 un _ 1 n\ Z—/ ml Z—/ uk1 ukm n\ ^-^ m\ ^-^ k\\ km\ m>0 /ciH-----\-km=n—l a je vidět, že vnitřní sumu dostaneme jako koeficient u xn 1 v m-té mocnině řady U(x) = E un^- Proto Je n! 1 1 ^ m\ m>0 a tedy U(x) = xe < □ ► < [3P ► < -E ► < -E >0 Q,o Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. r Definice Zobecněnou exponenciální mocninnou řadou £t{x) nazýváme řadu St(x) -- k>0 Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice _1 Zobecněnou exponenciální mocninnou řadou £t{x) nazýváme řadu €t{x) - = S>+i)*-i£. k>0 Snadno je vidět, že £q = ex, dále označujeme £{x) = £\{x). Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice _1 Zobecněnou exponenciální mocninnou řadou £t{x) nazýváme řadu €t{x) - = S>+i)*-i£. k>0 Snadno je vidět, že £q = ex, dále označujeme £{x) = £\{x). Fakt: In Et(x) = x • £t(x), tj. spec. £{x) = exS^ . Srovnáním tohoto vztahu s výše uvedeným U{x) — xe^x' vidíme, že U{x) — x£[x). >0 Q,o Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice _1 Zobecněnou exponenciální mocninnou řadou £t{x) nazýváme řadu €t{x) - = S>+i)*-i£. k>0 Snadno je vidět, že £q = ex, dále označujeme £{x) = £\{x). Fakt: In Et(x) = x • £t(x), tj. spec. £{x) = exS^ . Srovnáním tohoto vztahu s výše uvedeným U{x) — xe^x' vidíme, že U{x) — x£[x). Proto tn = ^ = ^ixn]U(x) = („- l)![x""VW = n Alternativní závěr výpočtu Pokud vám přišel závěr výpočtu příliš umělý, zkusme to ještě jednou, s využitím tzv. Lagrangeovy inverzní formule: Alternativní závěr výpočtu Pokud vám přišel závěr výpočtu příliš umělý, zkusme to ještě jednou, s využitím tzv. Lagrangeovy inverzní formule: Pokud vytvořující funkce g(x) — X)n>i SnXn splňuje vztah x = f(g{x)), kde f(0) = 0, f'(0) i- 0, pak Alternativní závěr výpočtu Řešíme U{x) = xeu(x\ tj. U{x) splňuje vztah x = ŕ((V(x)), kde Alternativní závěr výpočtu Řešíme U{x) = xeu(x\ tj. U{x) splňuje vztah x = ŕ((V(x)), kde f (u) = -17. Odtud z Lagrangeovy formule [x"](}(x) = - K"1] / 17 ^ rr " \u/eu7 1 1 nn~l nn~l _ _[ n-lj = 1 n _ ^_ n1 J n(n-l)! n! Alternativní závěr výpočtu Řešíme U{x) = xeu(x\ tj. U{x) splňuje vztah x = ŕ((V(x)), kde f (u) = -17. Odtud z Lagrangeovy formule [x"](}(x) = - K"1] / 17 ^ rr " \u/eu7 1 1 nn~l nn~l _ _[ n-lj = 1 n _ ^_ n1 J n(n-l)! n! Protože = [xn](y(x), dostáváme odtud ŕ — Hr — nn~2 L n — n — n Plán přednášky 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í. Kolika způsoby můžeme pokrýt (nerozlíšenými) kostkami domina obdélník 3 x n? 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? Řešení Snadno zjistíme, že c\ — 0, C2 = 3, C3 = 0, dále klademe co = 1 (nejde jen o konvenci, má to svou logiku). 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 + cn_2, rn = c_i + rn_2, r0 = 0, r\ = 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 1 0 3 0 11 0 41 0 rn 0 1 0 4 0 15 0 56 ^iS^ <■€.*■ < -E Řešení (pokr.) Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = cn_x + r„_2. Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], • Krok 2: C(x) = 2x/?(x) + x2C(x) + 1, /?(x) = xC(x)+x2/?(x). Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = cn_x + r„_2. • Krok 2: C(x) = 2xR(x) + x2C(x) + 1, /?(x) = xC(x) + x2R(x) • Krok 3: C(x) = X 1 - 4x2 + x4 ' >0 Q,o Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = cn_x + r„_2. • Krok 2: C(x) = 2xR(x) + x2C(x) + 1, /?(x) = xC(x) + x2R(x) • Krok 3: C(x) = X 1 - 4x2 + x4 ' • 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 C2n = dn — dn-\. < □ ► < [3P ► < -E ► < -E Řešení (závěr) Kořeny 1 — 4x + x2 jsou 2 + V3 a 2 — a již standardním způsobem obdržíme (2 + y/3)n C2n= 3-VŠ (2-V3)" 3 + VŠ < □ ► < [3P ► < -E ► < -E Řešení (závěr) Kořeny 1 — 4x + x2 jsou 2 + V3 a 2 — V3 a již standardním způsobem obdržíme = (2 + VŠ)n (2 - y/3)n C2n 3 - y/3 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 C2n = (2 + VŠ)n 3-VŠ Např. c20 = 413403.