Diskrétní matematika - 11. týden Vytvořující funkce a re k u re n ce Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2024 Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O oooooooooo ooooo ooooooooo ooooo Obsah přednášky Q Řešení rekurencí Q Catalanova čísla Q Caleyho vztah pro počet stromů Q Rekurzivně propojené posloupnosti □ 13 Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti • oooooooooo ooooo ooooooooo ooooo 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. 1 1 O Q, O Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti • oooooooooo ooooo ooooooooo ooooo 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. 9 Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O »000000000 ooooo ooooooooo ooooo án přednášky v Řešení rekurencí Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o o»oooooooo ooooo ooooooooo ooooo Obecný postup Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí (a to nejen lineárních!). Tím je míněno vyjádření členu a^ jako funkci k. Č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 a^ na ostatních členech posloupnosti. Tento vztah musí platit pro všechna k 6 No (předpokládajíce a_i = a_2 = • • • = 0). Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o o»oooooooo ooooo ooooooooo ooooo Obecný postup Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí (a to nejen lineárních!). Tím je míněno vyjádření členu a^ jako funkci k. Č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 a^ na ostatních členech posloupnosti. Tento vztah musí platit pro všechna k £ No (předpokládajíce a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme xk a sečteme přes všechna k G No- Na jedné straně tak dostaneme J2k>o ak*k, c°ž je vytvořující funkce A(x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o o»oooooooo ooooo ooooooooo ooooo Obecný postup Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí (a to nejen lineárních!). Tím je míněno vyjádření členu a^ jako funkci k. Č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 a^ na ostatních členech posloupnosti. Tento vztah musí platit pro všechna k £ No (předpokládajíce a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme xk a sečteme přes všechna k G No- Na jedné straně tak dostaneme J2k>o ak*k, c°ž 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). Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o o»oooooooo ooooo ooooooooo ooooo Obecný postup Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí (a to nejen lineárních!). Tím je míněno vyjádření členu a^ jako funkci k. Č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 a^ na ostatních členech posloupnosti. Tento vztah musí platit pro všechna k £ No (předpokládajíce a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme xk a sečteme přes všechna k G No- Na jedné straně tak dostaneme J2k>o ak*k, c°ž 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 xk udává a/o tj. a^ = [x/c]>A(x) . Literatura v Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 OO0OOOOOOO ooooo ooooooooo OOOOO Příklad Reste rekurenci 3q = 0, ai = 1 ak = 5a/c_i - 6ak-2 Literatura v Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oo»ooooooo ooooo ooooooooo OOOOO Příklad Reste rekurenci 3o = 0, ai = 1 ak = 5a/c_i - 6a/c_2 • Krok 1: ak — ba^-i Ô3k-2 + [k = 1] □ s1 Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 OO0OOOOOOO OOOOO ooooooooo OOOOO Příklad Reste rekurencí 3o = 0, ai = 1 3k = 5a/<_i — 6a/c_2 • Krok 1: = 5a/(_i — 6a/<_2 + [/c = 1]. • Krok 2: /4(x) = 5x/4(x) - 6x2-4(x) + x. □ 13 = Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oo»ooooooo OOOOO ooooooooo OOOOO Příklad v Reste rekurencí 3q = 0, ai = 1 3k = 5a/c_i — 6a/c_2 • Krok 1: = 5a/c_i — 6a/c_2 + [/c = 1]. • Krok 2: /4(x) = 5xA(x) - 6x2A(x) + x. 9 Krok 3: A(x) = - x - 5x + 6x2 1 - 3x 1 - 2x >0 0,0 Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oo»ooooooo ooooo ooooooooo OOOOO Příklad v Reste rekurenci 3q = 0, ai = 1 3k = 5a/c_i — 6a/c_2 • Krok 1: • Krok 2: 9 Krok 3: x - 5x + 6x2 1 - 3x Krok 4: afc = 3k - 2k. 1 -2x >0 0,0 Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o ooo«oooooo ooooo ooooooooo ooooo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem F0 = 0, Fi = 1, Fk = Ffr_i + F*_2 pro /c > 2. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice (podrobně viz http: //is .muni. cz/th/41281/prif _d/disertace. pdf). Našim cílem bude (opět) najít formuli pro výpočet r?-tého členu posloupnosti. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o ooo«oooooo ooooo ooooooooo ooooo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem F0 = 0, Fi = 1, Fk = Ffr_i + F*_2 pro k>2. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice (podrobně viz http: //is .muni. cz/th/41281/prif _d/disertace. pdf). Našim cílem bude (opět) najít formuli pro výpočet r?-tého členu posloupnosti. Poznámka (Nejen) pro manipulace se sumami používají autoři Concrete mathematics velmi vhodné označení [logický predikát] - výraz je roven 1 v případě splnění predikátu, jinak 0. Např. [k = 1], [2\k] apod. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o ooo«oooooo ooooo ooooooooo ooooo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem F0 = 0, Fi = 1, Fk = Ffr_i + F*_2 pro k>2. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice (podrobně viz http: //is .muni. cz/th/41281/prif _d/disertace. pdf). Našim cílem bude (opět) najít formuli pro výpočet r?-tého členu posloupnosti. Poznámka (Nejen) pro manipulace se sumami používají autoři Concrete mathematics velmi vhodné označení [logický predikát] - výraz je roven 1 v případě splnění predikátu, jinak 0. Např. [k = 1], [2\k] apod. Pro vyjádření koeficientu u xk ve vytvořující funkci F(x) se pak často používá zápis [x/c]F(x). Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooo«ooooo ooooo ooooooooo ooooo Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Při podmínkách Fq = 0, F\ — 1 je to F(x) — xF(x) — x2F(x) = x. tedy x — X — Xz Našim cílem je tedy odvodit vztah pro k-tý člen posloupnosti. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooo«ooooo ooooo ooooooooo ooooo Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Při podmínkách Fq = 0, F\ — 1 je to F(x) — xF(x) — x2F(x) = x, a tedy x — x — xz Našim cílem je tedy odvodit vztah pro k-tý člen posloupnosti. Využijeme k tomu rozklad na parciální zlomky a dostaneme x A B + 1 — x — x2 1 — Ax 1 — fix' kde A, jsou kořeny ŕ2 — t — 1 a A, B vhodné konstanty odvozené z počátečních podmínek. Odtud už vcelku snadno vyjde Fk = A-\k + B-fik, jak to známe z dřívějška. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o ooooo»oooo ooooo ooooooooo ooooo Příklad - závěr S využitím počátečních podmínek dostáváme Fu = i + Vš i - Vš Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o ooooo»oooo ooooo ooooooooo ooooo Příklad - závěr S využitím počátečních podmínek dostáváme F u = 1 VŠ i + i - Vš Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Uvážíme-li navíc, že (1 — v5)/2 ~ —0.618, vidíme, že pro všechna přirozená čísla lze F^ snadno spočítat zaokrouhlením čísla 1 (1+V5\k ^ 2 ) ■ □ S Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o ooooo»oooo ooooo ooooooooo ooooo Příklad - závěr S využitím počátečních podmínek dostáváme F u = 1 VŠ i + i - Vš Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Uvážíme-li navíc, že (1 - VŠ)/2 « -0.618, vid íme, že pro všechna přirozená čísla lze Fk snadno spočítat zaokrouhlením čísla -^g(1+2v^)/c. Navíc je vidět, že lim^oo F^+i/F^ = A « 1.618, což je poměr známý jako zlatý řez - objevuje se již od antiky v architektuře, výtvarném umění i hudbě. □ s Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O 000000*000 ooooo ooooooooo ooooo Quicksort - analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): if L []: return [] retu rn qsort([x for x in L[l:] if x=L[0]]) Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O 000000*000 ooooo ooooooooo ooooo Quicksort - analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): if L []: return [] retu rn qsort([x for x in L[l:] if x=L[0]]) O Počet porovnání při rozdělení (divide): k — 1. O (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je /-tý největší, je p O Velikost tříděných polí ve fázi conquer: i — 1 a k — i. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O 000000*000 ooooo ooooooooo ooooo Quicksort - analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): if L []: return [] retu rn qsort([x for x in L[l:] if x=L[0]]) O Počet porovnání při rozdělení (divide): k — 1. O (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je /-tý největší, je p O Velikost tříděných polí ve fázi conquer: i — 1 a k — i. Pro střední hodnotu počtu porovnání tak dostáváme rekurentní vzta h: k 1 Ck = k-l + ^2~ (C/_i + Ck-i). Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O OOOOOOO0OO ooooo ooooooooo ooooo Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurencí k kCk = k(k - 1) + 2 O-i, C0 = Ci = O i=i pomocí uvedeného postupu. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O 0000000*00 ooooo ooooooooo ooooo Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurencí k kCk = k(k - 1) + 2 C-i, Q = Ci = O i=i pomocí uvedeného postupu. • E*>o kCkxk = E/c>o ~ l)xk + 2 £fc>o E?=i G_ix* Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O ooooooo»oo ooooo ooooooooo ooooo Vyřešme nyní rekurenci kCk = /c(/c-l) + 2^ C/_i, C0 = Ci = 0 /=i pomocí uvedeného postupu. • Efc>o k<=kxk = E/c>o k(k - l)xk + 2 Zk>0 E?=i C/_ 2x2 , ^xC(x) —X □ s Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O 0000000*00 ooooo ooooooooo ooooo Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurencí kCk = k(k - 1) + 2 C-i, C0 = Q = O i=i pomocí uvedeného postupu. • E/c>o kCkxk = E,>0 k(k - l)xk + 2 J2k>0 E?=i Q_ixfc .xC'(x) = ^ + 2$M • Vyřešíme tuto lineární diferenciální rovnici prvního řádu ((1-x)2C(x))' = £l a tedy c(x) = črbp(lnrb-x odkud konečně Ck = 2{k + l)(Hk+1 - 1) - 2k. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooo»o ooooo ooooooooo ooooo Ještě jeden příklad r Příklad 1 Vyřešte rekurenci 3Q = 3l = 1 an = an_i+2an_2 + (-l)'7 □ rS1 = l O 0,0 Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooo»o ooooo ooooooooo ooooo Vyřešte rekurenci 30 = 3i = 1 an = an_i+2an_2 + (-l)n Řešení Tato rekurence je opět jiného typu než dosud studované. Jako vždy neuškodí vypsání prvních několika členů posloupnosti (teď ale ani moc nepomůže, snad jen pro kontrolu správnosti výsledku).3 aNarozdíl od tvrzení v Concrete mathematics je již možné tuto posloupnost nalézt v The On-Line Encyclopedia of Integer Sequences. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 ooooooooo* OOOOO ooooooooo OOOOO Řešení (pokr.) Krok 1: a„ = a„_i + 2a„_2 + (-!)"[" > 0] + [n = 1]. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 ooooooooo* OOOOO ooooooooo OOOOO Řešení (pokr.) • Krok 1: an = a„_i + 2a„_2 + (-l)n[n > 0] + [n = 1]. • Krok 2: A(x) = xA(x) + 2x2A(x) + + x. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 ooooooooo* ooooo ooooooooo OOOOO Řešení (pokr.) • Krok 1: an = a„_i + 2a„_2 + (-1)> > 0] + [n = 1]. • Krok 2: A(x) = xA(x) + 2x2A(x) + + x. • Krok 3: A(x)- 1 + x + x2 A[X)- (l-2x)(l+x)2- Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 ooooooooo* OOOOO ooooooooo OOOOO Řešení (pokr.) • Krok 1: an = a„_i + 2a„_2 + (-1)> > 0] + [n = 1]. • Krok 2: A(x) = xA(x) + 2x2A(x) + + x. • Krok 3: A(x)- 1 + x + x2 A[X)- (l-2x)(l+x)2- • Krok 4: an = Z2" + (i „+§)(-!)". Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O OOOOOOOOOO »0000 ooooooooo ooooo án přednášky Q Catalanova čísla Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo o»ooo ooooooooo ooooo Binární stromy a Catalanova čísla S využitím vytvořujících funkcí určíme formuli pro počet bn 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 Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo o»ooo ooooooooo ooooo Binární stromy a Catalanova čísla S využitím vytvořujících funkcí určíme formuli pro počet bn 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, ze bo = l.£>i = 1, £>2 = 2, £>3 = 5. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo o»ooo ooooooooo ooooo Binární stromy a Catalanova čísla S využitím vytvořujících funkcí určíme formuli pro počet bn 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, ze bo = 1, b\ — 1, £>2 = 2, £>3 = 5. Snadno nahlédneme, že pro n > 1 vyhovuje bn rekurentní formuli bn = b0bn-i + b\bn-2 H-----V bn-ib0. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo o»ooo ooooooooo ooooo Binární stromy a Catalanova čísla S využitím vytvořujících funkcí určíme formuli pro počet bn 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, ze bo = 1, b\ — 1, £>2 = 2, £>3 = 5. Snadno nahlédneme, že pro n > 1 vyhovuje bn rekurentní formuli bn = b0bn-i + b\bn-2 H-----V bn-ib0. Vidíme, že jde vlastně o konvoluci posloupností. Vztah upravíme, aby platil pro všechna n G Nq\ bn = b0bn-i + bibn-2 H-----h bn-ib0 + [n = 0]. Tím máme hotov krok 1. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo oo»oo ooooooooo ooooo bn = bobn-x + bibn-2 H-----h bn-i^o + [n = 0]. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo oo»oo ooooooooo OOOOO b„ = bobn-x + bibn-2 H-----h bn-ibQ + [n = 0]. V kroku 2 vynásobíme obě strany x" a sečteme. Je-li B(x) odpovídající vytvořující funkce, pak dostaneme: B(x) = x ■ B(x) ■ B(x) + 1. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo ooo»o ooooooooo OOOOO V kroku 3 řešíme kvadratickou rovnici B(x) = xB(x)2 + 1 pro B{x): B(x) = 1 ± VI -4x 2x □ S Literatura v Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O oooooooooo ooo»o ooooooooo OOOOO V kroku 3 řešíme kvadratickou rovnici B(x) = xB(x)2 + 1 pro fi(x): B(x) =-Yx-• 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. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo ooo»o ooooooooo ooooo V kroku 3 řešíme kvadratickou rovnici B(x) = xB(x)2 + 1 pro S(x): S(x) = 1 ± VI - 4x 2x 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. Zbývá už pouze krok 4, tedy rozvinout 6(x) do mocninné řady. Rozvoj získáme pomocí zobecněné binomické věty (1 - 4x)V2 = £ ( V2) (_4x)fc = 1 + £ i- ( ,. , (_4x) /c>0 v y k>l a po vydělení 1 — \fl — 4x výrazem 2x dostaneme E1/-1/2 2/cV/c-l fi(x) = /C>1 E n>0 k\k- -l/2\ (-4x)" n / n + 1 E n>0 2n x n J n + 1 Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo oooo» ooooooooo ooooo 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. □ s Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo oooo« ooooooooo ooooo Catalanova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = j^i2^) - 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: 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 Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo oooo« ooooooooo ooooo Catalanova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = j^i2^) - 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: 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 (5koruny a lOkoruny), že nezásobená pokladna může vždy vrátit Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo oooo« ooooooooo ooooo Catalanova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = j^i2^) - 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: 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 (5koruny a lOkoruny), ž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 Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo oooo« ooooooooo ooooo Catalanova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = j^i2^) - 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: 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 (5koruny a lOkoruny), ž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 9 počet monotónních cest z [0,0] do [r?, n] podél stran jednotkových čtverců, které nepřekročí diagonálu Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo oooo« ooooooooo ooooo Catalanova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = j^i2^) - 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: 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 (5koruny a lOkoruny), ž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 9 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 různých triangulací konvexního (r? + 2)-úhelníku. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O OOOOOOOOOO OOOOO «00000000 ooooo án přednášky Q Caleyho vztah pro počet stromů Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo ooooo o«ooooooo ooooo 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í. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo ooooo o«ooooooo ooooo 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). Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo OOOOO oo»oooooo OOOOO Rekurentní vztah získáme tak, že zafixujeme jeden vrchol vq a možné případy rozdělíme podle počtu komponent v grafu, který dostaneme z koster Kn tak, že odstraníme vrchol vq a hrany s ním incidentní. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo OOOOO oo»oooooo OOOOO Rekurentní vztah získáme tak, že zafixujeme jeden vrchol vq a možné případy rozdělíme podle počtu komponent v grafu, který dostaneme z koster Kn tak, že odstraníme vrchol vq a hrany s ním incidentní. Kvůli jednoduchosti argumentu budeme rekurzivně vyjadřovat počet tzv. kořenových stromů, tj. stromů s vybraným vrcholem, kterému říkáme kořen. Jejich počet je zjevně un = ntn. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo ooooo oo»oooooo OOOOO Rekurentní vztah získáme tak, že zafixujeme jeden vrchol vq a možné případy rozdělíme podle počtu komponent v grafu, který dostaneme z koster Kn tak, že odstraníme vrchol vq a hrany s ním incidentní. Kvůli jednoduchosti argumentu budeme rekurzivně vyjadřovat počet tzv. kořenových stromů, tj. stromů s vybraným vrcholem, kterému říkáme kořen. Jejich počet je zjevně un = ntn. Uvažme kořenový strom na n vrcholech s kořenem vq. Odstraněním tohoto vrcholu dostaneme disjunktní sjednocení několika stromů (tzv. les), přičemž každý strom, tj. každá z komponent, má vybraný kořen vn konkrétně soused vq v původním stromu. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo ooooo oo»oooooo OOOOO Rekurentní vztah získáme tak, že zafixujeme jeden vrchol vq a možné případy rozdělíme podle počtu komponent v grafu, který dostaneme z koster Kn tak, že odstraníme vrchol vq a hrany s ním incidentní. Kvůli jednoduchosti argumentu budeme rekurzivně vyjadřovat počet tzv. kořenových stromů, tj. stromů s vybraným vrcholem, kterému říkáme kořen. Jejich počet je zjevně un = ntn. Uvažme kořenový strom na n vrcholech s kořenem vq. Odstraněním tohoto vrcholu dostaneme disjunktní sjednocení několika stromů (tzv. les), přičemž každý strom, tj. každá z komponent, má vybraný kořen v\, konkrétně soused vq v původním stromu. Naopak, pokud zvolíme vrchol vq, rozložíme množinu zbylých vrcholů na několik neprázdných disjunktních částí - označme jejich počet m - a na každé vybereme strukturu kořenového stromu s kořenem v\, dostaneme přidáním hran vo^i, • • • ? vovm kořenový strom. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo ooooo OOO^OOOOO OOOOO Proto pro n > 1 platí u° = E ér E n I m m\ ^ l\k1\...km\Ukl"'Uk' m>0 l+/ci+---+/cm=n (množinu všech vrcholů obarvíme barvami následovně: jeden vrchol vq barvou 0, dále k\ vrcholů barvou /, pro každé /; faktor zaručí, že nezáleží na pořadí barev 1,..., m, takže se vskutku jedná o rozklad; v komponentě každé barvy zvolíme kořenový strom). Proto pro n > 1 platí m>0 ' l+/ciH-----\-km=n Y— y Wkx\---km\ u k! ■ ■ ■ ukl m (množinu všech vrcholů obarvíme barvami následovně: jeden vrchol vq barvou 0, dále k\ vrcholů barvou /, pro každé /; faktor zaručí, že nezáleží na pořadí barev 1,..., m, takže se vskutku jedná o rozklad; v komponentě každé barvy zvolíme kořenový strom). Vydělením n\ pak rekurenci výrazně zjednodušíme, zejména při substituci un — m>0 k\-\-----\-km=n-l m m>0 k\-\-----\-km=n-l Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo ooooo OOOO0OOOO OOOOO m m>0 ki-\-----\-km=n—l Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O oooooooooo ooooo OOOO0OOOO OOOOO »- = E E _ Ukl'" ukm m>0 /ciH-----\-km=n—l Je vidět, že vnitřní sumu dostaneme jako koeficient u xn 1 v rn-té mocnině řady l7(x) — ^un- *n- Proto je m! m>0 a tedy Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo OOOOO 0000*0000 OOOOO m>0 ' k!+-+km=n-l Je vidět, že vnitřní sumu dostaneme jako koeficient u x"-1 v m-té mocnině řady U(x) = ^u0 a tedy U(x) = xe Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo ooooo ooooo»ooo OOOOO Pokud vytvořující funkce g(x) — X)n>i Sn*n splňuje vztah x = f(g{x)), kde f(0) = 0, f'(0) i- 0, pak g" = -n[u ]{iur) n Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo ooooo OOOOOO0OO OOOOO Důkaz. Nebudeme se pokoušet o rigorózní důkaz, uvedeme jen, proč by vůbec nějaký vztah mezi koeficienty f a g měl existovat a jak lze pro malá n odvodit: Označíme-li f(u) — X)/c>i akLjk a g(x) — X)/>i ^/x/' Pa^ dosazením do sebe dostaneme vztah x = f(g(x)) = ai(bix + b2x2 + b3x3 + ...) + a2(bix + b2x2 + ... )2 + a3(bix + ... )3 + ... = aibix + (aib2 + a2b2)x2 + (aib3 + a2(bib2 + b2bi) + a3bi)x3 f ze kterého lze induktivně počítat (první koeficient a\b\ — 1, další jsou nulové): bi = —, b2 = ai ■32 ,3 ' 2a2, — 31^3 □ >0 Q,o Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo ooooo ooooooo«o OOOOO Řešíme U{x) = xeu(x\ tj. U{x) splňuje vztah x = ŕ((V(x)), kde Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo OOOOO ooooooo«o OOOOO Řešíme U(x) = xeu(x\ tj. U(x) splňuje vztah x = ŕ((V(x)), kde f(u) — tu- Odtud z Lagrangeovy formule n \ u eu 1 1 nn_1 nn_1 = £[,,"-11 p«" = _ —_ = -_ n1 J n(n-l)\ n\ Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo OOOOO ooooooo«o OOOOO Řešíme U(x) = xe°(x\ tj. U(x) splňuje vztah x = f(U(x)), kde f(lí) = ^77. Odtud z Lagrangeovy formule n \u/euJ 1 1 nn_1 nn~l = V-1]ewn = -7A^rí = V nL J n(n-l)! n! Protože un = tjjl, dostáváme odtud u„ = r?n_1 a nakonec Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O OOOOOOOOOO OOOOO 00000000» ooooo Další aplikace Lagrangeovy inverzní formule Vraťme se ještě krátce ke Catalanovým číslům. Chtěli jsme vyřešit rovnici B(x) = xB(x)2 + 1 a výslednou funkci 6(x) pak rozvést do mocninné řady. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O OOOOOOOOOO OOOOO 00000000» ooooo Další aplikace Lagrangeovy inverzní formule Vraťme se ještě krátce ke Catalanovým číslům. Chtěli jsme vyřešit rovnici B(x) = xB(x)2 + 1 a výslednou funkci B(x) pak rozvést do mocninné řady. Substitucí 6(x) = C(x) + 1 rovnici převedeme na C(x) = x(C(x) + l)2 neboli Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O OOOOOOOOOO OOOOO 00000000» ooooo Další aplikace Lagrangeovy inverzní formule Vraťme se ještě krátce ke Catalanovým číslům. Chtěli jsme vyřešit rovnici B(x) = xB(x)2 + 1 a výslednou funkci B(x) pak rozvést do mocninné řady. Substitucí 6(x) = C(x) + 1 rovnici převedeme na C(x) = x(C(x) + l)2 neboli C(x) (C(x) + 1)2 ^ Označíme-li nyní f(u) — (u+iy > Je hledaná funkce C(x) k této funkci inverzní a podle Lagrangeovy formule její koeficienty jsou Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O OOOOOOOOOO OOOOO 00000000» ooooo Další aplikace Lagrangeovy inverzní formule Vraťme se ještě krátce ke Catalanovým číslům. Chtěli jsme vyřešit rovnici B(x) = xB(x)2 + 1 a výslednou funkci B(x) pak rozvést do mocninné řady. Substitucí 6(x) = C(x) + 1 rovnici převedeme na C(x) = x(C(x) + l)2 neboli C(x) (C(x) + 1)2 ^ Označíme-li nyní f(u) — (u+iy » Je hledaná funkce C(x) k této funkci inverzní a podle Lagrangeovy formule její koeficienty jsou c" = ^"""^WTif)" = ^u""1,((i, + 1)2)" což lze vskutku ekvivalentně přepsat jako ^ttÍ2"). Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O oooooooooo ooooo ooooooooo •oooo án přednášky Q Rekurzivně propojené posloupnosti Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo ooooo ooooooooo o»ooo Rekurzivně propojené posloupnosti Někdy dokážeme snadno vyjádřit hledaný počet jen pomocí více vzájemně provázaných posloupností. v I Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo ooooo ooooooooo o»ooo Rekurzivně propojené posloupnosti 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 Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo ooooo ooooooooo o»ooo Rekurzivně propojené posloupnosti 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 co = 1 (nejde jen o konvenci, má to svou logiku). Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo ooooo ooooooooo o»ooo Rekurzivně propojené posloupnosti 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 en = 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 Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo ooooo ooooooooo oo»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 Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti o oooooooooo ooooo ooooooooo ooo»o Řešení (pokr.) o Krok 1: c„ = 2r„_i + c„_2 + [n = 0], r„ = c„_i + r„_2. Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo ooooo ooooooooo ooo»o Řešení (pokr.) • Krok 1: cn = 2r„_i + c„_2 + [n = 0], r n — cn-i + rn-2- • Krok 2: C(x) = 2xR(x) + x2C(x) + 1, R(x) = xC(x)+x2/?(x). Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti O oooooooooo ooooo ooooooooo ooo»o Řešení (pokr.) • Krok 1: cn = 2r„_i + cn_2 + [n = 0], rn = c„_i + rn-2- • Krok 2: C(x) = 2xR(x) + x2C{x) + 1, R{x) = xC(x) + x2R(x) • Krok 3: 1 -x' C(X) ~ 1 - 4x2 + x4 x □ s Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo ooooo ooooooooo ooo»o Řešení (pokr.) • Krok 1: c„ = 2r„_i + c„_2 + [n = 0], rn = cn_x + r„_2. • Krok 2: C(x) = 2xR(x) + x2C(x) + 1, R(x) = xC(x) + x2R(x). • Krok 3: C(X) = 1 x*' /?(x)=l-4x^ + x4- • Krok 4: Vidíme, že funkce C(x) je funkce x2, ušetříme si práci tím, že uvážíme funkci D(z) = 1/(1 — 4z + z2), pak totiž C(x) = (l-x2)D(x2), tj. [x2"]C(x) = [x2"](l - x2)D(x2) = [x"](l - x)D(x), a tedy Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo OOOOO ooooooooo oooo« Řešení (závěr) Kořeny 1 - 4x + x2 jsou 2 + \/3 a 2 — a/3 a již standardním způsobem obdržíme = (2 + Všy (2 - Všy C2n 3-VŠ 3 + VŠ Literatura Řešení rekurencí Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 0 oooooooooo ooooo ooooooooo oooo« Řešení (závěr) Kořeny 1 — 4x + x2 jsou 2 + y3 a 2 — y3 a již standardním způsobem obdržíme = (2 + y/3)n (2 - y/3)n 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 + V3)n 3- -s/3 Např. c20 = 413403.