Rozklady přirozených čísel na sčítance Pro libovolná kladná přirozená čísla n a k označme d(n, k) počet všech rozkladů čísla n na součet k vzájemně různých sčítanců. Těmito sčítanci mají být opět kladná přirozená čísla a nebude přitom záležet na pořadí těchto sčítanců. Odvodím Pro n menší než součet 1 + 2 + • • • + /c, to jest pro n < ( ) neexistuje rozklad čísla n na k různých sčítanců, takže je 5(a7, k) = 0. Pro n ^ ( kÍ^1 ) veďme následující úvahu. Uvažme libovolný rozklad čísla n na k různých sčítanců: n = mi + m2 H-----h tnk. kde mi < A7i2 < • • • < ati^. Pak jsou dvě možnosti. Buďto mi > 1, pak ovšem n — k = (/t?i — 1) + (/t?2 — 1) + • • • + (rn/c — 1) je rozklad přirozeného čísla n — k na k různých sčítanců; těchto rozkladů je d(n — k, k). Anebo mi = 1. Jestliže přitom k > 1, pak a? — 1 = A7i2 + • • • + ATi/c je rozklad přirozeného čísla n — 1 na k — 1 různých sčítanců větších než 1, a tedy n — k = (/r?2 — 1) + • • • + (/r?^ — 1) je rozklad přirozeného čísla n — k na k — 1 různých sčítanců; těchto rozkladů je $(a7 — /c, /c — 1). Odtud plyne rekurentní formule d(n, k) = d{n - /c, k) + d{n - /c, k - 1) pro hodnoty k > 1 a n ^ ( ^1 ). Není ale těžké si rozmyslet, že tato rekurentní formule ve skutečnosti platí už pro všechna n > k. Přitom počáteční hodnoty jsou ovšem 9(a?, 1) = 1 pro všechna přirozená čísla n a d(n, k) = 0 všechna přirozená čísla a?, k splňující n < ( ), respektive n ^ k. Budeme chtít postupně počítat hodnoty d(n, 1), d(n,2), 9(n, 3), . .. pro libovolná přirozená čísla n. Již víme, že 9(a?, 1) = 1 pro všechna přirozená čísla n. Zkoumejme dále hodnoty 9(a?, 2). Víme, že 9(1,2) = 0, 9(2,2) = 0, a pro n ^ 3 máme podle předchozí rekurentní formule vztah <9(a7, 2) = <9(a7 -2,2) + <9(a7 - 2,1). To znamená, že pro všechna přirozená čísla n ^ 1 máme vztah 9(a7 + 2,2) = 9(a7,2) + 9(a7,1), tedy dostáváme vztah <9(a7 + 2,2)-<9(a7,2) = 1. To je nehomogenní lineární rekurentní formule s konstantními koeficienty pro čísla d(n< 2 Charakteristický polynom této lineární rekurentní formule je x2-l, má dva kořeny ±1, takže fundamentální systém řešení zhomogenizované lineární rekurentní formule pozůstává ze dvou řešení 1" = 1 a (—1)". Metodou variace konstant hledáme partikulární řešení nehomogenní lineární rekurentní formule ve tvaru c{n) + d{n){-l)n pro jisté funkce c(n) a d(n), pro něž máme dvě rovnice Ac(a7) + (-l)n+1Ad(n) = 0, Ac(a7) + (-l)nAc/(n) = 1. Z těchto rovnic vychází Ac(n) = \, Ad(n) = \(-1)". Odtud sumací vyplyne c(n) = |n, d(n) = -\(-l)". Obecné řešení nehomogenní lineární rekurentní formule je tedy tvaru a + b(-l)n + \n-\{-l)n{-iy = a + b(-l)" + \n-\ pro jisté konstanty a, b. Pro tyto konstanty z počátečních podmínek 5(1,2) = 0, 5(2,2) = 0 vychází a-b+\-\ = Q, a + 6+l-i=0, neboli ^ ^ a — b = —, a + = —, ta kže ^ ^ 3 = —-, b = —. 2' 4 Dostáváme tak d{n,2) = \{-iy+1 + \n-\ pro všechna přirozená čísla n. Zkoumejme dále hodnoty 5(n, 3) pro libovolná přirozená čísla n. Víme, že 5(1, 3) = 0, 5(2, 3) = 0, 5(3, 3) = 0, a pro n ^ 4 máme podle výše odvozené rekurentní formule vztah 5(a7, 3) = 5(a7 - 3,3) + 5(a7 - 3,2). To znamená, že pro všechna přirozená čísla n ^ 1 máme vztah 5(a7 + 3,3) = 5(a7,3) + 5(a7,2). Podle předchozího výsledku přitom známe hodnotu d(ni2) = \{-iy+í + \n-\. Dostávame tedy vztah d(n + 3, 3) - d(n, 3) = \(-l)n+1 + \n - \. To je nehomogenní lineární rekurentní formule s konstantními koeficienty pro čísl $(a7, 3). Charakteristický polynom této lineární rekurentní formule je x3-l, má tři kořeny , 1 , VŠ ■ 2 1 VŠ ■ 1, £ =-----/, £ =----/, 2 2' 2 2 ' takže fundamentální systém řešení zhomogenizované lineární rekurentní formule pozůstává ze tří řešení ln = 1, en, £2n. Metodou variace konstant hledáme partikulární řešení nehomogenní lineární rekurentní formule ve tvaru f(n)+g(n)en + h(n)e2n pro jisté funkce f(n), g(n) a h(n), pro něž máme tři rovnice Af(n) + £n+1 Ag(n) + £2n+2 Ah(n) = 0, Af(n) + £n+2Ag(n) + £2n+1 Ah(n) = 0, Af(n) + £nAg(n) + £2nAh(n) = \(-l)n+1 + \n - |. To je soustava tří lineárních rovnic pro tři neznámé funkce Af(n), Ag(n) a Ah(n). Determinant matice této soustavy lineárních rovnic je 1 £n+l £2n+2 1 £n+2 £2n+l 1 c = 3c 3c. Směřujeme k řešení této soustavy lineárních rovnic Cramerovým pravidlem K tomu potřebujeme vypočíst ještě determinanty 0 0 -n+l -2/7+2 c c -/7+2 ,-2/7+1 c c K- i)"+1 + \n 3 4 n -2/7 c í 0 i 0 £2n+l — i K-i) n+l i 2 11 3 4 e2n i £n+l 0 i £n+2 0 — i en K- l)"+1+ In_ 3 2 4 = (i(-ir1+5"-!)(^2 G(-l)n+1+^ (Jí-l^ + ^n-DeV-^ Dostáváme tedy Af(n) = ^( l)"+i +1 _ I 7 6 4 Ag(")=(^(-ir1 + i«-4)E A/,("'= (é(-1'°+1 + s"-;i£°- Odtud sumací obdržíme f(n) = ^(-1)" + ^n(n - 1) - \n. Zamýšlíme vypočíst partikulární řešení f(n) + g(n)en + h(n)e2n naší nehomogenní lineární rekurentní formule. K tomu účelu zjistíme f(n) = ±(-iy + ±n(n-l)-\n, *V ' 12e2 + :T ; ^6e2-l 6 (e2 -1)2 4e2-l' Chceme tyto hodnoty sečíst. K tomu si nejdříve všimněme, že 1 1 2 + s + e- e + 1 e2 + l (£ + l)(e2 + l) 1 1 _ £ + £2-2 _ I o i / i \ / o - \ -L s-1 s2-l {s- l){s2 - 1) e e2 _ e(e2-ľ)2 + e2(e-ľ)2 _ 2(e + e2 - 2) _ 2 {s-1)2 {e2-ľ)2 {s-l)2{s2 -l)2 {2-s-s2)2 3' kde poslední rovnost vyplynula využitím faktu, že e2 + s + 1 = 0. Nyní tedy sečtením obdržíme f» + g(n)e" + /^e2" = ±(-1)" + ln2 - + |. Obecné řešení nehomogenní lineární rekurentní formule je tedy tvaru a + b£n + C£2n + 1 (_ir + _Ln2 _ 1 „ + 13 pro jisté konstanty a, £>, c, pro které z počátečních podmínek d(l, 3) = 0, 9(2,3) = 0, <9(3,3) = 0 vychází a + bs + cs2-l + ^--l + ^ = 0, 8 12 2 36 a + be2 + ce + ^ + \ - 1 + § = 0, 8 3 36 1 3 3 13 a + b+ c---h - - - + — =0. 84 236 neboli a + be + c£ = a + te + ce a + b + c 72 13 72 37 72 Sečtením těchto tří rovnic dostaneme takže 7 a = 24 Odtud plyne Odečtěme dále od první rovnice druhou rovnici vynásobenou číslem e. Takto dostaneme Vydělením číslem 1 — e odtud obdržíme / 13 a — b = — 72 Takže dále dostáváme b= , . 9' 9 i 1 1 b = —. c = -. Poznamenejme, že 27T . . 27T ? 27T . . 27T c = cos — + / sin —. e = cos ——/sin — Vypočteme 2n 1 n , 1 2n ben + c^n = ^n + 1/ 27TA7 . . 27TA7\ 1/ 27TA7 . . 2tTA7 = - cos ——h / sin —— + - cos —--/ sin -—— 9V 3 3 ) 9V 3 3 2 27TA7 = - cos -—. 9 3 Dostáváme tak r\í q\ 2 27th 1, 1 2 1 , 47 0(#i,3) = - cos— + -(-1) + -n -2H+-pro všechna přirozená čísla a?.