离散数学生成函数及其应用.ppt

《离散数学生成函数及其应用.ppt》由会员分享，可在线阅读，更多相关《离散数学生成函数及其应用.ppt（25页珍藏版）》请在三一办公上搜索。

1、1,10.2 生成函数及其应用,牛顿二项式定理与牛顿二项式系数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

2、,n)的生成函数为(1+x)m给定正整数k,kn的生成函数为 G(x)=1+kx+k2x2+k3x3+=,6,生成函数的性质,1.bn=an,为常数，则B(x)=A(x)=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,生成函数的应用,求解递推方程计数多重集

3、的r组合数不定方程的解整数拆分,13,求解递推方程,例1 an 5an1+6an2=0 a0=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+4y

4、4+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生成函数,生成函数

5、,20,实例,例4 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+y12,21,正整数拆分,拆分的定义：将给定正整数N表示成若干个正整数之和.拆分的分类,22,无序拆分,基本模型：将N无序拆分成正整数 a1,a2,an a1x1+a2x2+anxn=N 不允许重复,允许重复,23,实例,例5 证明任何正整数都可以唯一表示成 2 进制数.对应于将任何正整数N

6、拆分成 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 做任意重复的有序拆分，方案数为,不允许重复有序拆分：不允许重复无序拆分+全排列,