1、13.4 生成函數及其應用牛頓二項式系數與牛頓二項式定理生成函數的定義生成函數的應用1牛頓二項式系數定義 設 r 為實數，n為整數，引入形式符號稱為牛頓二項式系數. 實例2牛頓二項式定理定理 （牛頓二項式定理）設為實數，則對一切實數x, y，|x/y|1，有若= m，其中m為正整數，那么3重要展開式令x=z，y=1，那么牛頓二項式定理就變成 在上面式子中用z代替 z ，則有 4生成函數定義定義 設序列an，構造形式冪級數 G(x) = a0 + a1x + a2x2 + + an xn + 稱G(x)為序列an的生成函數. 例如， C(m,n) 的生成函數為 (1+x)m給定正整數k, kn

2、的生成函數為 G(x) =1+ kx + k2x2 + k3x3 + = 5例14 求序列an的生成函數 (1) an = 7 3n (2) an = n(n+1)解由序列求生成函數6由生成函數求序列通項例15 已知 an 的生成函數為求an. 解7生成函數的應用求解遞推方程計數多重集的 r 組合數不定方程的解整數拆分 8求解遞推方程例16 an 5an1 + 6an2 = 0，a0 = 1, a1 = 2 G(x) = a0 + a1x + a2x2 + a3x3 + 5x G(x) = 5a0 x 5a1x2 5a2x3 - 6x2 G(x) = +6a0 x2 +6a1x3 + (15x

3、+6x2)G(x) = a0 + (a15a0)x 9例17 解：設 hn 的生成函數為 求解遞推方程10求解遞推方程11多重集的 r 組合數S = n1a1, n2a2, , nkak 的 r 組合數就是不定方程 x1 + x2 + + xk = r xi ni i = 1,2,k的非負整數解的個數 的展開式中 yr 的系數 生成函數12實例例18 S = 3a, 4b, 5c 的10 組合數解：生成函數G(y) = (1+y+y2+y3)(1+y+y2+y3+y4)(1+y+y2+y3+y4+y5) = (1+2y+3y2+4y3+4y4+3y5+2y6+y7)(1+y+y2+y3+y4+

4、y5) = (1 + +3y10+2y10+y10 + ) N = 6 組合方案 a, a, a, b, b, b, b, c, c, c , a, a, a, b, b, b, c, c, c, c , a, a, a, b, b, c, c, c, c, c , a, a, b, b, b, b, c, c, c, c , a, a, b, b, b, c, c, c, c, c , a, b, b, b, b, c, c, c, c, c 13不定方程解的個數基本的不定方程 x1 + x2 + + xk = r ， xi 為自然數 14推廣的不定方程帶限制條件的不定方程 x1 + x2

5、+ + xk = r，li xi ni帶系數的不定方程 p1x1 + p2x2 + + pkxk = r，xiN生成函數生成函數15重量0123456789101112方案1121212121211實例例19 1克砝碼2個，2克砝碼1個，4克砝碼2個，問能稱出哪些重量，方案有多少？解： x1 + 2 x2 + 4 x3 = r 0 x1 2, 0 x2 1, 0 x3 2 G(y) = (1+y+y2)(1+y2)(1+y4+y8) = 1+y+2y2+y3+2y4+y5+2y6+y7+2y8+y9+2y10+y11+y1216有序無序不重復 4 = 4 4 = 1+3 4 = 3+1 4 =

6、 4 4 = 1+3重復 4 = 4 4 = 1+3 4 = 3+1 4 = 2+2 4 = 2+1+1 4 = 1+2+1 4 = 1+1+2 4 = 1+1+1+1 4 = 4 4 = 1+3 4 = 2+2 4 = 2+1+1 4 = 1+1+1+1拆分的定義：將給定正整數N表示成若干個正整數之和. 正整數拆分17無序拆分基本模型：將N無序拆分成正整數 a1, a2, , an a1x1 + a2x2 + + anxn = N 不允許重復 允許重復18實例例20 證明任何正整數都可以唯一表示成 2 進制數.對應于將任何正整數N拆分成 2 的冪， 20, 21, 22, 23, , 且不允許重復. 對于所有的 n, 系數是1，這就證明唯一的表法.生成函數19解 N允許重復無序拆分成 k個數（kr）的方案 N允許重復無序拆分成正整數 k（kr）的方案做下述 Ferrers圖 將圖以 y =x 對角線翻轉180度，得到 共軛的Ferrers圖. 16 = 6+5+3+2 （k 4）對應每個數不超過4的拆分: 16 = 4+4+3+2+2+1 這種拆分數的生成函數為 大小k個數k例21 給定r, 求N允許重復無序拆分成 k個數 (kr)的方法數無序拆分：個數限制20定理 將N允許重復地有序拆分成 r 個部分的方案數為 C(N1,r1). 證