10.2生成函数及其应用

10.2生成函数及其应用10.2.1牛顿二项式定理与牛顿二项式系数10.2.2生成函数的定义及其性质10.2.3生成函数的应用1牛顿二项式系数20!)1)...(1(0100nnnrrrnnnr定义10.5设r为实数，n为整数，引入形式符号65!6)5)(4)(3)(2)((521285!42)5)(3(1)1(!4)321)(221)(121(2142/144!323434称为牛顿二项式系数.例如牛顿二项式定理3定理10.6（牛顿二项式定理）设为实数，则对一切实数x,y，|x/y|1，有!)1)...(1(,)(0nnnyxnyxnnn其中!)1...(1)((nnmmmnmn）nnmnnmmmnn1)1(!)1)...(1()1(若=m，其中m为正整数，那么重要展开式41||1)1()1(1)1(0zznnmzznnnmm1||1)1(1)1(0zznnmzznnmm022)1()1(1,2...111,1nnxnxmxxxm令x=z，y=1，那么牛顿二项式定理就变成在上面式子中用z代替z，则有生成函数的定义5定义10.6设序列{an}，构造形式幂级数G(x)=a0+a1x+a2x2+…+anxn+…称G(x)为序列{an}的生成函数.例如，{C(m,n)}的生成函数为(1+x)m给定正整数k,{kn}的生成函数为G(x)=1+kx+k2x2+k3x3+…=kx11生成函数的性质6)()()(,.30xBxAxCbacniinin则)()(,0.4xAxxBlnalnbllnn则1.bn=an,为常数，则B(x)=A(x)2.cn=an+bn,则C(x)=A(x)+B(x)llnnnxxaxAxB10)()(5．bn=an+l,则生成函数的性质(续)xxAxBabniin1)()(,.60则7xxxAAxBaAabniniin1)()1()()1(,.70则收敛，且xnndxxAxxBnab0)(1)(,1.108．bn=nan,为常数，则B(x)=A(x)9．bn=nan,则B(x)=xA(x)证明xxAxBabniin1)()(,.60则8xxAxxaxxaxaxBxaxaxaxbxaxaxbabnnnnnnnn1)(...11...1111)(.........101010100证有关级数的结果9112111111121212102121001222)1(1)!1(2!2)!22()1(1!2)32...(531)1(1!)1)...(1(1)1()1(1111kkkkkkkkkkkkkkkkknnnnnxkkkxkkkxkkxkkxkxxxxx由序列求生成函数103222202010112110)1(2)')1(()(,)1()()1(1)(,1)()(),()()2(xxxxxGxxdxxGxxHxxxdxxHnxxHxHxnxdxxGxnnxnnnnx例1求序列{an}的生成函数(1)an=7·3n(2)an=n(n+1)xxxxGnnnnn317)3(737)()1(00解由生成函数求序列通项11xxxxG21632(2）xxxxxxxxxxGnnnnn323)2(2321221632(0102）1,7321,221nnann例2已知{an}的生成函数为求an解.生成函数的应用求解递推方程计数多重集的r组合数不定方程的解整数拆分12求解递推方程13例1an–5an1+6an2=0a0=1,a1=2nnnnnnnnnaxxxxxxxxG3425342531421565171)(002G(x)=a0+a1x+a2x2+a3x3+…5xG(x)=5a0x5a1x25a2x3-…6x2G(x)=+6a0x2+6a1x3+…(15x+6x2)G(x)=a0+(a15a0)x求解递推方程(续)1412,111hnhhhnkknkn例2xxHxhxHxhhhxxhxhxHnnnnnkknknlllkkk)()()(122111121)(nnnxhxH解：设{hn}的生成函数为求解递推方程(续)15122112212)1(1222)1(])4(1222)1(1[212141(21212)41(1)(0,)()(112211212121nnnhxnnnxnnnxnnnxxxHxxHxHnnnnnnnnnnnnn）多重集的r-组合数16S={n1a1,n2a2,…,nkak}的r组合数就是不定方程x1+x2+…+xk=rxinii=1,2,…,k的非负整数解的个数的展开式中yr的系数)...1)...(...1)(...1()(21knnnyyyyyyyG生成函数多重集的r-组合数(续)17例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,c,c,c,c}不定方程解的个数180001)1(!)1)...(1)(()1()(!)1)...(1)(()1(1...)1()(rrrrrrrrkkyrrkyrrkkkyrrkkkyyyGrrkN1基本的不定方程x1+x2+…+xk=r，xi为自然数不定方程解的个数(续)19)...(...)...)(...()(111222111knnnllnllnllyyyyyyyyyyG...)1(......)1...)(1()(2222211kkppppppyyyyyyyG带限制条件的不定方程x1+x2+…+xk=r，lixini带系数的不定方程p1x1+p2x2+…+pkxk=r，xiN生成函数生成函数实例20重量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+y7+2y8+y9+2y10+y11+y12正整数拆分21有序无序不重复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表示成若干个正整数之和.拆分的分类无序拆分22)1)...(1)(1()(21naaayyyyG基本模型：将N无序拆分成正整数a1,a2,…,ana1x1+a2x2+…+anxn=N不允许重复)1)...(1)(1(1...)1(......)1...)(1()(212211222nnnaaaaaaaaayyyyyyyyyyG允许重复实例23例5证明任何正整数都可以唯一表示成2进制数.对应于将任何正整数N拆分成2的幂，20,21,22,23,…,且不允许重复.生成函数04824284211...111111)...1)(1)(1)(1()(nnyyyyyyyyyyyyyG对于所有的n,系数是1，这就证明唯一的表法.无序拆分——个数限制24例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这种拆分数的生成函数为)1)...(1)(1(1)(2ryyyyG有序拆分25NSSSriaSrikii...0,...,2,1,211NrNrN11211定理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做任意重复的有序拆分，方案数为不允许重复有序拆分：不允许重复无序拆分+全排列