离散数学--102生成函数及其应用ppt课件

1、10.2 生成函数及其应用生成函数及其应用 10.2.1牛顿二项式定理与牛顿二项式系数牛顿二项式定理与牛顿二项式系数 10.2.2 生成函数的定义及其性质生成函数的定义及其性质 10.2.3 生成函数的应用生成函数的应用牛顿二项式系数牛顿二项式系数 0!)1).(1(0100nnnrrrnnnr定义定义10.5 设设 r 为实数，为实数，n为整数，引入形式符号为整数，引入形式符号65!6)5)(4)(3)(2)(52 1285! 42)5)(3(1)1(! 4)321)(221)(121(2142/14 4! 323434 称为牛顿二项式系数称为牛顿二项式系数. . 例如例如牛顿二项式定理牛顿

2、二项式定理定理定理10.6 （牛顿二项式定理）（牛顿二项式定理）设设为实数，则对一切实数为实数，则对一切实数x, y，|x/y|1，有，有!)1).(1(,)(0nnnyxnyxnnn 其其中中!) 1.(1)(nnmmmnmn ） nnmnnmmmnn1) 1(!) 1).(1() 1(假设假设= m，其中，其中m为正整数，那么为正整数，那么重要展开式重要展开式1|1)1()1(1)1(0 zznnmzznnnmm1|1)1(1)1(0 zznnmzznnmm 022)1()1(1, 2.111, 1nnxnxmxxxm令令x=z，y=1，那么牛顿二项式定理就变成，那么牛顿二项式定理就变成

3、在上面式子中用在上面式子中用z代替代替 z ，则有，则有 生成函数的定义生成函数的定义定义定义10.6 设序列设序列an，构造形式幂级数，构造形式幂级数 G(x) = a0 + a1x + a2x2 + + an xn + 称称G(x)为序列为序列an的生成函数的生成函数. 例如，例如，C(m,n)的生成函数为的生成函数为 (1+x)m给定正整数给定正整数k, kn的生成函数为的生成函数为 G(x) =1+ kx + k2x2 + k3x3 + = kx 11生成函数的性质生成函数的性质)()()(,. 30 xBxAxCbacniinin 则则)()(,0. 4xAxxBlnalnbllnn

4、 则则1. bn=an, 为常数，则为常数，则B(x)= A(x)2. cn=an+bn, 则则C(x)=A(x)+B(x) llnnnxxaxAxB 10)()(5bn= an+l , 那么那么 xxAxBabniin 1)()(,. 60则则生成函数的性质生成函数的性质(续续)xxxAAxBaAabniniin 1)()1()()1(,. 70则则收收敛敛，且且 xnndxxAxxBnab0)(1)(,1.108bn= nan, 为常数，则为常数，则B(x)=A(x)9bn= nan, 则则B(x)=xA(x)证明证明xxAxxaxxaxaxBxaxaxaxbxaxaxbabnnnnnnn

5、n 1)(.11.1111)(.101010100 xxAxBabniin 1)()(,. 60则则证证有关级数的结果有关级数的结果 112111111121212102121001222)1(1)!1(2!2)!22()1(1!2)32.(531)1(1!)1).(1(1)1()1(1111kkkkkkkkkkkkkkkkknnnnnxkkkxkkkxkkxkkxkxxxxx 3222202010112110)1(2)1()(,)1()()1(1)(,1)()(),()()2(xxxxxGxxdxxGxxHxxxdxxHnxxHxHxnxdxxGxnnxnnnnx 由序列求生成函数由序列求生

6、成函数例例1 求序列求序列an的生成函数的生成函数 (1) an = 7 3n (2) an = n(n+1)xxxxGnnnnn317)3(737)()1(00 解解由生成函数求序列通项由生成函数求序列通项xxxxG21632(2 ）xxxxxxxxxxGnnnnn323)2(2321221632(0102 ） 1, 7321,221nnann例例2 知知 an 的生成函数为的生成函数为求求an解解 . 生成函数的应用生成函数的应用 求解递推方程求解递推方程 计数多重集的计数多重集的r组合数组合数 不定方程的解不定方程的解 整数拆分整数拆分 求解递推方程求解递推方程例例1 an 5an1 +

7、 6an2 = 0 a0 = 1, a1 = 2 nnnnnnnnnaxxxxxxxxG3425342531421565171)(002 G(x) = a0 + a1x + a2x2 + a3x3 + 5x G(x) = 5a0 x 5a1x2 5a2x3 - 6x2 G(x) = +6a0 x2 +6a1x3 + (15x+6x2)G(x) = a0 + (a15a0)x 求解递推方程求解递推方程(续续) 12,111hnhhhnkknkn例例2 xxHxhxHxhhhxxhxhxHnnnnnkknknlllkkk )()()(12211112 1)(nnnxhxH解：设解：设 hn 的生成

8、函数为的生成函数为 122112212)1(1222)1()4(1222)1(1 212141(21212)41(1)( 0,)()(112211212121nnnhxnnnxnnnxnnnxxxHxxHxHnnnnnnnnnnnnn）求解递推方程求解递推方程(续续)多重集的多重集的r-组合数组合数S = n1a1, n2a2, , nkak 的的 r 组合数就是不定组合数就是不定方程方程 x1 + x2 + + xk = r xi ni i = 1,2,k的非负整数解的个数的非负整数解的个数 的展开式中的展开式中 yr 的系数的系数 ).1).(.1)(.1()(21knnnyyyyyyyG

9、 生成函数生成函数多重集的多重集的r-组合数组合数(续续) 例例3 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+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,

10、 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 不定方程解的个数不定方程解的个数 0001)1(!)1).(1)()1()(!)1).(1)()1(1.)1()(rrrrrrrrkkyrrkyrrkkkyrrkkkyyyG rrkN1 基本的不定方程基本的不定方程 x1 + x2 + + xk = r ， xi为自然数为自然数 不定方程解的个数不定方程解的个数(续续).(.).)(.()(111222111knnnllnllnllyyyyyyyyyyG

11、 .)1(.)1.)(1()(2222211 kkppppppyyyyyyyG带限制条件的不定方程带限制条件的不定方程 x1 + x2 + + xk = r，li xi ni带系数的不定方程带系数的不定方程 p1x1 + p2x2 + + pkxk = r，xiN生成函数生成函数生成函数生成函数重量重量012345678910 11 12方案方案1121212121211实例实例例例4 14 1克砝码克砝码2 2个，个，2 2克砝码克砝码1 1个，个，4 4克砝码克砝码2 2个，问能称出个，问能称出哪些重量，方案有多少？哪些重量，方案有多少？解：解： x1 + 2 x2 + 4 x3 = r

12、x1 + 2 x2 + 4 x3 = r 0 0 x1 x1 2, 0 2, 0 x2 x2 1, 0 1, 0 x3 x3 2 2 G(y) = (1+y+y2)(1+y2)(1+y4+y8) G(y) = (1+y+y2)(1+y2)(1+y4+y8) = = 1+y+2y2+y3+2y4+y5+2y6+y7+2y8+y9+2y10+y11+y121+y+2y2+y3+2y4+y5+2y6+y7+2y8+y9+2y10+y11+y12有序有序无序无序不重复不重复 4 = 4 4 = 1+3 4 = 3+1 4 = 4 4 = 1+3重复重复 4 = 4 4 = 1+3 4 = 3+1 4

13、= 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表示成若干个正整数之和表示成若干个正整数之和. 拆分的分类拆分的分类无序拆分无序拆分)1).(1)(1()(21naaayyyyG 基本模型：将基本模型：将N无序拆分成正整数无序拆分成正整数 a1, a2, , an a1x1 + a2x2 + + anxn = N 不允许重复不允许重复 )1).(1)(1(1.)1(.)1.)(1()(2122

14、11222nnnaaaaaaaaayyyyyyyyyyG 允许重复允许重复实例实例例例5 证明任何正整数都可以唯一表示成证明任何正整数都可以唯一表示成 2 进制数进制数.对应于将任何正整数对应于将任何正整数N拆分成拆分成 2 的幂，的幂， 20, 21, 22, 23, , 且不允许重复且不允许重复. 生成函数生成函数 04824284211.111111).1)(1)(1)(1()(nnyyyyyyyyyyyyyG对于所有的对于所有的 n, 系数是系数是1，这就证明唯一的表法，这就证明唯一的表法.无序拆分无序拆分个数限制个数限制 例例6 给定给定r,求求N允许重复无序拆分成允许重复无序拆分成

15、 k个数个数 (kr)的方法数的方法数解解 N允许重复无序拆分成允许重复无序拆分成 k个数个数kr的方案的方案 N允许重复无序拆分成正整数允许重复无序拆分成正整数 kkr的方案的方案做下述做下述 Ferrers图图 将图以将图以 y =x对角线翻转对角线翻转180度，度，得到得到 共轭的共轭的Ferrers图图. 16 = 6+5+3+2 （k 4）对应每个数不超过对应每个数不超过4的拆分的拆分: 16 = 4+4+3+2+2+1 这种拆分数的生成函数为这种拆分数的生成函数为 )1).(1)(1(1)(2ryyyyG 有序拆分有序拆分NSSSriaSrikii .0,., 2, 1,211 Nr