生成函数及其应用.ppt

《生成函数及其应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、10.2生成函数及其应用10.2.1牛顿二项式定理与牛顿二项式系数10.2.2生成函数的定义及其性质10.2.3生成函数的应用1牛顿二项式系数定义10.5设r为实数，n为整数，引入形式符号称为牛顿二项式系数.例如2牛顿二项式定理定理10.6（牛顿二项式定理）设为实数，则对一切实数x,y，

2、x/y

3、<1，有若=m，其中m为正整数，那么3重要展开式令x=z，y=1，那么牛顿二项式定理就变成在上面式子中用z代替z，则有4生成函数的定义定义10.6设序列{an}，构造形式幂级数G(x)=a0+a1x+a2x2+…+anxn+…称G(x)为序列{an}的生成函数.例如，{

4、C(m,n)}的生成函数为(1+x)m给定正整数k,{kn}的生成函数为G(x)=1+kx+k2x2+k3x3+…=5生成函数的性质1.bn=an,为常数，则B(x)=A(x)2.cn=an+bn,则C(x)=A(x)+B(x)5．bn=an+l,则6生成函数的性质(续)8．bn=nan,为常数，则B(x)=A(x)9．bn=nan,则B(x)=xA(x)7证明证8有关级数的结果9由序列求生成函数例1求序列{an}的生成函数(1)an=7·3n(2)an=n(n+1)解10由生成函数求序列通项例2已知{an}的生成函数为求an解.11生成函数的应用求解递推

5、方程计数多重集的r组合数不定方程的解整数拆分12求解递推方程例1an–5an1+6an2=0a0=1,a1=2G(x)=a0+a1x+a2x2+a3x3+…5xG(x)=5a0x5a1x25a2x3-…6x2G(x)=+6a0x2+6a1x3+…(15x+6x2)G(x)=a0+(a15a0)x13求解递推方程(续)例2解：设{hn}的生成函数为14求解递推方程(续)15多重集的r-组合数S={n1a1,n2a2,…,nkak}的r组合数就是不定方程x1+x2+…+xk=rxinii=1,2,…,k的非负整数解的个数的展开式中yr的系数生成函数

6、16多重集的r-组合数(续)例3S={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},{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

7、,c,c,c,c}17不定方程解的个数基本的不定方程x1+x2+…+xk=r，xi为自然数18不定方程解的个数(续)带限制条件的不定方程x1+x2+…+xk=r，lixini带系数的不定方程p1x1+p2x2+…+pkxk=r，xiN生成函数生成函数19实例重量0123456789101112方案1121212121211例41克砝码2个，2克砝码1个，4克砝码2个，问能称出哪些重量，方案有多少？解：x1+2x2+4x3=r0x12,0x21,0x32G(y)=(1+y+y2)(1+y2)(1+y4+y8)=1+y+2y2+y3+2y4+y5+2y6+

8、y7+2y8+y9+2y10+y11+y1220正整数拆分有序无序不重复4=44=1+34=3+14=44=1+3重复4=44=1+34=3+14=2+24=2+1+14=1+2+14=1+1+24=1+1+1+14=44=1+34=2+24=2+1+14=1+1+1+1拆分的定义：将给定正整数N表示成若干个正整数之和.拆分的分类21无序拆分基本模型：将N无序拆分成正整数a1,a2,…,ana1x1+a2x2+…+anxn=N不允许重复允许重复22实例例5证明任何正整数都可以唯一表示成2进制数.对应于将任何正整数N拆分成2的幂，20,21,22,23,…,且不允许重复.

9、生成函数对于所有的n,系数是1，这就证明唯一的表法.23无序拆分——个数限制例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）对应每个数不超过4的拆分:16=4+4+3+2+2+1这种拆分数的生成函数为24有序拆分定理10.7将N允许重复地有序拆分成r个部分的方案数为C(N1,r1).证设N=a1+a2+…+ar是满足条件的拆分