Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Matematika IV – 10. týden Příklady řešení rekurencí Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2014 Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Obsah přednášky 1 Binární stromy a Catalanova čísla 2 Caleyho vztah pro počet stromů 3 Rekurzivně propojené posloupnosti Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 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. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 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. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Plán přednášky 1 Binární stromy a Catalanova čísla 2 Caleyho vztah pro počet stromů 3 Rekurzivně propojené posloupnosti Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 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 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, b1 = 1, b2 = 2, b3 = 5. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 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, b1 = 1, b2 = 2, b3 = 5. Dělením problému na levý a pravý strom dostaneme pro n ≥ 1 bn = b0bn−1 + b1bn−2 + · · · + bn−1b0. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 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, b1 = 1, b2 = 2, b3 = 5. Dělením problému na levý a pravý strom dostaneme pro n ≥ 1 bn = b0bn−1 + b1bn−2 + · · · + bn−1b0. Vidíme, že jde vlastně o konvoluci posloupností. Vztah upravíme, aby platil pro všechna n ∈ N0: bn = 0≤k 1 tn = m>0 1 m! k1+···+km=n−1 (n − 1)! k1! · · · km! k1 · · · km · tk1 · · · tkm Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 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 tn = m>0 1 m! k1+···+km=n−1 (n − 1)! k1! · · · km! k1 · · · km · tk1 · · · tkm Např. pro n = 4 máme t4 = 3t3 + 6t1t2 + t3 1 . Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 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 tn = m>0 1 m! k1+···+km=n−1 (n − 1)! k1! · · · km! k1 · · · km · tk1 · · · tkm Např. pro n = 4 máme t4 = 3t3 + 6t1t2 + t3 1 . 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 Dostáváme pro n > 1 un n! = m>0 1 m! k1+···+km=n−1 uk1 k1! · · · ukm km! a je vidět, že vnitřní sumu dostaneme jako koeficient u xn−1 v m-té mocnině řady U(x) = un xn n! . Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Dostáváme pro n > 1 un n! = m>0 1 m! k1+···+km=n−1 uk1 k1! · · · ukm km! a je vidět, že vnitřní sumu dostaneme jako koeficient u xn−1 v m-té mocnině řady U(x) = un xn n! . Proto je un n! = [xn−1 ] m≥0 1 m! U(x)m , a tedy U(x) = x eU(x) . Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice Zobecněnou exponenciální mocninnou řadou Et(x) nazýváme řadu Et(x) = k≥0 (tk + 1)k−1 xk k! . Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice Zobecněnou exponenciální mocninnou řadou Et(x) nazýváme řadu Et(x) = k≥0 (tk + 1)k−1 xk k! . Snadno je vidět, že E0 = ex , dále označujeme E(x) = E1(x). Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice Zobecněnou exponenciální mocninnou řadou Et(x) nazýváme řadu Et(x) = k≥0 (tk + 1)k−1 xk k! . Snadno je vidět, že E0 = ex , dále označujeme E(x) = E1(x). Fakt: ln Et(x) = x · Et(x), tj. spec. E(x) = exE(x) . Srovnáním tohoto vztahu s výše uvedeným U(x) = x eU(x) vidíme, že U(x) = xE(x). Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice Zobecněnou exponenciální mocninnou řadou Et(x) nazýváme řadu Et(x) = k≥0 (tk + 1)k−1 xk k! . Snadno je vidět, že E0 = ex , dále označujeme E(x) = E1(x). Fakt: ln Et(x) = x · Et(x), tj. spec. E(x) = exE(x) . Srovnáním tohoto vztahu s výše uvedeným U(x) = x eU(x) vidíme, že U(x) = xE(x). Proto tn = un n = n! n [xn ]U(x) = (n − 1)![xn−1 ]E(x) = nn−2 . Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 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 Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 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: Věta Pokud vytvořující funkce g(x) = n≥1 gnxn splňuje vztah x = f (g(x)), kde f (0) = 0, f (0) = 0, pak gn = 1 n [un−1 ] u f (u) n . Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Alternativní závěr výpočtu Řešíme U(x) = x eU(x), tj. U(x) splňuje vztah x = f (U(x)), kde f (u) = u eu . Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Alternativní závěr výpočtu Řešíme U(x) = x eU(x), tj. U(x) splňuje vztah x = f (U(x)), kde f (u) = u eu . Odtud z Lagrangeovy formule [xn ]U(x) = 1 n [un−1 ] u u/eu n = 1 n [un−1 ] eun = 1 n nn−1 (n − 1)! = nn−1 n! Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Alternativní závěr výpočtu Řešíme U(x) = x eU(x), tj. U(x) splňuje vztah x = f (U(x)), kde f (u) = u eu . Odtud z Lagrangeovy formule [xn ]U(x) = 1 n [un−1 ] u u/eu n = 1 n [un−1 ] eun = 1 n nn−1 (n − 1)! = nn−1 n! Protože un n! = [xn]U(x), dostáváme odtud tn = un n = nn−2 . Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Plán přednášky 1 Binární stromy a Catalanova čísla 2 Caleyho vztah pro počet stromů 3 Rekurzivně propojené posloupnosti Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti 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 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 (nerozlišenými) kostkami domina obdélník 3 × n? Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů 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 (nerozlišenými) kostkami domina obdélník 3 × n? Řešení Snadno zjistíme, že c1 = 0, c2 = 3, c3 = 0, dále klademe c0 = 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 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 (nerozlišenými) kostkami domina obdélník 3 × n? Řešení Snadno zjistíme, že c1 = 0, c2 = 3, c3 = 0, dále klademe c0 = 1 (nejde jen o konvenci, má to svou logiku). Najdeme rekurzívní vztah – diskusí chování „na kraji“ zjistíme, že cn = 2rn−1 + cn−2, rn = cn−1 + rn−2, r0 = 0, r1 = 1, kde rn je počet pokrytí obdélníku 3 × 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 Ř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 Řešení (pokr.) Krok 1: cn = 2rn−1 + cn−2 + [n = 0], rn = cn−1 + rn−2. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Řešení (pokr.) Krok 1: cn = 2rn−1 + cn−2 + [n = 0], rn = cn−1 + rn−2. Krok 2: C(x) = 2xR(x) + x2C(x) + 1, R(x) = xC(x) + x2R(x). Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Řešení (pokr.) Krok 1: cn = 2rn−1 + cn−2 + [n = 0], rn = cn−1 + rn−2. Krok 2: C(x) = 2xR(x) + x2C(x) + 1, R(x) = xC(x) + x2R(x). Krok 3: C(x) = 1 − x2 1 − 4x2 + x4 , R(x) = x 1 − 4x2 + x4 . Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Řešení (pokr.) Krok 1: cn = 2rn−1 + cn−2 + [n = 0], rn = cn−1 + rn−2. Krok 2: C(x) = 2xR(x) + x2C(x) + 1, R(x) = xC(x) + x2R(x). Krok 3: C(x) = 1 − x2 1 − 4x2 + x4 , R(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. [x2n]C(x) = [x2n](1 − x2)D(x2) = [xn](1 − x)D(x), a tedy c2n = dn − dn−1. Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Řešení (závěr) Kořeny 1 − 4x + x2 jsou 2 + √ 3 a 2 − √ 3 a již standardním způsobem obdržíme c2n = (2 + √ 3)n 3 − √ 3 + (2 − √ 3)n 3 + √ 3 . Literatura Binární stromy a Catalanova čísla Caleyho vztah pro počet stromů Rekurzivně propojené posloupnosti Řešení (závěr) Kořeny 1 − 4x + x2 jsou 2 + √ 3 a 2 − √ 3 a již standardním způsobem obdržíme c2n = (2 + √ 3)n 3 − √ 3 + (2 − √ 3)n 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 + √ 3)n 3 − √ 3 . Např. c20 = 413403.