资源描述：
《李凡长版 组合数学课后习题答案习题4》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第四章生成函数1.求下列数列的生成函数：（1）{0,1,16,81,…,n4,…}解：G{k4}=（2）解：=（3）{1,0,2,0,3,0,4,0,……}解：A(x)=1+2x2+3x4+4x6+…=（）2.（4）{1,k,k2,k3,…}解：A(x)=1+kx+k2x2+k3x3+…=.2.求下列和式：（1）14+24+…+n4解：由上面第一题可知，{n4}生成函数为A(x)==，此处ak=k4.令bn=14+24+…+n4，则bn=，由性质3即得数列{bn}的生成函数为B(x)===.比较等式两边xn的
2、系数，便得14+24+…+n4=bn=（2）1·2+2·3+…+n(n+1)解：{n(n+1)}的生成函数为A(x)==，此处ak=n(n+1).令bn=1·2+2·3+…+n(n+1)，则bn=.由性质3即得数列{bn}的生成函数为B(x)====.比较等式两边xn的系数，便得301·2+2·3+…+n(n+1)=bn=.1.利用生成函数求解下列递推关系：（1）;解：令A(x)=则有A(x)-f(0)-f(1)x====7x(A(x)-f(0))-12x2A(x).将f(0)=2，f(1)=7代入上式并整理
3、，得.（2）;解：令A(x)=，则有A(x)-f(0)===3xA(x)+15x·.A(x)=（3）;解：令A(x)=，则有A(x)-f(0)-f(1)x===2x(A(x)-f(0))+x2A(x).将f(0)=0，f(1)=1代入上式并整理，得.2.设序列{}的生成函数为：,但,,……,,……,求序列{}的生成函数.解：由,,……,,得，所以A(x)=30.由此得B(x)=(1-x)A(x)=，亦即序列{}的生成函数。1.已知生成函数,求对应的序列{}.解：==所以an=-5·8n-2·(-7)n.2.有
4、红,黄,蓝,白球各两个,绿,紫,黑球各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.3.口袋中有白球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)中
5、x5的系数，为12。4.求1,3,5,7,9这5个数字组成的n位数个数,要求其中3和7出现的次数位偶数,其它数字出现的次数无限制.解：M1=M5=M9={0,1,2,3,…}，M3=M7={0,2,4,…}该排列的生成函数为=(ex+e-x)2e3x=(e5x+e3x+ex)=所以an=.5.用3个1,2个2,5个3这十个数字能构成多少个偶的四位数？解：因要组成偶的四位数，所以个位必为2，然后确定其它三位的排列即可.M1={0,1,2,3}，M2={0,1}，M3={0,1,2,3,4,5}，故生成函数为.其
6、中的系数为20，即可以组成20个偶的四位数。6.求由A,B,C,D组成的允许重复的排列中AB至少出现一次的排列数目.解：可把AB看作一个整体，用E表示，则MA=MB=MC=MD={0,1,2,…}，ME={1,2,…}故有=e(4x)(e(x)-1)=e(5x)-e(4x)=5n-4n.7.从中取出n个字母,要求a的个数为3的倍数,b的个数是偶数,问有多少种取法?解：由题意可知，Ma={0,3,6,…}，Mb=Mc={0,1,2,…}，该取法的生成函数为(1+x3+x6+…)(1+x+x2+x3)2=·301
7、.把正整数8写成三个非负整数之和，要求n1≤3,n2≤3,n3≤6.问有多少种不同的方案？解：由题意可知，M1=M2={0,1,2,3}，M3={0,1,2,3,…,6}，则生成函数为(1+x+x2+x3)2(1+x+x2+x3+…+x6)=·=(1-2x4-x7+x8+2x11-x15)·符合题意的方案数为x8的系数，为=13.2.在一个程序设计课程里,每个学生的每个任务最多可以运行10次.教员发现某个任务共运行了38次.设有15名学生,每个学生对这一任务至少做一次.求观察到的总次数的组合数.解：M1=M2
8、=…=M15={1,2,3,…,10}，生成函数为(x+x2+x3+…+x10)15=，其中x38的系数为。3.用1角、2角、3角的邮票可贴出多少种不同数值的邮资？解：生成函数为G(x)=(1+x+x2+…)(1+x2+x4+…)(1+x3+x6+…)=··=1+x+2x2+3x3+4x4+…4.设多重集合,表示集合满足下列条件的n组合数,分别求数列{}生成函数.（1）每个出现奇数次（i＝1,2,3
