遞推關(guān)系與生成函數(shù)

1、遞推關(guān)系與生成函數(shù)第1頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三1摘要線(xiàn)性齊次遞推關(guān)系 生成函數(shù) 遞歸和生成函數(shù)一個(gè)幾何的例子指數(shù)生成函數(shù)作業(yè) 第2頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三2線(xiàn)性齊次遞推關(guān)系第3頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三3線(xiàn)性遞推關(guān)系令 h0, h1, hn, 是一個(gè)數(shù)列，如果存在量 a1, a2, , ak, ak 0, 和量bn (每一個(gè)量 a1, a2, , ak, bn 可能依賴(lài)于 n) ，使得 hn = a1hn-1+a2hn-2+akhn-k+bn, (n k).則稱(chēng)該序列滿(mǎn)足k階線(xiàn)性遞推關(guān)系.第4頁(yè)

2、，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三4例子 錯(cuò)位排列數(shù)列 D0, D1, D2, Dn 滿(mǎn)足兩個(gè)遞推關(guān)系Dn = (n-1)Dn-1+(n-1)Dn-2, (n 2)Dn = nDn-1 + (-1)n, (n 1). 第一個(gè)遞推關(guān)系的階 是多少 且 a1 ，a2 ， bn等于多少。第二個(gè)遞推關(guān)系的 .第5頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三5齊次的 如果bn = 0，則線(xiàn)性遞推關(guān)系 hn = a1hn-1+a2hn-2+akhn-k+bn, (n k) 稱(chēng)為齊次的.如果a1, a2, , ak 是常數(shù),則稱(chēng)線(xiàn)性遞推關(guān)系式具有常系數(shù).第6頁(yè)，共51頁(yè)，

3、2022年，5月20日，19點(diǎn)38分，星期三6令q 為一個(gè)非零數(shù). 則 hn = qn 是常系數(shù)線(xiàn)性遞推關(guān)系 hn a1hn-1 a2hn-2 akhn-k= 0, (ak 0, n k) (7.20) 的解，當(dāng)且僅當(dāng)q是多項(xiàng)式 xk a1xk-1 a2xk-2 ak = 0. (7.21)的一個(gè)根。如果多項(xiàng)式方程有k個(gè)不同的根 q1, q2, , qk, 則 hn = c1q1n + c2q2n + + ckqkn (7.22) 是下述意義下式 (7.20) 的一般解: 無(wú)論給定 h0, h1, , 什么初始值，都存在 常數(shù)c1, c2, , ck 使得式 (7.22) 是滿(mǎn)足遞推關(guān)系 (7

4、.20) 和初始條件的唯一的序列. 第7頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三7注解 多項(xiàng)式方程 (7.21) 叫做 遞推關(guān)系 (7.20) 的特征方程 ，而它的 k 個(gè)根叫做 特征根. 如果特征根 互異, 那么式(7.22) 就是式(7.20) 的一般解.第8頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三8例題求解滿(mǎn)足h0 = 1, h1 = 2 and h2 = 0的遞推關(guān)系 hn = 2hn-1+hn-2 2hn-3, (n 3) . 提示: 這個(gè)遞推關(guān)系的特征方程為 x3 2x2 x + 2 = 0 而它的三個(gè)根 1, -1 , 2. 根據(jù)定理7.2.1

5、, hn = c11n + c2(-1)n + c32n 是一般解. 第9頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三9例題（續(xù)）由三個(gè)字母a, b, c組成的長(zhǎng)度為n的一些單詞將在通信信道上傳輸，滿(mǎn)足條件：傳輸中不得有兩個(gè)a連續(xù)出現(xiàn)在任一個(gè)單詞中。確定通信信道允許傳輸?shù)膯卧~個(gè)數(shù)。 第10頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三10提示 首先, 找到特征關(guān)系式 并且求出它的解.令 hn 表示允許傳輸?shù)拈L(zhǎng)度為 n的單詞的個(gè)數(shù). 我們有 h0 = 1 和 h1 = 3. 令 n 2. 如果第一個(gè)字母是 b 或者 c, 那么這個(gè)單詞就可以有 hn-1種方法構(gòu)成. 如果

6、第一個(gè)字母是 a , 那么第二個(gè)字母是 b 或者 c. 這樣, hn = 2 hn-1 + 2hn-2, (n 2).bab第11頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三11練習(xí) 一個(gè) 1n 棋盤(pán). 我們把每個(gè)方格都涂上紅色或者藍(lán)色. 令 hn 表示沒(méi)有兩個(gè)連續(xù)的方格被同時(shí)涂上紅色的方法的個(gè)數(shù). 找到并且證明這樣的一個(gè)遞推關(guān)系hn. 然后求得公式 hn.求解遞推關(guān)系 hn = 4hn-1 4hn-2, (n 2) .第12頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三12注解 如果特征方程的根 q1, q2, , qk 不是互異的, 那么 hn = c1q1n+c

7、2q2n+ckqkn 就不是遞推關(guān)系的一個(gè)一般解. 第13頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三13 令 q1, q2, , qt 為常系數(shù)線(xiàn)性齊次遞推關(guān)系 (7.20) 的特征方程的互異的根. 此時(shí)，如果 qi是 si重根, 則該遞推關(guān)系對(duì)qi的部分一般解為 Hn(i) = c1qin + c2nqin + + csinsi-1qin = (c1 +c2n+csinsi-1)qin 遞推關(guān)系的一般解則是hn = Hn(1) + Hn (2) + + Hn(t).第14頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三14例題求遞推關(guān)系 hn = 4hn-1 4hn

8、-2, (n 2) .提示: 特征方程是 x2-4x+4 = 0. 這樣 2 是重特征根. 特征關(guān)系的一般解為 hn = c12n + c2n2n.第15頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三15練習(xí) 求特征關(guān)系 hn = -hn-1 +3hn-2+5hn-3 +2hn-4, (n 4).第16頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三16生成函數(shù) 第17頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三17生成函數(shù)的方法利用代數(shù)的方法計(jì)算一個(gè)問(wèn)題可能性的次數(shù)生成函數(shù)是無(wú)窮次可微函數(shù)的泰勒級(jí)數(shù)如果你可以找到一個(gè)函數(shù)和它的泰勒級(jí)數(shù), 那么泰勒級(jí)數(shù)的系數(shù)

9、則給出這個(gè)問(wèn)題的解.第18頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三18生成函數(shù)的定義令 h0, h1, , hn, 是一個(gè)無(wú)窮的數(shù)列. 它的 生成函數(shù) 被定義為無(wú)窮級(jí)數(shù) g(x) = h0 + h1x + h2x2 + hnxn +在 g(x)中，xn 的系數(shù)是這個(gè)序列的第n項(xiàng) hn, 從而， xn 作為hn的“位置持有者”。 第19頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三19例題1. 無(wú)限序列的生成函數(shù) 1, 1, 1, , 1, , 它的每一項(xiàng)都等于1 g(x) = 1 +x+x2+xn+ = 1/(1-x)2. M是一個(gè)正整數(shù). 二項(xiàng)式序列 c(m,0

10、), c(m,1) c(m, 2),., c(m,m) 的生成函數(shù)是 gm(x)=c(m,0)+c(m,1)x+c(m,2)x2+c(m,m)xm = (1+x)m (二項(xiàng)式定理).第20頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三20練習(xí) 令a為一個(gè)實(shí)數(shù). 根據(jù)牛頓二項(xiàng)式定理, 二項(xiàng)式系數(shù) c(a, 0), c(a, 1) ,c(a, n),的無(wú)窮生成函數(shù)是什么？令 k 是一個(gè)整數(shù)， 并令序列 h0, h1, h2, hn, 使得hn等于 e1+e2+ek=n的非負(fù)整數(shù)的個(gè)數(shù). 這個(gè)序列的生成函數(shù)是什么?第21頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三21復(fù)習(xí)

11、令a是一個(gè)實(shí)數(shù) . 那么對(duì)于所有的 x 和 y （0 |x| |y|）, 第22頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三22又因?yàn)?|y|11)第24頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三24例題（續(xù)）確定蘋(píng)果、香蕉、橘子和梨的n-組合的個(gè)數(shù), 其中在每個(gè)n-組合中蘋(píng)果的個(gè)數(shù)是偶數(shù)，香蕉的個(gè)數(shù)是奇數(shù)，橘子的個(gè)數(shù)在0和4之間，而且至少要有一個(gè)梨提示: 該問(wèn)題等價(jià)于找出 e1 + e2 + e3 + e4 = n.的非負(fù)整數(shù)解的個(gè)數(shù)第25頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三25 其中 e1 是偶數(shù) (e1 為蘋(píng)果數(shù)), e2 是奇數(shù), 0

12、 e34, 而 e4 1. 我們?yōu)槊糠N類(lèi)型的水果建立一個(gè)因子， 其中的指數(shù)為那種類(lèi)型水果的n- 組合中所允許的數(shù): g(x) = (1 + x2 + x4 +)(x + x3 + x5 +)(1 + x + x2 + x3 + x4) (x + x2 + x3 + x4 +) 第26頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三26練習(xí) 令hn代表好幾袋子蘋(píng)果、香蕉、橘子和梨的總個(gè)數(shù), 并且每個(gè)袋子中蘋(píng)果的個(gè)數(shù)是偶數(shù), 香蕉的隔數(shù)是 5的倍數(shù), 橘子的個(gè)數(shù)至多為 4 并且梨的個(gè)數(shù)為 0 或者 1. 提示: 計(jì)算這個(gè)問(wèn)題的生成函數(shù)的xn的系數(shù). 第27頁(yè)，共51頁(yè)，2022年，5月2

13、0日，19點(diǎn)38分，星期三27練習(xí)（續(xù)）確定方程 e1 + e2 + + ek = n非負(fù)整數(shù)解e1, e2, , ek 的個(gè)數(shù)hn的生成函數(shù)。提示: k (x+x3+x5+x7+).第28頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三28練習(xí) (續(xù))令 hn 表示方程 3e1 + 4e2 + 2e3 + 5e4 = n非負(fù)整數(shù)解的個(gè)數(shù). 找到h0, h1, h2, , hn,.的生成函數(shù) g(x)提示: 令 f1 = 3e1, f2 = 4e2, f3 = 2e3 并且 f4 =5e4. 于是hn 也等于 f1 + f2 + f3 + f4 = n 的非負(fù)整數(shù)解的個(gè)數(shù)，其中 f1

14、 是 3的倍數(shù), f2 是 4的倍數(shù), f3 是偶數(shù) 并且 f4 是 5的倍數(shù). 第29頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三29遞歸生成函數(shù)第30頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三30內(nèi)容利用生成函數(shù)來(lái)求解常系數(shù)的線(xiàn)性齊次遞推關(guān)系. 牛頓二項(xiàng)定理的應(yīng)用.第31頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三31復(fù)習(xí): 牛頓二項(xiàng)定理如果 n是一個(gè)正整數(shù) 并且 r 是一個(gè)非零整數(shù), 那么第32頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三32例題確定平方項(xiàng)的序列 0, 1, 4, , n2,.的生成函數(shù)解答: 把 n =2 、 r

15、 =1帶入上面的牛頓二項(xiàng)式, (1-x)-2 = 1+2x+3x2+nxn-1+. 因此 x/(1-x)2=x+2x2 + 3x3+nxn +. 微分, 我們得到 （1+x)/(1-x)3=1+22x+32x2+n2xn-1+. 乘 x, 得到 x(1+x)/(1-x)3.第33頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三33例題 (續(xù))求解滿(mǎn)足初始值 h0 = 1 和 h1 = -2的遞推關(guān)系 hn = 5hn-1 6 hn-2, (n2).提示: 令 g(x) = h0+h1x+h2x2+hnxn+. 為 h0, h1, h2, , hn 的生成函數(shù)。此時(shí)，我們有下列方程 第

16、34頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三34g(x) = h0+h1x+h2x2+hnxn+.-5xg(x) = -5h0 x -5h1x2 - 5h2x3 - 5hn-1 xn -. 6x2 g(x) = 6h0 x2 +6h1x3 +6h2x4 +6hn-2xn +. 將三個(gè)方程相加, 得到(1-5x+6x2)g(x) = h0+(h1-5h0)x+(h2-5h1+6h0)x2+(hn-5hn-1+6hn-2)xn+. = h0+(h1-5h0)x = 1-7x因此, g(x) = (1-7x)/(1-5x+6x2) = 5/(1-2x) 4/(1-3x)第35頁(yè)，共

17、51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三35通過(guò)牛頓二項(xiàng)定理(1-2x)-1 = 1+2x+22x2+2nxn.(1-3x)-1 = 1+3x+32x2+3nxn.于是, g(x) = 1 + (-2)x + (-15)x2 + (52n 43n)xn+可以得到 hn = 52n 43n (n = 0, 1, 2, ).第36頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三36練習(xí) 滿(mǎn)足h0 = 0, h1 = 1 ，h2 = -1的遞推關(guān)系 hn + hn-1 16 hn-2+20hn-3 = 0 (n3)求hn的一般公式。第37頁(yè)，共51頁(yè)，2022年，5月20日，1

18、9點(diǎn)38分，星期三37一個(gè)幾何的例子第38頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三38劃分凸多邊形的方法通過(guò)畫(huà)出在區(qū)域內(nèi)部不相交的對(duì)角線(xiàn)將具有n+1 條邊的凸多邊形區(qū)域分成三角形區(qū)域，令hn 表示分成三角形區(qū)域的方法數(shù)。定義h1 =1. 則 hn 滿(mǎn)足遞推關(guān)系 hn = h1hn-1+h2hn-2+hn-1h1, (n2). 該遞推關(guān)系的解為 hn = n-1C(2n-2, n-1), (n=1, 2 , 3, ).第39頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三39指數(shù)生成函數(shù)第40頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三40復(fù)習(xí): ex的

19、泰勒級(jí)數(shù)第41頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三41指數(shù)生成函數(shù)的定義 序列 h0, h1, h2, , hn, 的指數(shù)生成函數(shù) 第42頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三42例子 令n為一正整數(shù).確定數(shù)列P(n, 0), P(n, 1), P(n, 2), , P(n, n),的指數(shù)生成函數(shù),其中 P(n, k) 表示n-元素集的k-排列的個(gè)數(shù),對(duì)于k = 0, 1, , n 其值為n!/(n-k)! .指數(shù)生成函數(shù)為第43頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三43因此, (1+x)n 既是序列P(n, 0), P(n, 1), P(n, 2), , P(n, n) 的指數(shù)生成函數(shù)又是序列C(n, 0), C(n, 1), C(n, 2), , C(n, n)的常規(guī)生成函數(shù).第44頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三44練習(xí) (續(xù))序列1, 1, 1, , 1, . 的指數(shù)生成函數(shù)是更一般的,如果a是一個(gè)實(shí)數(shù),那么序列a0 = 1, a, a2, , an, . 的指數(shù)生成函數(shù)是第45頁(yè)，共51頁(yè)，2022年，5月20日，19點(diǎn)38分，星期三45定理令S為多重集 n1.a1, n2.a2, nk.ak ,其中 n1, n2, , nk 均為非負(fù)整數(shù).令hn 是S的n-排列數(shù). 則序列h