Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo oooo Matematika IV - 10. týden Příklady řešení rekurencí Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2017 □ S Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo oooo Obsah 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 ooooo oooooooo oooo 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. □ g = Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo oooo 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. Binární stromy a Catalanova čísla ooooo Caleyho vztah pro počet stromů oooooooo Rekurzivně propojené posloupnosti oooo Plán prednášky Q Binární stromy a Catalanova čísla 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 = 1, bi = 1, b2 = 2, b3 = 5. 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 = 1, bi = 1, b2 = 2, b3 = 5. Dělením problému na levý a pravý strom dostaneme pro n > 1 bn = b0bn-i + bibn-2 H-----h bn-ib0. -írnJ^ < >• -E O Q, O 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 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: b0 = 1, bi = 1, b2 = 2, b3 = 5. bobn-i + bibn-2 H-----h bn-ib0. 0 = 0]x" = n n,k n,k = E^X" (li bn-k-lXn~k J + 1 = = bkxk{xB{x)) + 1 = 6(x) • xB(x) + 1. k Pravá strana rekurence na prvním řádku je koeficientem u xn_1 v součinu B(x) • B(x), tj. členem u xn v xB(x)2. Je tedy xB(x)2 vytvořující po tutéž posloupnost jako B{x) s výjimkou prvního členu u x . 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 6(x) = xB(x)2 + 1 B(x): 2x 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) + 1 pro Znaménko + ale nepřichází v úvahu, protože pak by pro x 0+ 6(x) měla limitu oo, 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. S(x): B(x) 1 ± VI - 4x 2x B(x) 1 - y/l-Ax 2x = 1 OnO Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooo»o oooooooo oooo Rozvoj získáme pomocí zobecněné binomické věty d - **>1/2 = E T <-4*>' =1+E h U i) (-4x) /c>0 V 7 k>l v a po vydělení 1 — Vl 4x výrazem 2x dostaneme ew=EK*-i)(-4^"1 = /c>l V 7 ^ /-l/2\ (~4x)" = /2n\ _x^_ Literatura Binární stromy a Catalanova čísla oooo* Caleyho vztah pro počet stromů oooooooo Rekurzivně propojené posloupnosti oooo Catalanova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = (2nn). 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 Catalanova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = (2nn). 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 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 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 • 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 čí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 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 • 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 (r? lidí má 5korunu a m lOkorunu, lístek stojí 5 Kč.), že nezásobená pokladna může vždy vrátit čí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 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 • 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 (r? lidí má 5korunu a m lOkorunu, lístek stojí 5 Kč.), že nezásobená pokladna může vždy vrátit o počet korektně ozávorkovaných výrazů složených z levých a pravých závorek čí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 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 • 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 (r? lidí má 5korunu a m lOkorunu, lístek stojí 5 Kč.), že nezásobená pokladna může vždy vrátit o 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 (r? + 2)-úhelníku. čísel. Binární stromy a Catalanova čísla ooooo Caleyho vztah pro počet stromů oooooooo Rekurzivně propojené posloupnosti oooo Plán prednášky Q Caleyho vztah pro počet stromů Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 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. xn n\ 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 xn 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é posloupnosti 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. X n n>0 n\ 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é. 1 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 xn 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é 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 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í (a/ + 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í (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. 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í (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. o Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, a2, a3,...), tj. derivování odpovídá posuvu doleva o jedno místo . -írnJ^ < >• -E O Q, O 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í (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. o 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í a(t) dt vytvořuje posloupnost (0, ao, ai, a2, a3,...), tj. odpovídá posuvu doprava o jedno m ísto. -írnJ^ < >• -E O Q, O 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í (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. o 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, 33,...), tj. odpovídá posuvu doprava o jedno m ísto. • Součin vytvořujících funkcí vytvořuje posloupnost se členy Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti OOOOO OO0OOOOO oooo 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íc vytvořujících funkcí. 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 ti = t2 = 1, t3 = 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). Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti OOOOO OOO0OOOO 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 OOO0OOOO 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 /ciH-----\-km=n-l ki\---km\ m □ g = 1 O °nO Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti OOOOO OOO0OOOO 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 /ciH-----\-km=n-l ki\---km\ m Např. pro n = 4 máme U — 3ŕ3 + 6ŕiŕ2 + t\. □ S - 1 O Q.O Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti OOOOO OOO0OOOO 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 El v-^ (r?-l)! r }^ T~\-1—\kl " ' km • • • • tkm m\ k\ \ • • • km\ m>0 /ciH-----\-km=n—l Např. pro n = 4 máme U — 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\ Z—/ ml Z—/ n\ ^—' m\ ^—' k\\ km\ m>0 ki~\-----\-km=n—l a je vidět, že vnitřní sumu dostaneme jako koeficient u x n-1 v rn-té mocnině řady U{x) — ^ unK □ s Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti OOOOO 0000*000 oooo Dostáváme pro n > 1 un _ 1 nl ^—-/ ml ^—-/ m n\ m\ k\\ km\ m>0 k\-\-----\-km=n—l a je vidět, že vnitřní sumu dostaneme jako koeficient u x v m-té mocnině řady U(x) — ^ un^\- Proto je n-1 n\ m\ m>0 a tedy U{x) =xe 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 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 é:r(x) = ^(ř/c + i)fc-1^ /c>0 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 £t(x) = J2(tk + l)k-1 x k>0 k\ Snadno je vidět, že £o = 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). 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 x k>0 k\ Snadno je vidět, že £o = 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 = — = -[xn]U(x) = (n - l)l[xn-ľ]S{x) = nn~2. n n Literatura Binární stromy a Catalanova čísla ooooo Caleyho vztah pro počet stromů OOOOOO0O Rekurzivně propojené posloupnosti oooo 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: Literatura Binární stromy a Catalanova čísla ooooo Caleyho vztah pro počet stromů OOOOOO0O Rekurzivně propojené posloupnosti oooo 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) — J2n>ignxn splňuje vztah x = f(g{x)), kde f(0) = 0, f'(0) ^ 0, pak g" = -n[u ]{iur) n 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 U{x) = xe°W, tj. U(x) splňuje vztah x = f{U(x)), kde Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů OOOOO 0000000« Rekurzivně propojené posloupnosti oooo Alternativní závěr výpočtu Řešíme U{x) — xeu(x\ tj. U{x) splňuje vztah x = f(U(x)), kde f (u) = -17. Odtud z Lagrangeovy formule 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 U{x) = xe°W, tj. U(x) splňuje vztah x = f{U(x)), kde f(u) = -17. Odtud z Lagrangeovy formule [xn]U{x) = -[un-1] n 1 1 nn_1 = ±\un-l] un = - n1 J n(n-l)! n n-l Protože ^ = [xn]U(x), dostáváme odtud ŕ — Hr — n""2 L n — n — n Binární stromy a Catalanova čísla ooooo Caleyho vztah pro počet stromů oooooooo Rekurzivně propojené posloupnosti oooo Plán prednášky Q Rekurzivně propojené posloupnosti 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í. 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, C3 = O, 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? Ř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). Najdeme rekurzívní vztah - diskusí chování „na kraji" zjistíme, že cn = 2r„_i + cn_2, rn = cn_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. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo o«oo Ř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 Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo oo«o Řešení (pokr.) • Krok 1: c„ = 2r„_i + c„_2 + [n = 0], r„ = c„_i + r„_2. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo oo«o Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], ľ n — Cn-1 + ľn-2- • Krok 2: C(x) = 2xR(x) + x2C(x) + 1, R(x) = xC(x) + x2/?(x). Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo oo«o Ř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, R(x) = xC(x) + x2R(x) • Krok 3: C(x) = -ô-T i R(X) = l-4x2 + x4' v ' X 1 - 4x2 + x4' □ S Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti ooooo oooooooo oo«o Řešení (pokr.) • Krok 1: c„ = 2r„_i + c„_2 + [n = 0], rn = cn_i + r„_2. • Krok 2: C(x) = 2x/?(x) + x2C(x) + 1, /?(x) = xC(x) + x2/?(x). • Krok 3: C(X) = 1 - 4x2 + X4 » *M = 1_4xX2+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-\. 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 + y/Š a 2 - \/Š a již standardním způsobem obdržíme = (2 + VŠ)n (2 - y/3)n C2n~ 3-VŠ 3 + x/3 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 + V3 a 2 — V3 a již standardním způsobem obdržíme = (2 + VŠ)n (2 - VŠ)n 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 02 n = (2 + VŠ)n Např. c20 = 413403.