Diskrétní matematika - cvičení 12. a 13. týden Lukáš Vokřínek Masarykova univerzita Fakulta informatiky jaro 2020 Príklad Najděte explicitní vyjadrení pro n-tý člen Fibonacciho posloupnosti {an} defiované rekurentním vztahem a0 = 0. 3i = 1 an = a„_i + an-2 pro n > 2 Najděte explicitní vyjádření pro n-tý člen Fibonacciho posloupnosti {an} defiované rekurentním vztahem 3o = 0, ai = 1 an = an-i + an-2 pro n > 2 Řešení Doplňme a_i = a_2 = 0 a rozepišme druhou rovnici pro případ n = 1, r? = 0: r? = 1: ai = ao + a_i + /4 r? = 0: ao = a_i + a_2 + 6 Dohromady tak můžeme psát rekurenci jedinou formulkou: an = a„_i + an_2 + A • [n = 1] + B • [n = 0]. 3n = an-i + an-2 +A>[n = l] + B>[n = 0]. Tu nyní vynásobíme xn a sečteme přes všechna n = 0,1. dostaneme: ■v ✓ -v .cimz J] anxn = x • a^ix""1 + x2 • ^ an-2Xn~2 +A-X+B. Označíme f(x) vytvořující funkci posloupnosti {an}, tím se rovnice přepíše na f (x) = x • f (x) + x2 • f(x) + A-X+B. Řešení f (x) = x • f (x) + x2 • f (x) + A-x+ B. Převedením výrazů obsahujících ŕ(x) na levou stranu a vytknutím dostaneme (l-x-x2)'f(x)=A-x+ B neboli (1-a- x)(l - f3 • x) • f (x) = 4 ■ x + 6, kde a, /3 = ľ±y^. Podělením koeficientem u ŕ (x) pak f(x) = /4-x + e (l-a-x)(l-/3-x)' Řešení Rozklad na parciální zlomky dá f{x) = C ■ —^-+ D • 1 1 — a • x 1-P>x a rozvinutím do mocninné řady pomocí zobecněné binomické věty ŕ(x) = c • ;>> • x)n + d • • x)". Řešení Rozklad na parciální zlomky dá f{x) = C ■ —^-+ D • 1 1 — a • x 1-P>x a rozvinutím do mocninné řady pomocí zobecněné binomické věty f(x) = C ■ £(a ■ x)n + D ■ £(0 ■ x)n. Celkový koeficient u x", tj. n-tý člen posloupnosti an, tedy je an = C • a" + D • f3n n n Nyní teprve určíme neznámé koeficienty C a D, s ohledem na ao a 31- an = C • a" + D • (3n n / ^\ n Nyní teprve určíme neznámé koeficienty C a D, s ohledem na ao a 31- 0 = a0 = C • I —-— I + D ■ 1 = 3i = C • —-— + D • Řešení 0 = ao = C.|I±^0 + D>-^° 1 = 3l=C.|i±^V + D í1-^1 S Úpravou dostaneme: 0 = C + D 2 = C • (1 + VŠ) + D • (1 - VŠ) jejímž řešením snadno obdržíme C = D = VŠ Řešení Výsledné explicitní vyjádření pro n-tý člen Fibonacciho posloupnosti je tedy i fi+ŕV i /i-VšV Poznámka Ukážeme si, jak lze "snadno" faktorizovat a + bx + cx2 = a • (1 — ax) • (1 — /3x) Jde to pomocí vzorečku pro kořeny kvadratického polynomu: ct,/3= -b±^J^-4ac Qen jsme prohodili u polynomu roli a, c) Poznámka Ukážeme si, jak lze "snadno" faktorizovat a + bx + cx2 = a • (1 — ax) • (1 — /3x) Jde to pomocí vzorečku pro kořeny kvadratického polynomu: ct,/3= ~b±^~4ac (jen jsme prohodili u polynomu roli a, c). To je proto, že substituce x = ŕ-1 a vynásobení ŕ2 dá ŕ2 • (a + br-1 + ct~2) = ŕ2 • a • (1 - aŕ-1) • (1 -aŕ2 + bt + c = a • (ŕ - a) • (ŕ - /3) což je rozklad na kořenové činitele tak, jak jej známe, a vzorec pro kořeny funguje (nyní jsou již koeficienty a, c standardně). i standardní Poznámka Ukážeme si, jak lze "snadno" faktorizovat a + bx + cx2 = a • (1 — ax) • (1 — /3x) Jde to pomocí vzorečku pro kořeny kvadratického polynomu: ct,/3= -b±^J^-4ac Qen jsme prohodili u polynomu roli a, c). To je proto, že substituce x = t a vynásobení t dá ŕ2 • (a + br"1 + cŕ"2) = ŕ2 • a • (1 - at'1) • (1 - /^ŕ"1) aŕ2 + bŕ + c = a • (ŕ - a) • (ŕ - /3) což je rozklad na kořenové činitele tak, jak jej známe, a standardní vzorec pro kořeny funguje (nyní jsou již koeficienty a, c standardně). Např. l-5x + 6x2 = 1 - 5 + 1 x 1 - -—-x ) = (l-3x)-(l-2x). Příklad S využitím vytvořující funkce pro Fibonacciho posloupnost F(x) = x/(l — x — x2) určete vytvořující funkci "poloviční" Fibonacciho posloupnosti (Fq, f2, f4,...). Příklad S využitím vytvořující funkce pro Fibonacciho posloupnost F(x) = x/(l — x — x2) určete vytvořující funkci "poloviční" Fibonacciho posloupnosti (Fq, F2, F4,...). Řešení Pišme F(x) = F0 + Fix + F2x2 + F3x3 + F4x4 H----, pak F(-x) = F0- Fix + F2x2 - F3x3 + F4x4---- a sečtením dostaneme 1/2 • (F(x) + F(-x)) = F0 + F2x2 + F4x4 + • • • . Hledanou vytvořující funkci pak získáme substitucí ^/x za x. Snadnou úpravou dostaneme 1/2 • (F(x) + F(-x)) = 1/2 • ( * y2 + \ j. x x —x = 1/2 • 1 + x - x2 x(l + x - x2) - x(l - x - x2) (l-x-x2)(l+x-x2) x2 x2 (l-x2)2-x2 l-3x2+x' a hledaná vytvořující funkce, vzniklá dosazením yx za x, je pak x 1 - 3x + x 2 ' Poznámka f (x) = a0 + aix + a2x2 + a3x3 + a4x4 H---- Potom máme následující "transformace": f(x) 1 f{-x) (ao, ai, a2, a3, a4,...) (ao, — ai, a2, —a3, a4,...) 1/2 • (f (x) + f (-x)) (ao, 0, a2, 0, a4,...) g(x2) (bo, 0, bi, 0, b2,...) (b0, bi, b2,...) Poznámka f(x) = a0 + aix + a2x2 + a3x3 + a4x4 -\---- g(x) = b0 + bíX + b2X2 + b3x3 + b4x4 + ■■■ Potom: f(x) ■ g(x) = (a0 + axx + a2x2 + •■•)• (6q + bxx + b2x2 + ■■■) = (a0b0) + (a0bi + a1b0)x + (aQb2 + axbx + a2bo)x2 + Tato "konvoluce" (a * b)n = aQbn + 3lbn-X + • • • + anbo má následující speciální případy: Tato "konvoluce" (a * b)n = aobn + a\bn-\ + • • • + anbo má následující speciální případy: (a0, ai, a2,...) * (0? 1,0,...) = (0, a0, ai, a2,...), na úrovni vytvořujících funkcí: f (x) • x je vytvořující funkcí pro posunutou posloupnost (an_i). (ao, ai, a2,...) * (1,1,1,...) = (ao, ao + ai, ao + ai + a2,...), na úrovni vytvořujících funkcí: f(x) • je vytvořující funkcí pro posloupnost (ao + a± + • • • + an) částečných součtů. (ao, ai, a2,...) * (0,1,1,...) = (0, a0, a0 + ai,...), na úrovni vytvořujících funkcí: f(x) • je vytvořující funkcí pro posunutou posloupnost (ao + a± + • • • + an_i) částečných součtů. Príklad Vějířem řádu n nazveme graf na n + 1 vrcholech 0,1,..., n, který má následujících 2n — 1 hran: vrchol 0 je spojen hranou s každým ze zbylých vrcholů a každý vrchol k je spojen hranou s vrcholem k + 1 (pro 1 < k < n). Kolik koster má takový graf? Príklad Vějířem řádu n nazveme graf na n + 1 vrcholech 0,1,..., n, který má následujících 2n — 1 hran: vrchol 0 je spojen hranou s každým ze zbylých vrcholů a každý vrchol k je spojen hranou s vrcholem k + 1 (pro 1 < k < n). Kolik koster má takový graf? 2 n-1 ■v Řešení O pokud n > 1 (aby vrchol n nebyl izolovaný), koster tohoto typu je vn-i. Řešení / - 1 /-/ + 1 O pokud n > 1 (aby vrchol n nebyl izolovaný), koster tohoto typu je vn-i. O koster tohoto typu je pro libovolné / = 1, 2,..., n. O pokud n > 1 (aby vrchol n nebyl izolovaný), koster tohoto typu je vn-i. O koster tohoto typu je pro libovolné / = 1, 2,..., n. vn = vn-i • [n > 1] + i/0 + vi H----vn_i ■v Řešení vn = vn-i • [n > 1] + v0 + vi H----vn_i Z logiky věci je vějíř rádu 0 jediný graf s jedním vrcholem a ten má právě jednu kostru, tedy vq = 1 (to sedí i s předchozí analýzou, kde vo vystupuje). Můžeme tedy psát vn-i • [n > 1] = vn-i -[n = í\ a rekurenci lze přepsat jako: vn = + v0 + vi H----vn-i - [n = í\ + [n = 0]. Vytvořující funkci pro (vn) označme V(x), pak vytvořující funkce pro (vn-i) je \/(x) • x a pro (\z0 H-----h je \/(x) • ^ a tedy \/(x) = V{x) • x + \/(x) • —--x + 1. 1 x Řešení V (x) = V (x) • x + V (x) • - x — X - x + 1. Převedením výrazů obsahujících V(x) na levou stranu a vytknutím dostaneme l-3x + x2 --Wx) = 1 - x. 1-x v ; Podělením koeficientem u V(x) pak V(x) = (1-X)22=1 + K J l-3x + x2 S využitím předchozího příkladu: x 1 - 3x + x: vn = [n = 0] + F: 2n tj. vn — pro n > 0, a \/q = 1 (zatímco Fq = 0) >0 0,0 Určete, kolika způsoby lze pokrýt (nerozlišenými) kostkami domina obdélník n x 3 (a vyčíslete tuto hodnotu pro obdélník 20 x 3)? Příklad Určete, kolika způsoby lze pokrýt (nerozlišenými) kostkami domina obdélník n x 3 (a vyčíslete tuto hodnotu pro obdélník 20 x 3)? Řešení Příklad Určete, kolika způsoby lze pokrýt (nerozlišenými) kostkami domina obdélník n x 3 (a vyčíslete tuto hodnotu pro obdélník 20 x 3)? Řešení Příklad Určete, kolika způsoby lze pokrýt (nerozlišenými) kostkami domina obdélník n x 3 (a vyčíslete tuto hodnotu pro obdélník 20 x 3)? Řešení □ 3 ► < ► 4 = Řešení Cn = cn-2 + rn-i + rn-i >0 Q,o ■v Řešení Cn = Cn-2 + /"n-1 + /"n-1 rn = rn-2 + ■v Řešení Cn — Cn-2 + fn-l + rn-l rn — rn-2 + cn-i ■v Řešení cn = cn-2 + 2rn- fn — rn-2 + cn-l Řešení i Cn = Cn-2 + 2r„_i + ? • [n = 1] + ? • [n = 0] /"n = /"n-2 + c„_i + ? • [n = 1] + ? • [n = 0] Řešení Cn = Cn-2 + 2r„_i + ? • [n = 1] + ? • [n = 0] /"n = /"n-2 + c„_i + ? • [n = 1] + ? • [n = 0] C(x) = C(x) • x2 + 2/?(x) • x + linear R(x) = R(x) ■ x2 + C(x) • x + linear ■v Řešení cn = cn_2 + 2rn_i + ? • [n = 1] + ? • [n = 0] rn = r„_2 + cn_i + ? • [n = 1] + ? • [n = 0] C(x) = C(x) • x2 + 2/?(x) • x + linear /?(x) = R(x) ■ x2 + C(x) • x + linear C(x) • (1 - x2) = R(x) ■ 2x + linear / • (1 - x2) R(x) ■ (1 -x2) = C(x) -x + linear / • 2x C(x) • (1 - x2)2 = C(x) • 2x2 + cubic Řešení C(x) • (1 - x2)2 = C(x) • 2xz + cubic Převedením prvního výrazu napravo na levou stranu dostaneme C(x) • ((1 - x2)2 - 2xz) = cubic C(x) = C(x) = cubic cubic (l-x2)2-2x2 l-4x2+x4 cubic (l-(2 + V3)x2) • (1 - (2 - V3)x2) Označme A2 = 2 + y/Š, /i2 = 2 - y/Š. Pak C(x) = cubic (1 - A2x2) • (1 - fx2) cubic (1 - Ax) • (1 + Ax) • (1 - fix) • (1 + fix) >0 Q,o Řešení C(x) = cubic (1 - Ax) • (1 + Ax) • (1 - fix) • (1 + fix) a rozklad na parciální zlomky dá C(x) = T A + + A- + B. + + — Ax 1 + Ax 1 — fix 1 + [ix pro neznámé konstanty A±, B±. Hledaná posloupnost (tedy počet dláždění) je cn = A+- \n + A- ■ (-A)" + B+ ■ nn + e_ • (-//)" Zbývá určit tyto konstanty, k tomu využijeme první 4 členy posloupnosti: c0 = 1, ci = 0, c2 = 3, c3 = 0. Řešení a+- \n + a- ■ (-xy + b+ ■ ixn + e_ • (-fj,)n, c0 = 1, ci = 0, c2 = 3, c3 = 0. Pro n = 1 a n = 3 dostáváme konkrétně (a+ - a-) • X + {b+ - b-) ■ n = 0 (a+ - a-) • A3 + (b+ - b-) • /i3 = 0 Protože jsou dvojice (A,//) a (A ,\i ) lineárně nezávislé, znamená to, že a+-a-=0, b+ - e_ = 0 tj. a+ = a. = /4, = b- = b. Zbylé dvě rovnice pak jsou a-2+ b-2 = 1 a ■ 2X2 + b ■ 2/j2 = 3 Řešení A-2 + B-2 = 1 A ■ 2A2 + B ■ 2/j2 = 3 jejímž řešením je (připomeňme A2 = 2 + v3, jjl2 = 2 — V3) 4^3 4^3 Dosazením tak cn = • (A" + (-A)") + 4^ • + (-/i)") 4^3 4^3 Řešení c" = ■ (A°+ (-Ar) + =}i7T ■(""+ (-"r) Pro n lichá je tento výraz nulový (závorky jsou nulové), což je jasné i z lichosti počtu čtverců v obdélníku v tomto případě. Pro n = 2k dostaneme íWš 1 + 73 273 i + Vš 2^3 (A2fc + (-X)ZK) + 2k -1 + 73 4^3 2/c A2fc + -1 + 73 273 •/i 2fc (2 + 73^ + ^^.(2- 73) c20 = 413 403 >0 Q,o