Literatura Binární stromy a Catalano1 /a čísla Caleyho vztah pro počet stromů Rekurzivi iě propojené posloupnosti ooooo oooooooo oooo Matematika IV - 10. týden Příklady řešení rekurencí Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2014 Literatura Binární stromy a Catalano1 /a čísla Caleyho vztah pro počet stromů Rekurzivi iě propojené posloupnosti ooooo oooooooo oooo Q Binární stromy a Catalanova čísla Q| Caleyho vztah pro počet stromů Q Rekurzivně propojené posloupnosti Literatura Binární stromy a Catalano1 /a čísla Caleyho vztah pro počet stromů Rekurzivi iě propojené posloupnosti ooooo oooooooo oooo • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo oooo • 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. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo oooo Plán přednášky Q Binární stromy a Catalanova čísla Q Caleyho vztah pro počet stromů Q Rekurzivně propojené posloupnosti Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti •oooo oooooooo oooo 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]. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti •oooo oooooooo oooo 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 b0 = l,b1 = l,bz = 2,b3 = 5. Literatura Binární stromy a Catalanova čís la Caleyho vztah pro počet stromů Rekurzivi iě propojené posloupnosti •oooo oooooooo OOOO 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,b1 = l,b2 = 2,b3 = 5. Dělením problému na levý a pravý strom dostaneme pro n > 1 bn = bobn-! + hbn-2 H-----r- £n-iV Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti •oooo oooooooo oooo 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 b0 = l,b1 = l,bz = 2,b3 = 5. Dělením problému na levý a pravý strom dostaneme pro n > 1 bn = bobn-! + hbn-2 H-----h bn-lV Vidíme, že jde vlastně o konvoluci posloupností. Vztah upravíme, aby platil pro všechna n G Nq: bn = ^2 bkbn-k-i + [n = 0]. 0 = 0]X" = n n,k n,k = bkxk(xB(x)) + 1 = B(x) ■ xB(x) + 1. k Pravá strana rekurence na prvním řádku je koeficientem u x" v součinu B(x) ■ B(x), tj. členem u x" v x6(x)2. Je tedy x6(x)2 vytvořující po tutéž posloupnost jako B(x) s výjimkou prvního členu u x°. Literatura Binární stromy a Catalano' ✓a čísla Caleyho vztah pro počet stromů Rekurzivi iě propojené posloupnosti oo»oo oooooooo oooo V kroku 3 řešíme kvadratickou rovnici B(x) = xB(x)2 + 1 pro B(x): B(x) = i±^E^. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti oo»oo oooooooo oooo V kroku 3 řešíme kvadratickou rovnici B(x) = xB(x)2 + 1 pro 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 £>o = 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 - VI - 4x 2x Literatura Binární stromy a Catalano' ✓a čísla Caleyho vztah pro počet stromů Rekurzivi iě propojené posloupnosti ooo»o oooooooo oooo Rozvoj získáme pomocí zobecněné binomické věty k>0 v 7 k>l v a po vydělení 1 — y/l — 4x výrazem 2x dostaneme y. /-l/2\ (-4x)" = y. /2n\ x" n>0 V 7 n>0 V 7 Literatura Binární stromy a Catalano' ✓a čísla Caleyho vztah pro počet stromů Rekurzivi iě propojené posloupnosti OOOO* oooooooo OOOO 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. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti oooo* oooooooo oooo 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 [n, n] podél stran jednotkových čtverců, které nepřekročí diagonálu Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti oooo* oooooooo oooo 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 [n, n] podél stran jednotkových čtverců, které nepřekročí diagonálu • 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 Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti oooo* oooooooo oooo 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 [n, n] podél stran jednotkových čtverců, které nepřekročí diagonálu • 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 • 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 Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti oooo* oooooooo oooo 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 [n, n] podél stran jednotkových čtverců, které nepřekročí diagonálu • 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 • 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 Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti oooo* oooooooo oooo 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 [n, n] podél stran jednotkových čtverců, které nepřekročí diagonálu • 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 • 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. Literatura Binární stromy a Catalano1 /a čísla Caleyho vztah pro počet stromů Rekurzivi iě propojené posloupnosti ooooo oooooooo oooo Q Binární stromy a Catalanova čísla Q| Caleyho vztah pro počet stromů Q Rekurzivně propojené posloupnosti Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnost OOOOO »0000000 oooo í f u n kce Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciální varianty1. n>0 1Použí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. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnost OOOOO »0000000 oooo 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. n>0 Poznámka 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é. 1Použí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. Literatura Binární stromy a Catalanova čís la Caleyho vztah pro počet stromů Rekurzivi iě propojené posloupnosti ooooo o»oooooo oooo 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): Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo o»oooooo oooo 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í (af- + b,) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo o»oooooo oooo 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í (af- + 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. Literatura Binární stromy a Catalanova čís la Caleyho vztah pro počet stromů Rekurzivi iě propojené posloupnosti ooooo o»oooooo oooo 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í (af- + 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, 32, 33, • • •), tj. derivování odpovídá posuvu doleva o jedno místo . Literatura Binární stromy a Catalanova čís la Caleyho vztah pro počet stromů Rekurzivi iě propojené posloupnosti ooooo o»oooooo oooo 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í (af- + 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, 32, 33, • • •), tj. derivování odpovídá posuvu doleva o jedno místo . • Integrování f* s(ř) dř vytvořuje posloupnost (0, an, 3i, 32, 33, • • •), tj. odpovídá posuvu doprava o jedno místo. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo o»oooooo oooo 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í (af- + 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, 32, 33, • • •), tj. derivování odpovídá posuvu doleva o jedno místo . • Integrování f* s(ř) dř vytvořuje posloupnost (0, ao, 3i, 32, 33, • • •), tj. odpovídá posuvu doprava o jedno místo. • Součin vytvořujících funkcí vytvořuje posloupnost se členy i+j—n ■0 0.0 Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oo»ooooo oooo 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 K,(Kn) = nn~2. Dokážeme tento výsledek pomocí exponenciálních vytvořujících funkcí. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oo»ooooo oooo 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 K,(Kn) = nn~2. Dokážeme tento výsledek pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = n(Kn). Lze snadno spočítat, že t\ = t2 = 1, Í3 = 3, Í4 = 16. (Např. víme, že v případě stromů na 4 vrcholech musíme z (^) = 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ě (^) = 4). Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo ooo»oooo oooo 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í. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo ooo»oooo oooo 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 íriH-----\-km—n—l ki\---km\ m ' fyq tf 1 m>0 íriH-----\-km—n—l ki\---km\ ■m Např. pro n = 4 máme ŕ4 = 3ŕ3 + 6ŕiŕ2 + tf. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo ooo»oooo oooo 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 /qH-----Vkm=n-1 Např. pro n = 4 máme Í4 = 3ř3 + 6ŕiŕ2 + tf. Ošklivě vypadající rekurenci zjednodušíme substitucí un = ntn (uvědomte si přitom, že un udává počet tzv. kořenových stromů). Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooo^ooo oooo Dostáváme pro n > 1 n\~ Ľ m\ Ľ /ci! km\ m>0 k!-{-----Vkm=n-1 a je vidět, že vnitřní sumu dostaneme jako koeficient u x" v m-té mocnině řady U(x) = Yl u"7ír- Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooo^ooo oooo Dostáváme pro n > 1 "n n\ a je vidět, že vnitřní sumu dostaneme jako koeficient u x" v m-té mocnině řady U(x) = Yl u"7ír- Pr°t° je m>0 a tedy U{x) =xe°W. m>0 k!-{-----Vkm=n-1 Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo ooooo»oo oooo Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice Zobecněnou exponenciální mocninnou řadou £t{x) nazýváme řadu £t(x) = J2(tk + l) k>0 Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo ooooo»oo oooo Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice Zobecněnou exponenciální mocninnou řadou £t{x) nazýváme řadu £t(x) = J2(tk + l)k-1 k>0 k\ Snadno je vidět, že £q = ex, dále označujeme £(x) = £\{x). Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo ooooo»oo oooo Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice Zobecněnou exponenciální mocninnou řadou £t{x) nazýváme řadu 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) = xeyM vidíme, že U{x)=x£(x). Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo ooooo»oo oooo Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice Zobecněnou exponenciální mocninnou řadou £t{x) nazýváme řadu 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) = xeyM vidíme, že U{x)=x£(x). Proto tn = — = -[xn]U{x) = {n- íy.ix"-1^) = nn~2. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti OOOOO 000000*0 oooo Pokud vám přišel závěr výpočtu příliš umělý, zkusme to jednou, s využitím tzv. Lagrangeovy inverzní formule: Literatura Binární stromy a Catalano /a čísla Caleyho vztah pro počet stromů Rekurziv iě propojené posloupnost ooooo 000000*0 oooo 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) = J2n>i SnXn splňuje vztah kde f(0) = O, f'(0) + O, pak gn=n[u Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti OOOOO 0000000» oooo Alternativní závěr výpočtu Řešíme Ú(x) f(u) = 5- xeuW, tj. U{x) splňuje vztah x = f(U(x)), kde < □ ► 4 (5? ► 4 š ► < 5 ► Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo ooooooo* oooo Řešíme U(x) = xeu(x\ tj. U(x) splňuje vztah f(u) = -77. Odtud z Lagrangeovy formule [xn]U(x) = -[u"-1 n \u/eu 1 1 n"_1 -lu"-1] eun - n(n-l) Literatura Binární stromy a Catalano1 /a čísla Caleyho vztah pro počet stromů Rekurzivi iě propojené posloupnosti ooooo 0000000» oooo Řešíme U{x) =xeuW, tj. U{x) splňuje vztah x = f(U(x)), kde f(u) = -77. Odtud z Lagrangeovy formule [xn]U{x) = -[u"-1} 1 / \ " 1 r „_1, / U n \u/eu 1 1 nn-l nn-l n(n-l)\ n\ Protože ^ = [xn]U(x), dostáváme odtud t„ = = n"-2. " n Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 00000 oooooooo oooo Plán přednášky Q Binární stromy a Catalanova čísla Q Caleyho vztah pro počet stromů Q Rekurzivně propojené posloupnosti 4 S ► < -š ► ' - ► Literatura Binární stromy a Catalano1 /a čísla Caleyho vztah pro počet stromů Rekurzivi ně propojené posloupnosti ooooo oooooooo •ooo Někdy dokážeme snadno vyjádřit hledaný počet jen pomocí více vzájemně provázaných posloupností. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti OOOOO OOOOOOOO »000 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? Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti OOOOO OOOOOOOO »000 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\ = O, C2 = 3, cj = O, dále klademe cq = 1 (nejde jen o konvenci, má to svou logiku). Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti OOOOO OOOOOOOO »000 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\ = O, C2 = 3, cj = O, 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, = O, a = 1, kde rn je počet pokrytí obdélníku 3 x n, ze kterého jsme odstranili levý horní roh. Literatura Binární stromy a Catalano /a čísla Caleyho vztah pro počet stromů Rekurziv ně propojené posloupnosti ooooo oooooooo 0900 Ř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 Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo 00*0 Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = c„_i + r„_2- ■0 0.0 Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo 00*0 Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = c„_i + r„_2- • Krok 2: C(x) = 2xR{x) +x2C(x) + 1, /?(x) =xC(x) + x2/?(x). ■0 0.0 Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo 00*0 Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = c„_i + r„_2- • Krok 2: C(x) = 2xR{x) +x2C(x) + 1, /?(x) =xC(x) + x2/?(x). • Krok 3: C(X) = R{X) = l-4xX2+x^ ■0 0.0 Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo 00*0 Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], rn = c„_i + r„_2- • Krok 2: C(x) = 2xR{x) +x2C(x) + 1, /?(x) =xC(x) + x2/?(x). • Krok 3: C(X) = R{X) = l-4x2+x*- • 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. [x2n]C(x) = [x2n](l -x2)D(x2) = [x"](l -x)D(x), a tedy C2n = dn — dn-i. ■0 0.0 Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo ooo« Řešení (závěr) Kořeny 1 — 4x + x2 jsou 2 + VŠ a 2 — VŠ a již standardním způsobem obdržíme (2 + y/3)n C2n~ 3-V3 | (2-V3)" 3 + VŠ Literatura Binární stromy a Catalano /a čísla Caleyho vztah pro počet stromů Rekurziv ně propojené posloupnosti ooooo oooooooo ooo« Řešení (závěr) Kořeny 1 — 4x + x2 jsou 2 + \/3 a 2 — \/3 a již standardním způsobem obdržíme = (2 + y/3)n (2 - Všy C2n~ 3-VŠ 3 + VŠ 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-y/3 Např. c20 = 413403.