资源预览内容
第1页 / 共25页
第2页 / 共25页
第3页 / 共25页
第4页 / 共25页
第5页 / 共25页
第6页 / 共25页
第7页 / 共25页
第8页 / 共25页
第9页 / 共25页
第10页 / 共25页
亲,该文档总共25页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
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 + 称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),解,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-组合数(续),例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, 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+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,无序拆分个数限制,例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 做任意重复的有序拆分,方案数为,不允许重复有序拆分:不允许重复无序拆分 + 全排列,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号