离散数学--.生成函数及其应用精选文档.ppt

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

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

2、在上面式子中用 z代替代替 z，则有，则有 4本讲稿第四页，共二十五页生成函数的定义生成函数的定义定定义义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本讲稿第五页，共二十五页生成函数的性质生成函数的性质1.bn=an,为为常数，常数，则则B(x)=A(x)=an+bn,则则C(x)=A(x)+B(x)5bn=an+l,则则 6本

3、讲稿第六页，共二十五页生成函数的性质生成函数的性质(续续)8bn=nan,为常数，为常数，则则B(x)=A(x)9bn=nan,则则B(x)=xA(x)7本讲稿第七页，共二十五页证明证明证证8本讲稿第八页，共二十五页有关级数的结果有关级数的结果 9本讲稿第九页，共二十五页由序列求生成函数由序列求生成函数例例1 求序列求序列an的生成函数的生成函数 (1)an=7 3n (2)an=n(n+1)解解10本讲稿第十页，共二十五页由生成函数求序列通项由生成函数求序列通项例例2 已知已知 an 的生成函数为的生成函数为求求an解解 .11本讲稿第十一页，共二十五页生成函数的应用生成函数的应用求解递推方

4、程求解递推方程计数多重集的计数多重集的r组合数组合数不定方程的解不定方程的解整数拆分整数拆分 12本讲稿第十二页，共二十五页求解递推方程求解递推方程例例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本讲稿第十三页，共二十五页求解递推方程求解递推方程(续续)例例2 解：设解：设 hn 的生成函数为的生成函数为 14本讲稿第十四页，共二十五页求解递推方程求解递推方程(续续)15本讲稿第十

5、五页，共二十五页多重集的多重集的r-组合数组合数S=n1 a1,n2 a2,nk ak 的的 r 组组合数就是不定方程合数就是不定方程 x1+x2+xk=r xi ni i=1,2,k的非的非负负整数解的个数整数解的个数 的展开式中的展开式中 yr 的系数的系数 生成函数生成函数16本讲稿第十六页，共二十五页多重集的多重集的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

6、+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 17本讲稿第十七页，共二十五页不定方程解的个数不定方程解的个数 基本的不定方程基本的不定方程 x1+x2+xk=r，xi为为自然数自然数 18本讲稿第十八页，共二十五页不定方程解的个数不定方程解的个数(续续)带限制条件的不定方程带限制条件的不定方程 x1+x2+xk=r，li

7、 xi ni带系数的不定方程带系数的不定方程 p1x1+p2x2+pkxk=r，xi N生成函数生成函数生成函数生成函数19本讲稿第十九页，共二十五页重量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+y122

8、0本讲稿第二十页，共二十五页有序无序不重复 4=4 4=1+3 4=3+1 4=4 4=1+3重复 4=4 4=1+3 4=3+1 4=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表示成若干个正整数之和表示成若干个正整数之和.拆分的分类拆分的分类21本讲稿第二十一页，共二十五页无序拆分无序拆分基本模型：将基本模型：将N无序拆分成正整数无序拆分成正整数 a1,a2,an a1x1+a2x2+anxn=N 不允许重复不允许重复 允许

9、重复允许重复22本讲稿第二十二页，共二十五页实例实例例例5 证证明任何正整数都可以唯一表示成明任何正整数都可以唯一表示成 2 进进制数制数.对应对应于将任何正整数于将任何正整数N拆分成拆分成 2 的的幂幂，20,21,22,23,且不允且不允许许重复重复.生成函数生成函数 对于所有的对于所有的 n,系数是系数是1，这就证明唯一的表法，这就证明唯一的表法.23本讲稿第二十三页，共二十五页无序拆分无序拆分个数限制个数限制 例例6 给给定定r,求求N允允许许重复无序拆分成重复无序拆分成 k个数个数(k r)的方法数的方法数解解 N允允许许重复无序拆分成重复无序拆分成 k个数（个数（k r）的方案）的

10、方案 N允允许许重复无序拆分成正整数重复无序拆分成正整数 k（k r）的方案）的方案做下述做下述 Ferrers图图 将将图图以以 y=x对对角角线线翻翻转转180度，度，得到得到 共共轭轭的的Ferrers图图.16=6+5+3+2（k 4）对应对应每个数不超每个数不超过过4的拆分的拆分:16=4+4+3+2+2+1 这这种拆分数的生成函数种拆分数的生成函数为为 24本讲稿第二十四页，共二十五页有序拆分有序拆分定理定理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本讲稿第二十五页，共二十五页