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

1、1第七章第七章遞推關(guān)系與生成函數(shù)遞推關(guān)系與生成函數(shù)2摘要摘要 線性齊次遞推關(guān)系線性齊次遞推關(guān)系 生成函數(shù)生成函數(shù) 遞歸和生成函數(shù)遞歸和生成函數(shù) 一個幾何的例子一個幾何的例子 指數(shù)生成函數(shù)指數(shù)生成函數(shù) 作業(yè)作業(yè) 3線性齊次遞推關(guān)系線性齊次遞推關(guān)系4線性遞推關(guān)系線性遞推關(guān)系 令令 h0, h1, hn, 是一個數(shù)列，如果存是一個數(shù)列，如果存在量在量 a1, a2, , ak, ak 0, 和量和量bn (每一個每一個量量 a1, a2, , ak, bn 可能依賴于可能依賴于 n) ，使得，使得 hn = a1hn-1+a2hn-2+akhn-k+bn, (n k).則稱該序列滿足則稱該序列滿足k

2、階線性遞推關(guān)系階線性遞推關(guān)系.5例子 錯位排列數(shù)列錯位排列數(shù)列 D0, D1, D2, Dn 滿足兩個滿足兩個遞推關(guān)系遞推關(guān)系 Dn = (n-1)Dn-1+(n-1)Dn-2, (n 2) Dn = nDn-1 + (-1)n, (n 1). 第一個遞推關(guān)系的階第一個遞推關(guān)系的階 是多少是多少 且且 a1 ，a2 ， bn等于多少。等于多少。 第二個遞推關(guān)系的第二個遞推關(guān)系的 .6齊次的齊次的 如果如果bn = 0，則線性遞推關(guān)系，則線性遞推關(guān)系 hn = a1hn-1+a2hn-2+akhn-k+bn, (n k) 稱為稱為齊次的齊次的. 如果如果a1, a2, , ak 是常數(shù)是常數(shù),則

3、稱線性遞推關(guān)則稱線性遞推關(guān)系式具有系式具有常系數(shù)常系數(shù).7定理定理 7.2.1 令令q 為一個非零數(shù)為一個非零數(shù). 則則 hn = qn 是常系數(shù)線性遞推關(guān)系是常系數(shù)線性遞推關(guān)系 hn a1hn-1 a2hn-2 akhn-k= 0, (ak 0, n k) (7.20) 的解，當(dāng)且僅當(dāng)?shù)慕?，?dāng)且僅當(dāng)q是多項(xiàng)式是多項(xiàng)式 xk a1xk-1 a2xk-2 ak = 0. (7.21)的一個根。的一個根。 如果多項(xiàng)式方程有如果多項(xiàng)式方程有k個不同的根個不同的根 q1, q2, , qk, 則則 hn = c1q1n + c2q2n + + ckqkn (7.22) 是下述意義下式是下述意義下式 (

4、7.20) 的一般解的一般解: 無論給定無論給定 h0, h1, , 什么初什么初始值，都存在始值，都存在 常數(shù)常數(shù)c1, c2, , ck 使得式使得式 (7.22) 是滿足遞推關(guān)是滿足遞推關(guān)系系 (7.20) 和初始條件的唯一的序列和初始條件的唯一的序列. 8注解注解 多項(xiàng)式方程多項(xiàng)式方程 (7.21) 叫做叫做 遞推關(guān)系遞推關(guān)系 (7.20) 的的特征方程特征方程 ，而它的，而它的 k 個根叫做個根叫做 特征根特征根. 如果特征根如果特征根 互異互異, 那么式那么式(7.22) 就是式就是式(7.20) 的的一般解一般解.9例題例題 求解滿足求解滿足h0 = 1, h1 = 2 and

5、h2 = 0的遞推的遞推關(guān)系關(guān)系 hn = 2hn-1+hn-2 2hn-3, (n 3) . 提示提示: 這個遞推關(guān)系的特征方程為這個遞推關(guān)系的特征方程為 x3 2x2 x + 2 = 0 而它的三個根而它的三個根 1, -1 , 2. 根據(jù)定理根據(jù)定理7.2.1, hn = c11n + c2(-1)n + c32n 是一般解是一般解. 10例題（續(xù)）例題（續(xù)） 由三個字母由三個字母a, b, c組成的長度為組成的長度為n的一些的一些單詞將在通信信道上傳輸，滿足條件：單詞將在通信信道上傳輸，滿足條件：傳輸中不得有兩個傳輸中不得有兩個a連續(xù)出現(xiàn)在任一個單連續(xù)出現(xiàn)在任一個單詞中。確定通信信道允

6、許傳輸?shù)膯卧~個詞中。確定通信信道允許傳輸?shù)膯卧~個數(shù)。數(shù)。 11提示 首先首先, 找到特征關(guān)系式找到特征關(guān)系式 并且求出它的解并且求出它的解. 令令 hn 表示允許傳輸?shù)拈L度為表示允許傳輸?shù)拈L度為 n的單詞的個數(shù)的單詞的個數(shù). 我我們有們有 h0 = 1 和和 h1 = 3. 令令 n 2. 如果第一個字母如果第一個字母是是 b 或者或者 c, 那么這個單詞就可以有那么這個單詞就可以有 hn-1種方法種方法構(gòu)成構(gòu)成. 如果第一個字母是如果第一個字母是 a , 那么第二個字母是那么第二個字母是 b 或者或者 c. 這樣這樣, hn = 2 hn-1 + 2hn-2, (n 2).ba b12練習(xí)練

7、習(xí) 一個一個 1n 棋盤棋盤. 我們把每個方格都涂上我們把每個方格都涂上紅色或者藍(lán)色紅色或者藍(lán)色. 令令 hn 表示沒有兩個連續(xù)表示沒有兩個連續(xù)的方格被同時涂上紅色的方法的個數(shù)的方格被同時涂上紅色的方法的個數(shù). 找找到并且證明這樣的一個遞推關(guān)系到并且證明這樣的一個遞推關(guān)系hn. 然后然后求得公式求得公式 hn. 求解遞推關(guān)系求解遞推關(guān)系 hn = 4hn-1 4hn-2, (n 2) .13注解注解 如果特征方程的根如果特征方程的根 q1, q2, , qk 不是互異不是互異的的, 那么那么 hn = c1q1n+c2q2n+ckqkn 就不是就不是遞推關(guān)系的一個一般解遞推關(guān)系的一個一般解.

8、14定理定理 7.2.2 令令 q1, q2, , qt 為常系數(shù)線性齊次遞推關(guān)為常系數(shù)線性齊次遞推關(guān)系系 (7.20) 的特征方程的互異的根的特征方程的互異的根. 此時，此時，如果如果 qi是是 si重根重根, 則該遞推關(guān)系對則該遞推關(guān)系對qi的部分的部分一般解為一般解為 Hn(i) = c1qin + c2nqin + + csinsi-1qin = (c1 +c2n+csinsi-1)qin 遞推關(guān)系的一般解則是遞推關(guān)系的一般解則是hn = Hn(1) + Hn (2) + + Hn(t).15例題例題 求遞推關(guān)系求遞推關(guān)系 hn = 4hn-1 4hn-2, (n 2) .提示提示:

9、特征方程是特征方程是 x2-4x+4 = 0. 這樣這樣 2 是是重特征根重特征根. 特征關(guān)系的一般解為特征關(guān)系的一般解為 hn = c12n + c2n2n.16練習(xí)練習(xí) 求特征關(guān)系求特征關(guān)系 hn = -hn-1 +3hn-2+5hn-3 +2hn-4, (n 4).17生成函數(shù)生成函數(shù) 18生成函數(shù)的方法生成函數(shù)的方法利用代數(shù)的方法計算一個問題可能性的利用代數(shù)的方法計算一個問題可能性的次數(shù)次數(shù)生成函數(shù)是無窮次可微函數(shù)的泰勒級數(shù)生成函數(shù)是無窮次可微函數(shù)的泰勒級數(shù)如果你可以找到一個函數(shù)和它的泰勒級如果你可以找到一個函數(shù)和它的泰勒級數(shù)數(shù), 那么泰勒級數(shù)的系數(shù)則給出這個問那么泰勒級數(shù)的系數(shù)則給出

10、這個問題的解題的解.19生成函數(shù)的定義生成函數(shù)的定義令令 h0, h1, , hn, 是一個無窮的數(shù)列是一個無窮的數(shù)列. 它的它的 生成函數(shù)生成函數(shù) 被定義為無窮級數(shù)被定義為無窮級數(shù) g(x) = h0 + h1x + h2x2 + hnxn +在在 g(x)中，中，xn 的系數(shù)是這個序列的第的系數(shù)是這個序列的第n項(xiàng)項(xiàng) hn, 從而，從而， xn 作為作為hn的的“位置持有者位置持有者”。 20例題例題1. 無限序列的生成函數(shù)無限序列的生成函數(shù) 1, 1, 1, , 1, , 它的每一它的每一項(xiàng)都等于項(xiàng)都等于1 g(x) = 1 +x+x2+xn+ = 1/(1-x)2. M是一個正整數(shù)是一個

11、正整數(shù). 二項(xiàng)式序列二項(xiàng)式序列 c(m,0), c(m,1) c(m, 2),., c(m,m) 的生成函數(shù)是的生成函數(shù)是 gm(x)=c(m,0)+c(m,1)x+c(m,2)x2+c(m,m)xm = (1+x)m (二項(xiàng)式定理二項(xiàng)式定理).21練習(xí)練習(xí) 令令a為一個實(shí)數(shù)為一個實(shí)數(shù). 根據(jù)牛頓二項(xiàng)式定理根據(jù)牛頓二項(xiàng)式定理, 二項(xiàng)二項(xiàng)式系數(shù)式系數(shù) c(a, 0), c(a, 1) ,c(a, n),的無窮的無窮生成函數(shù)是什么？生成函數(shù)是什么？令令 k 是一個整數(shù)，是一個整數(shù)， 并令序列并令序列 h0, h1, h2, hn, 使得使得hn等于等于 e1+e2+ek=n的非負(fù)整的非負(fù)整數(shù)的個數(shù)

12、數(shù)的個數(shù). 這個序列的生成函數(shù)是什么這個序列的生成函數(shù)是什么?22復(fù)習(xí) 令令a是一個實(shí)數(shù)是一個實(shí)數(shù) . 那么對于所有的那么對于所有的 x 和和 y （0 |x| |y|）, 0)(kkkaayxkayx!121kkaaaaka23又因?yàn)橛忠驗(yàn)?|y|11)25例題（續(xù)）例題（續(xù)）確定蘋果、香蕉、橘子和梨的確定蘋果、香蕉、橘子和梨的n-組合的個數(shù)組合的個數(shù), 其中其中在每個在每個n-組合中蘋果的個數(shù)是偶數(shù)，香蕉的個數(shù)組合中蘋果的個數(shù)是偶數(shù)，香蕉的個數(shù)是奇數(shù)，橘子的個數(shù)在是奇數(shù)，橘子的個數(shù)在0和和4之間，而且至少要有之間，而且至少要有一個梨一個梨提示提示: 該問題等價于找出該問題等價于找出 e1

13、+ e2 + e3 + e4 = n.的非負(fù)整數(shù)解的個數(shù)的非負(fù)整數(shù)解的個數(shù)26 其中其中 e1 是偶數(shù)是偶數(shù) (e1 為蘋果數(shù)為蘋果數(shù)), e2 是奇數(shù)是奇數(shù), 0 e34, 而而 e4 1. 我們?yōu)槊糠N類型的水果建我們?yōu)槊糠N類型的水果建立一個因子，立一個因子， 其中的指數(shù)為那種類型水果其中的指數(shù)為那種類型水果的的n- 組合中所允許的數(shù)組合中所允許的數(shù): g(x) = (1 + x2 + x4 +)(x + x3 + x5 +)(1 + x + x2 + x3 + x4) (x + x2 + x3 + x4 +) 22252522)1 ()1 ()1 (111111xxxxxxxxxxx27練

14、習(xí)練習(xí) 令令hn代表好幾袋子蘋果、香蕉、橘子和梨代表好幾袋子蘋果、香蕉、橘子和梨的總個數(shù)的總個數(shù), 并且每個袋子中蘋果的個數(shù)是并且每個袋子中蘋果的個數(shù)是偶數(shù)偶數(shù), 香蕉的隔數(shù)是香蕉的隔數(shù)是 5的倍數(shù)的倍數(shù), 橘子的個數(shù)橘子的個數(shù)至多為至多為 4 并且梨的個數(shù)為并且梨的個數(shù)為 0 或者或者 1. 提示提示: 計算這個問題的生成函數(shù)的計算這個問題的生成函數(shù)的xn的系數(shù)的系數(shù). 28練習(xí)（續(xù)）練習(xí)（續(xù)）確定方程確定方程 e1 + e2 + + ek = n非負(fù)整數(shù)解非負(fù)整數(shù)解e1, e2, , ek 的個數(shù)的個數(shù)hn的生成函數(shù)。的生成函數(shù)。提示提示: k (x+x3+x5+x7+).29練習(xí)練習(xí) (

15、續(xù)續(xù))令令 hn 表示方程表示方程 3e1 + 4e2 + 2e3 + 5e4 = n非負(fù)非負(fù)整數(shù)解的個數(shù)整數(shù)解的個數(shù). 找到找到h0, h1, h2, , hn,.的的生成函數(shù)生成函數(shù) g(x)提示提示: 令令 f1 = 3e1, f2 = 4e2, f3 = 2e3 并且并且 f4 =5e4. 于是于是hn 也等于也等于 f1 + f2 + f3 + f4 = n 的非負(fù)整的非負(fù)整數(shù)解的個數(shù)，其中數(shù)解的個數(shù)，其中 f1 是是 3的倍數(shù)的倍數(shù), f2 是是 4的的倍數(shù)倍數(shù), f3 是偶數(shù)是偶數(shù) 并且并且 f4 是是 5的倍數(shù)的倍數(shù). 30遞歸生成函數(shù)遞歸生成函數(shù)31內(nèi)容內(nèi)容 利用生成函數(shù)來求

16、解常系數(shù)的線性齊次利用生成函數(shù)來求解常系數(shù)的線性齊次遞推關(guān)系遞推關(guān)系. 牛頓二項(xiàng)定理的應(yīng)用牛頓二項(xiàng)定理的應(yīng)用.32復(fù)習(xí)復(fù)習(xí): 牛頓二項(xiàng)定理牛頓二項(xiàng)定理如果 n是一個正整數(shù) 并且 r 是一個非零整數(shù), 那么)|(|,1)1()()1(1000 rxxrkknxrknrxknrxkkkkkkkkkn33例題例題確定平方項(xiàng)的序列確定平方項(xiàng)的序列 0, 1, 4, , n2,.的生成函數(shù)的生成函數(shù)解答解答: 把把 n =2 、 r =1帶入上面的牛頓二項(xiàng)式帶入上面的牛頓二項(xiàng)式, (1-x)-2 = 1+2x+3x2+nxn-1+. 因此因此 x/(1-x)2=x+2x2 + 3x3+nxn +. 微分

17、微分, 我們得到我們得到 （1+x)/(1-x)3=1+22x+32x2+n2xn-1+. 乘乘 x, 得到得到 x(1+x)/(1-x)3.34例題例題 (續(xù)續(xù)) 求解滿足初始值求解滿足初始值 h0 = 1 和和 h1 = -2的遞推的遞推關(guān)系關(guān)系 hn = 5hn-1 6 hn-2, (n2).提示提示: 令令 g(x) = h0+h1x+h2x2+hnxn+. 為為 h0, h1, h2, , hn 的生成函數(shù)。此時，的生成函數(shù)。此時，我們有下列方程我們有下列方程 35g(x) = h0+h1x+h2x2+hnxn+.-5xg(x) = -5h0 x -5h1x2 - 5h2x3 - 5

18、hn-1 xn -. 6x2 g(x) = 6h0 x2 +6h1x3 +6h2x4 +6hn-2xn +. 將三個方程相加將三個方程相加, 得到得到(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)36通過牛頓二項(xiàng)定理通過牛頓二項(xiàng)定理(1-2x)-1 = 1+2x+22x2+2nxn.(1-3x)-1 = 1+3x+32x2+3nxn.于是于是, g(x) = 1 + (

19、-2)x + (-15)x2 + (52n 43n)xn+可以得到可以得到 hn = 52n 43n (n = 0, 1, 2, ).37練習(xí) 滿足滿足h0 = 0, h1 = 1 ，h2 = -1的遞推關(guān)系的遞推關(guān)系 hn + hn-1 16 hn-2+20hn-3 = 0 (n3)求求hn的一般公式。的一般公式。38一個幾何的例子一個幾何的例子39劃分凸多邊形的方法劃分凸多邊形的方法通過畫出在區(qū)域內(nèi)部不相交的對角線將具通過畫出在區(qū)域內(nèi)部不相交的對角線將具有有n+1 條邊的凸多邊形區(qū)域分成三角形區(qū)域，令條邊的凸多邊形區(qū)域分成三角形區(qū)域，令hn 表示分成三角形區(qū)域的方法數(shù)。定義表示分成三角形區(qū)

20、域的方法數(shù)。定義h1 =1. 則則 hn 滿足遞推關(guān)系滿足遞推關(guān)系 hn = h1hn-1+h2hn-2+hn-1h1, (n2). 該遞推關(guān)系的解為該遞推關(guān)系的解為 hn = n-1C(2n-2, n-1), (n=1, 2 , 3, ).40指數(shù)生成函數(shù)指數(shù)生成函數(shù)41復(fù)習(xí)復(fù)習(xí): ex的泰勒級數(shù)的泰勒級數(shù)! 21!20nxxxnxennnx42指數(shù)生成函數(shù)的定義指數(shù)生成函數(shù)的定義 序列序列 h0, h1, h2, , hn, 的指數(shù)生成函數(shù)的指數(shù)生成函數(shù) !2!)(22100)(nxhxhxhhnxhxgnnnnne43例子例子 令令n為一正整數(shù)為一正整數(shù).確定數(shù)列確定數(shù)列P(n, 0),

21、 P(n, 1), P(n, 2), , P(n, n),的指數(shù)生成函數(shù)的指數(shù)生成函數(shù),其中其中 P(n, k) 表示表示n-元素集的元素集的k-排列的個數(shù)排列的個數(shù),對對于于k = 0, 1, , n 其值為其值為n!/(n-k)! .指數(shù)生指數(shù)生成函數(shù)為成函數(shù)為44因此因此, (1+x)n 既是序列既是序列P(n, 0), P(n, 1), P(n, 2), , P(n, n) 的指數(shù)生成函數(shù)又是序列的指數(shù)生成函數(shù)又是序列C(n, 0), C(n, 1), C(n, 2), , C(n, n)的常規(guī)生成函數(shù)的常規(guī)生成函數(shù).nnnexxnnxnnnxnxnnPxnPxnPnPxg)1 (!

22、0 !)!2( ! 2!1!),(! 2)2 ,() 1 ,()0 ,()(22)(45練習(xí)練習(xí) (續(xù)續(xù)) 序列序列1, 1, 1, , 1, . 的指數(shù)生成函數(shù)是的指數(shù)生成函數(shù)是 更一般的更一般的,如果如果a是一個實(shí)數(shù)是一個實(shí)數(shù),那么序列那么序列a0 = 1, a, a2, , an, . 的指數(shù)生成函數(shù)是的指數(shù)生成函數(shù)是xnneenxxg 0)(!)(.!)(!)(00)(axnnnnneenaxnxaxg46定理定理 令令S為多重集為多重集 n1.a1, n2.a2, nk.ak ,其中其中 n1, n2, , nk 均為非負(fù)整數(shù)均為非負(fù)整數(shù).令令hn 是是S的的n-排列數(shù)排列數(shù). 則序列則序列h0, h1, h2,hn, 的指數(shù)的指數(shù)生成函數(shù)生成函數(shù)g(e)(x)由由 g(e)(x)= fn1(x) fn2(x) .