《清华离散数学(第2版)：10.2》由会员分享，可在线阅读，更多相关《清华离散数学(第2版)：10.2（25页珍藏版）》请在金锄头文库上搜索。
1、1,10.2 生成函数及其应用,10.2.1牛顿二项式定理与牛顿二项式系数 10.2.2 生成函数的定义及其性质 10.2.3 生成函数的应用,2,牛顿二项式系数,定义10.5 设 r 为实数，n为整数，引入形式符号,称为牛顿二项式系数. 例如,3,牛顿二项式定理,定理10.6 （牛顿二项式定理） 设为实数，则对一切实数x, y，|x/y|1，有,若= m，其中m为正整数，那么,4,重要展开式,令x=z，y=1，那么牛顿二项式定理就变成,在上面式子中用z代替 z ，则有,5,生成函数的定义,定义10.6 设序列an，构造形式幂级数G(x) = a0 + a1x + a2x2 + + an xn
2、 + 称G(x)为序列an的生成函数. 例如， C(m,n)的生成函数为 (1+x)m 给定正整数k, kn的生成函数为 G(x) =1+ kx + k2x2 + k3x3 + =,6,生成函数的性质,1. bn=an, 为常数，则B(x)= A(x) 2. cn=an+bn, 则C(x)=A(x)+B(x),5bn= an+l , 则,7,生成函数的性质(续),8bn= nan, 为常数，则B(x)=A(x) 9bn= nan, 则B(x)=xA(x),8,证明,证,9,有关级数的结果,10,由序列求生成函数,例1 求序列an的生成函数(1) an = 7 3n (2) an = n(n+1
3、),解,11,由生成函数求序列通项,例2 已知 an 的生成函数为,求an 解,.,12,生成函数的应用,求解递推方程 计数多重集的r组合数 不定方程的解 整数拆分,13,求解递推方程,例1 an 5an1 + 6an2 = 0a0 = 1, a1 = 2,14,求解递推方程(续),例2,解：设 hn 的生成函数为,15,求解递推方程(续),16,多重集的r-组合数,S = n1a1, n2a2, , nkak 的 r 组合数就是不定方程x1 + x2 + + xk = r xi ni i = 1,2,k 的非负整数解的个数,的展开式中 yr 的系数,生成函数,17,多重集的r-组合数(续),
4、例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, c , a, a, b, b, b, b, c, c, c, c , a, a, b, b
5、, b, c, c, c, c, c , a, b, b, b, b, c, c, c, c, c ,18,不定方程解的个数,基本的不定方程x1 + x2 + + xk = r ， xi为自然数,19,不定方程解的个数(续),带限制条件的不定方程x1 + x2 + + xk = r，li xi ni,带系数的不定方程p1x1 + p2x2 + + pkxk = r，xiN 生成函数,生成函数,20,实例,例4 1克砝码2个，2克砝码1个，4克砝码2个，问能称出 哪些重量，方案有多少？ 解： x1 + 2 x2 + 4 x3 = r0 x1 2, 0 x2 1, 0 x3 2 G(y) = (1
6、+y+y2)(1+y2)(1+y4+y8) = 1+y+2y2+y3+2y4+y5+2y6+y7+2y8+y9+2y10+y11+y12,21,正整数拆分,拆分的定义：将给定正整数N表示成若干个正整数之和. 拆分的分类,22,无序拆分,基本模型：将N无序拆分成正整数 a1, a2, , ana1x1 + a2x2 + + anxn = N不允许重复,允许重复,23,实例,例5 证明任何正整数都可以唯一表示成 2 进制数. 对应于将任何正整数N拆分成 2 的幂，20, 21, 22, 23, , 且不允许重复. 生成函数,对于所有的 n, 系数是1，这就证明唯一的表法.,24,无序拆分个数限制,
7、例6 给定r,求N允许重复无序拆分成 k个数 (kr)的方法数 解 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 这种拆分数的生成函数为,25,有序拆分,定理10.7 将N允许重复地有序拆分成 r 个部分的方案数为 C(N1,r1). 证 设 N= a1+a2+ar 是满足条件的拆分，则令,r1个Si 取值为1,2,N1，方法数为 C(N1,r1). 推论 对N 做任意重复的有序拆分，方案数为,不允许重复有序拆分：不允许重复无序拆分 + 全排列,
