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

离散数学--.生成函数及其应用1第一页，共二十五页，2022年，8月28日牛顿二项式系数定义10.5设r为实数，n为整数，引入形式符号称为牛顿二项式系数.例如2第二页，共二十五页，2022年，8月28日牛顿二项式定理定理10.6

（牛顿二项式定理）设为实数，则对一切实数x,y，|x/y|<1，有若=m，其中m为正整数，那么3第三页，共二十五页，2022年，8月28日重要展开式令x=z，y=1，那么牛顿二项式定理就变成

在上面式子中用z代替

z，则有

4第四页，共二十五页，2022年，8月28日生成函数的定义定义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第五页，共二十五页，2022年，8月28日生成函数的性质1.bn=an,为常数，则B(x)=A(x)2.cn=an+bn,则C(x)=A(x)+B(x)5．bn=an+l,则

6第六页，共二十五页，2022年，8月28日生成函数的性质(续)8．bn=nan,为常数，则B(x)=A(x)9．bn=nan,则B(x)=xA(x)7第七页，共二十五页，2022年，8月28日证明证8第八页，共二十五页，2022年，8月28日有关级数的结果

9第九页，共二十五页，2022年，8月28日由序列求生成函数例1

求序列{an}的生成函数

(1)an=7·3n

(2)an=n(n+1)解10第十页，共二十五页，2022年，8月28日由生成函数求序列通项例2

已知{an}的生成函数为求an解.11第十一页，共二十五页，2022年，8月28日生成函数的应用求解递推方程计数多重集的r组合数不定方程的解整数拆分

12第十二页，共二十五页，2022年，8月28日求解递推方程例1

an–5an1+6an2=0

a0=1,a1=

2

G(x)=a0+a1x+a2x2+a3x3+…5xG(x)=5a0x5a1x25a2x3-…6x2

G(x)=+6a0x2+6a1x3+…(15x+6x2)G(x)=a0+(a15a0)x

13第十三页，共二十五页，2022年，8月28日求解递推方程(续)例2解：设{hn}的生成函数为

14第十四页，共二十五页，2022年，8月28日求解递推方程(续)15第十五页，共二十五页，2022年，8月28日多重集的r-组合数S={n1a1,n2a2,…,nkak}的

r

组合数就是不定方程

x1+x2+…+xk

=r

xi

nii=1,2,…,k的非负整数解的个数的展开式中

yr的系数生成函数16第十六页，共二十五页，2022年，8月28日多重集的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}17第十七页，共二十五页，2022年，8月28日不定方程解的个数基本的不定方程

x1+x2+…+xk=r，xi为自然数

18第十八页，共二十五页，2022年，8月28日不定方程解的个数(续)带限制条件的不定方程

x1+x2+…+xk

=r，li

xi

ni带系数的不定方程

p1x1+p2x2+…+pkxk=r，xiN生成函数生成函数19第十九页，共二十五页，2022年，8月28日重量0123456789101112方案1121212121211实例例4

1克砝码2个，2克砝码1个，4克砝码2个，问能称出哪些重量，方案有多少？解：x1+2x2+4x3=r0

x12,0x21,0

x32

G(y)=(1+y+y2)(1+y2)(1+y4+y8)=1+y+2y2+y3+2y4+y5+2y6+y7+2y8+y9+2y10+y11+y1220第二十页，共二十五页，2022年，8月28日有序无序不重复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第二十一页，共二十五页，2022年，8月28日无序拆分基本模型：将N无序拆分成正整数a1,a2,…,an

a1x1+a2x2+…+anxn

=N

不允许重复允许重复22第二十二页，共二十五页，2022年，8月28日实例例5

证明任何正整数都可以唯一表示成2进制数.对应于将任何正整数N拆分成2的幂，

20,21,22,23,…,且不允许重复.生成函数

对于所有的n,系数是1，这就证明唯一的表法.23第二十三页，共二十五页，2022年，8月28日无序拆分——个数限制

例6

给定r,求N允许重复无序拆分成k个数(kr)的方法数解N允许重复无序拆分成k个数（kr）的方案

N允许重复无序拆分成正整数k（kr）的方案做下述Ferrers图将图以y=x对角线翻转180度，得到共轭的Ferrers图.16=6+5+3+2（k4）对应每个数不超过4的拆分:16=4+4+3+2+2+1这种拆分数的生成函数为

24第二十四页，共二十五页，2022年，8月28日有序拆分定理10.7

将N允许重复地有序拆分成r个部分