离散数学--.生成函数及其应用优秀课件.ppt

《离散数学--.生成函数及其应用优秀课件.ppt》由会员分享，可在线阅读，更多相关《离散数学--.生成函数及其应用优秀课件.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学-.生成函数生成函数及其应用及其应用1第1页，本讲稿共25页牛顿二项式系数牛顿二项式系数定定义义10.5 设设 r 为实为实数，数，n为为整数，引入形式符号整数，引入形式符号称称为为牛牛顿顿二二项项式系数式系数.例如例如2第2页，本讲稿共25页牛顿二项式定理牛顿二项式定理定理定理10.6（牛（牛顿顿二二项项式定理）式定理）设设 为实为实数，数，则对则对一切一切实实数数x,y，|x/y|1，有，有若若=m，其中，其中m为为正整数，那么正整数，那么3第3页，本讲稿共25页重要展开式重要展开式令令x=z，y=1，那么牛，那么牛顿顿二二项项式定理就式定理就变变成成 在上面式子中用z代替

2、 z，则有 4第4页，本讲稿共25页生成函数的定义生成函数的定义定定义义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+=5第5页，本讲稿共25页生成函数的性质生成函数的性质1.bn=an,为为常数，常数，则则B(x)=A(x)=an+bn,则则C(x)=A(x)+B(x)5bn=an+l,则 6第6页，本讲稿共25页生成函数的性质生成

3、函数的性质(续续)8bn=nan,为常数，为常数，则则B(x)=A(x)9bn=nan,则则B(x)=xA(x)7第7页，本讲稿共25页证明证明证8第8页，本讲稿共25页有关级数的结果有关级数的结果 9第9页，本讲稿共25页由序列求生成函数由序列求生成函数例例1 求序列求序列an的生成函数的生成函数 (1)an=7 3n (2)an=n(n+1)解10第10页，本讲稿共25页由生成函数求序列通项由生成函数求序列通项例2 已知 an 的生成函数为求求an解解 .11第11页，本讲稿共25页生成函数的应用生成函数的应用求解递推方程求解递推方程计数多重集的计数多重集的r组合数组合数不定方程的解不定方

4、程的解整数拆分整数拆分 12第12页，本讲稿共25页求解递推方程求解递推方程例例1 an 5an 1+6an 2=0 a0=1,a1=2 G(x)=a0+a1x+a2x2+a3x3+5x G(x)=5a0 x 5a1x2 5a2x3-6x2 G(x)=+6a0 x2+6a1x3+(1 5x+6x2)G(x)=a0+(a1 5a0)x 13第13页，本讲稿共25页求解递推方程求解递推方程(续续)例2 解：设 hn 的生成函数为 14第14页，本讲稿共25页求解递推方程求解递推方程(续续)15第15页，本讲稿共25页多重集的多重集的r-组合数组合数S=n1 a1,n2 a2,nk ak 的的 r

5、组组合数就是不定方程合数就是不定方程 x1+x2+xk=r xi ni i=1,2,k的非的非负负整数解的个数整数解的个数 的展开式中 yr 的系数 生成函数16第16页，本讲稿共25页多重集的多重集的r-组合数组合数(续续)例例3 S=3 a,4 b,5 c 的的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,

6、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 17第17页，本讲稿共25页不定方程解的个数不定方程解的个数 基本的不定方程基本的不定方程 x1+x2+xk=r，xi为为自然数自然数 18第18页，本讲稿共25页不定方程解的个数不定方程解的个数(续续)带限制条件的不定方程带限制条件的不定方程 x1+x2+xk=r，li xi ni带系数的不定方程带系数的不定方程 p1x1+p2x2+pkxk=r，xi N生成函数生成函数生成函数19第19页，本

7、讲稿共25页重量012345678910 11 12方案1121212121211实例实例例例4 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+y1220第20页，本讲稿共25页有序无序不重复 4=4 4=1+3 4=3+1 4=4 4=1+3重复 4=4 4=1+3 4=3+1 4=2+

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

9、21,22,23,且不允且不允许许重复重复.生成函数生成函数 对于所有的 n,系数是1，这就证明唯一的表法.23第23页，本讲稿共25页无序拆分无序拆分个数限制个数限制 例例6 给给定定r,求求N允允许许重复无序拆分成重复无序拆分成 k个数个数(k r)的方法数的方法数解解 N允允许许重复无序拆分成重复无序拆分成 k个数（个数（k r）的方案）的方案 N允允许许重复无序拆分成正整数重复无序拆分成正整数 k（k r）的方案）的方案做下述做下述 Ferrers图图 将将图图以以 y=x对对角角线线翻翻转转180度，度，得到得到 共共轭轭的的Ferrers图图.16=6+5+3+2（k 4）对应对应

10、每个数不超每个数不超过过4的拆分的拆分:16=4+4+3+2+2+1 这这种拆分数的生成函数种拆分数的生成函数为为 24第24页，本讲稿共25页有序拆分有序拆分定理定理10.7 将将N允允许许重复地有序拆分成重复地有序拆分成 r 个部分的方案数个部分的方案数为为 C(N 1,r 1).证证 设设 N=a1+a2+ar 是是满满足条件的拆分，足条件的拆分，则则令令 r 1个个Si 取值为取值为1,2,N 1，方法数为，方法数为 C(N 1,r 1).推论推论 对对N 做任意重复的有序拆分，方案数为做任意重复的有序拆分，方案数为不允许重复有序拆分：不允许重复无序拆分+全排列25第25页，本讲稿共25页