李凡长版组合数学课后习题答案习题4

24第四章生成函数1.求下列数列的生成函数：（1）{0,1,16,81,…,n4,…}解：G{k4}=235(11111)1xxxxx（）（2）343,,,333n解：3nGn=41(1)x（3）{1,0,2,0,3,0,4,0,……}解：A(x)=1+2x2+3x4+4x6+…=（211x）2.（4）{1,k,k2,k3,…}解：A(x)=1+kx+k2x2+k3x3+…=11kx.2.求下列和式：（1）14+24+…+n4解：由上面第一题可知，{n4}生成函数为A(x)=235(11111)1xxxxx（）=0kkkax，此处ak=k4.令bn=14+24+…+n4，则bn=0nkka，由性质3即得数列{bn}的生成函数为B(x)=0nnnbx=()1Axx=34125(1111)iiixxxxxi.比较等式两边xn的系数，便得14+24+…+n4=bn=1525354511111234nnnnnnnn321(1)(691)30nnnnn（2）1·2+2·3+…+n(n+1)解：{n(n+1)}的生成函数为A(x)=32(1)xx=0kkkax，此处ak=n(n+1).令bn=1·2+2·3+…+n(n+1)，则bn=0nkka.由性质3即得数列{bn}的生成函数为B(x)=0nnnbx=()1Axx=42(1)xx=032nkkkxxk.比较等式两边xn的系数，便得251·2+2·3+…+n(n+1)=bn=2(1)(2)213nnnnn.3.利用生成函数求解下列递推关系：（1）()7(1)12(2)(0)2,(1)7fnfnfnff;解：令A(x)=0()nnfnx则有A(x)-f(0)-f(1)x=2()nnfnx=2(7(1)12(2))nnfnfnx=2107()12()nnnnxfnxxfnx=7x(A(x)-f(0))-12x2A(x).将f(0)=2，f(1)=7代入上式并整理，得202711()(34)17121314nnnxAxxxxx.（2）()3(1)53(0)0nfnfnf;解：令A(x)=0()nnfnx，则有A(x)-f(0)=1(3(1)53)nnnfnx=003()153nnnnnxfnxxx=3xA(x)+15x·113x.A(x)=215(13)xx（3）()2(1)(2)(0)0,(1)1fnfnfnff;解：令A(x)=0()nnfnx，则有A(x)-f(0)-f(1)x=2(2(1)(2))nnfnfnx=2102()()nnnnxfnxxfnx=2x(A(x)-f(0))+x2A(x).将f(0)=0，f(1)=1代入上式并整理，得2()12xAxxx.4.设序列{na}的生成函数为：343(1)(1)xxxx,但00ba,110baa,……,1nnnbaa,……,求序列{nb}的生成函数.解：由00ba,110baa,……,1nnnbaa,得0nknkba，所以A(x)=()1Bxx.26由此得B(x)=(1-x)A(x)=3431xxx，亦即序列{nb}的生成函数。5.已知生成函数239156xxx,求对应的序列{na}.解：239156xxx=528171xx=11521817xx所以an=-5·8n-2·(-7)n.6.有红,黄,蓝,白球各两个,绿,紫,黑球各3个,从中取出10个球,试问有多少种不同的取法？解：Mr=My=Mb=Mw={0,1,2}，Mg=Mp=Mh={0,1,2,3}，所以该取法的个数为(1+x+x2)4(1+x+x2+x3)3中x10的系数，为678.7.口袋中有白球5个,红球3个,黑球2个,每次从中取5个,问有多少种取法？解：Mw={0,1,2,3,4,5}，Mr={0,1,2,3}，Mb={0,1,2}，所以从中取5个的取法个数为(1+x+x2)(1+x+x2+x3)(1+x+x2+x3+x4+x5)中x5的系数，为12。8.求1,3,5,7,9这5个数字组成的n位数个数,要求其中3和7出现的次数位偶数,其它数字出现的次数无限制.解：M1=M5=M9={0,1,2,3,…}，M3=M7={0,2,4,…}该排列的生成函数为24232(1...)(1...)2!4!2!xxxx=14(ex+e-x)2e3x=14(e5x+e3x+ex)=140(5231)!nnnnxn所以an=14(5231)nn.9.用3个1,2个2,5个3这十个数字能构成多少个偶的四位数？解：因要组成偶的四位数，所以个位必为2，然后确定其它三位的排列即可.M1={0,1,2,3}，M2={0,1}，M3={0,1,2,3,4,5}，故生成函数为2325(1)(1)(1)2!3!2!5!xxxxxxx.其中33!x的系数为20，即可以组成20个偶的四位数。10.求由A,B,C,D组成的允许重复的排列中AB至少出现一次的排列数目.解：可把AB看作一个整体，用E表示，则MA=MB=MC=MD={0,1,2,…}，ME={1,2,…}故有224(1)()2!2!xxxx=e(4x)(e(x)-1)=e(5x)-e(4x)=5n-4n.11.从{,,}nanbnc中取出n个字母,要求a的个数为3的倍数,b的个数是偶数,问有多少种取法?解：由题意可知，Ma={0,3,6,…}，Mb=Mc={0,1,2,…}，该取法的生成函数为(1+x3+x6+…)(1+x+x2+x3)2=311x·421()1xx12.把正整数8写成三个非负整数之和，要求n1≤3,n2≤3,n3≤6.问有多少种27不同的方案？解：由题意可知，M1=M2={0,1,2,3}，M3={0,1,2,3,…,6}，则生成函数为(1+x+x2+x3)2(1+x+x2+x3+…+x6)=421()1xx·711xx=(1-2x4-x7+x8+2x11-x15)·31(1)x符合题意的方案数为x8的系数，为82421221222=13.13.在一个程序设计课程里,每个学生的每个任务最多可以运行10次.教员发现某个任务共运行了38次.设有15名学生,每个学生对这一任务至少做一次.求观察到的总次数的组合数.解：M1=M2=…=M15={1,2,3,…,10}，生成函数为(x+x2+x3+…+x10)15=1015151()1xxx，其中x38的系数为371527151714114214。14.用1角、2角、3角的邮票可贴出多少种不同数值的邮资？解：生成函数为G(x)=(1+x+x2+…)(1+x2+x4+…)(1+x3+x6+…)=11x·211x·311x=1+x+2x2+3x3+4x4+…15.设多重集合1234{,,,}Seeee,na表示集合S满足下列条件的n组合数,分别求数列{na}生成函数.（1）每个ie出现奇数次（i＝1,2,3,4）；（2）每个ie出现4的倍数次i＝1,2,3,4）；（3）1e出现3或7次,3e出现2,6或8次；（4）每个ie至少出现6次（i＝1,2,3,4）；解：（1）由题意知，M1=M2=M3=M4={1,3,5,…}，故该组合数序列的生成函数为(x+x2+x3+…)4=x4·41(1)x=x4·03nnnnx=403nnnnx.Xn的系数为13n.（2）由题意知，M1=M2=M3=M4={0,4,8,…}，故该组合数序列的生成函数为(1+x4+x8+…)4=441(1)x.（3）由题意知，M1={3,7}，M2=M4={0,1,2,…}，M3={2,6,8}故该组合数序列的生成函数为(x3+x7)(x2+x6+x8)(1+x+x2+…)2=(x5+2x9+x11+x13+x15)·011nnnx.Xn的系数为5191111131151111112nnnnn＝6n-56.28（4）由题意知，M1=M2=M3=M4={6,7,8,…}，故该组合数序列的生成函数为(x6+x7+x8+…)4=x24·41(1)x=x24·03nnnnx=2403nnnnx.Xn的系数为213n.16.设多重集合123{,,,,}kSeeee,na表示集合S满足下列条件的n排列（1）S的每个元素出现偶数次；（2）S的每个元素至少出现4次；（3）S的每个元素至多出现i次（i=1,2,…,k）；（4）S的每个元素至少出现i次（i=1,2,…,k）；解：（1）由题意知，M1=M2=M3=…=Mk={0,2,4,…}，故该组合数序列的生成函数为24(1...)2!4!kxx=()()2kexex.（2）由题意知，M1=M2=M3=…=Mk={4,5,6,…}，故该组合数序列的生成函数为54(...)4!5!kxx=3212!3!(())kxxex=(-1)i0(())[(1)(2)(3)]kiikekixeeei=00((1)[1(2)(3)]())!kiininnkeeixkin0(1)[1(2)(3)]()kininieekakii（3）由题意知，M1=M2=M3=…=Mk={0,1,2,…,i}，故该组合数序列的生成函数为2(1...)2!!ikxxxi.（4）由题意知，M1=M2=M3=…=Mk={i,i+1,i+2,…}，故该组合数序列的生成函数为1(...)!(1)!iikxxii.17.用生成函数法证明下列等式：（1）2122nnnnrrrr证明：(1+x)n+2=(1+x)n·(1+x)2=(1+2x+x2)(1+x)n=x2(1+x)n+2(1+x)n+1-(1+x)n对比左右两边xr的系数，左边=2nr，右边=122nnnrrr，整理得：2122nnnnrrrr.等式得证.29（2）0(1)qjjqnqjnjrrq证明：(1+x)n[(1+x)-1]q=xq(1+x)n，对比左右两边xr的系数，左边=00(1)(1)(1)(1)qqnjqjjjjqqxxjjnqjr，右边=nrq，因此等式得证.18.设有砝码重为1g的3个,重为2g的4个,重为4g的2个,问能称出多少种重量？各有多少种方案？解：由题意知，M1={0,1,2,3}，M2={0,1,2,3,4}，M4={0,1,2}，故生成函数为(1+x+x2+x3)(1+x2+x4+x6+x8)(1+x4+x8)=1+x+2x2+2x3+3x4+3x5+4x6+4x7+5x8+5x9+5x10+5x11+4x12+4x13+3