第四章 生成函数
1. 求下列数列的生成函数： （1）{0,1,16,81,…,n4,…} 解：G{k}=
4
x(1?11x?11x2?x3)5（1?x）??3??4??n?3??（2）???,??,?,??? 333????????
??n?3??1解：G??= ??4??n??(1?x)（3）{1,0,2,0,3,0,4,0,……} 解：A(x)=1+2x2+3x4+4x6+…=（4）{1,k,k2,k3,…}
解：A(x)=1+kx+k2x2+k3x3+…=
1. 1?kx1
. 2
1?x
2. 求下列和式： （1）14+24+…+n4
解：由上面第一题可知，{n4}生成函数为
x(1?11x?11x2?x3)?kA(x)==， ax?k5（1?x）k?0此处ak=k.令bn=1+2+…+n，则bn=?ak，由性质3即得数列{bn}的生
4
4
4
4
k?0n?i?5?i成函数为 B(x)= ?bnx==(x?11x?11x?x)??x. ?1?xn?0i?1?i??nA(x)234?比较等式两边xn的系数，便得
?n?1?5??n?2?5??n?3?5??n?4?5?444
1+2+…+n=bn=? ?11??11????????n?1??n?2??n?3??n?4?30（2）1·2+2·3+…+n(n+1)
?1n(n?1)(6n3?9n2?n?1)
解：{ n(n+1)}的生成函数为A(x)=
2x(1?x)3n=?akxk，此处ak= n(n+1).
k?0?令bn=1·2+2·3+…+n(n+1)，则bn=?ak.由性质3即得数列{bn}的生成
k?0函数为B(x)=
1?x(1?x)4比较等式两边xn的系数，便得
n?0?bnx=
n?A(x)=
2x=2x???k?3?kx. ?k?k?0?n24
?n?2?n(n?1)(n?2)1·2+2·3+…+n(n+1)= bn=2?. ??3?n?1?3. 利用生成函数求解下列递推关系： ?f(n)?7f(n?1)?12f(n?2)（1）?;
?f(0)?2,f(1)?7解：令A(x)=?f(n)xn
n?0?则有A(x)-f(0)-f(1)x=
?f(n)x=?(7f(n?1)?12f(n?2))xnn?2?n?2??n
=7x?f(n)x?12xnn?12?f(n)xn?0?n
=7x(A(x)-f(0))-12xA(x).
将f(0)=2，f(1)=7代入上式并整理，得
?2?7x11nnA(x)????(3?4). ?21?7x?12x1?3x1?4xn?0?f(n)?3f(n?1)?5?3n（2）?;
?f(0)?0解：令A(x)=?f(n)xn，则有
n?0?2
A(x)-f(0)=
?(3f(n?1)?5?3)xnn?1?n=3x?f(n)x?15x?3nxn
nn?0n?0??=3xA(x)+15x·
11?3x.
A(x)= （3）?15x2(1?3x)?f(n)?2f(n?1)?f(n?2)
?f(0)?0,f(1)?1?n?0;
解：令A(x)=?f(n)xn，则有
A(x)-f(0)-f(1)x=?(2f(n?1)?f(n?2))x=2x?f(n)x?xnnn?2??2=2x(A(x)-f(0))+xA(x).
将f(0)=0，f(1)=1代入上式并整理，得A(x)?4. 设序列{an}的生成函数为：
2
n?1?f(n)xn?0?n
x1?2x?x2.
4?3x,但b0?a0,b1?a1?a0, 3(1?x)(1?x?x)……,bn?an?an?1,……,求序列{bn}的生成函数.
n解：由b0?a0,b1?a1?a0,……,bn?an?an?1,得?bk?an，所以A(x)=
k?0B(x)1?x.
25
4?3x，亦即序列{bn}的生成函数。 31?x?x3?9x5. 已知生成函数,求对应的序列{an}. 21?x?56x由此得B(x)=(1-x)A(x)= 解：
3?9x21?8x1?7x1?x?56x8x?17x?1nn
所以an=-5·8-2·(-7).
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,…}
该排列的生成函数为
x2x4x2112(1???...)(1?x??...)3=(ex+e-x)2e3x=(e5x+e3x+ex)
442!4!2!1?nxnn=?(5?2?3?1) 4n?0n!=
5?2=?5?1?2?1
所以an=
14(5n?2?3n?1).
9. 用3个1,2个2,5个3这十个数字能构成多少个偶的四位数？
解：因要组成偶的四位数，所以个位必为2，然后确定其它三位的排列即可.
M1={0,1,2,3}，M2 ={0,1}，M3={0,1,2,3,4,5}，故生成函数为
x2x3x2x5(1?x)(1?x??)(1?x????).
2!3!2!5!x3其中的系数为20，即可以组成20个偶的四位数。
3!10. 求由A,B,C,D组成的允许重复的排列中AB至少出现一次的排列数目. 解：可把AB看作一个整体，用E表示，则
MA=MB=MC=MD={0,1,2,…}，ME={1,2,…}
x2x24故有(1?x???)(x???)=e(4x)(e(x)-1)=e(5x)-e(4x)=5n-4n.
2!2!11. 从{n?a,n?b,n?c}中取出n个字母,要求a的个数为3的倍数,b的个数是
偶数,问有多少种取法?
解：由题意可知，Ma={0,3,6,…}，Mb=Mc={0,1,2,…}，该取法的生成函数为
1?x42136232
(1+x+x+…)(1+x+x+x)=·() 31?x1?x12. 把正整数8写成三个非负整数之和，要求n1≤3,n2≤3,n3≤6.问有多少种
26
不同的方案？
解：由题意可知，M1=M2 ={0,1,2,3}，M3={0,1,2,3,…,6}，则生成函数为 (1+x+x2+x3)2(1+x+x2+x3+…+x6)
1?x421?x71= (=(1-2x4-x7+x8+2x11-x15) · )·31?x1?x(1?x)
?8?2??4?2??1?2? 符合题意的方案数为x的系数，为???2?2???2??1=13. 2??????13. 在一个程序设计课程里,每个学生的每个任务最多可以运行10次.教员发
现某个任务共运行了38次.设有15名学生,每个学生对这一任务至少做一次.求观察到的总次数的组合数.
解：M1=M2 =…=M15={1,2,3,…,10}，生成函数为
8
1?x1015(x+x+x+…+x)=x()，
1?x?37??15??27??15??17?其中x38的系数为????????????。
?14??1??14??2??14?2
3
1015
1514. 用1角、2角、3角的邮票可贴出多少种不同数值的邮资？ 解：生成函数为G(x)=(1+x+x2+…)(1+x2+x4+…)(1+x3+x6+…)
=
111·· =1+x+2x2+3x3+4x4+… 231?x1?x1?x15. 设多重集合S?{??e1,??e2,??e3,??e4},an表示集合S满足下列条件的
n组合数,分别求数列{an}生成函数. （1）每个ei出现奇数次（i＝1,2,3,4）； （2）每个ei出现4的倍数次i＝1,2,3,4）； （3）e1出现3或7次,e3出现2,6或8次； （4）每个ei至少出现6次（i＝1,2,3,4）； 解：（1）由题意知，M1=M2=M3=M4={1,3,5,…}，故该组合数序列的生成函
??n?3?n??n?3?4?n123444
x. 数为(x+x+x+…)=x·= x·?x=??4?(1?x)n?0?n?n?0?n???Xn的系数为?
?n?1?
. ??3?
（2）由题意知，M1=M2=M3=M4={0,4,8,…}，故该组合数序列的生成函
1数为(1+x4+x8+…)4= . 44(1?x)（3）由题意知，M1={3,7}，M2= M4={0,1,2,…}，M3={2,6,8} 故该组合数序列的生成函数为
??n?1?n372682259111315
x. (x+x)(x+x+x)(1+x+x+…)=(x+2x+x+x+x) ·??n?0?1??Xn的系数为
?n?5?1??n?9?1??n?11?1??n?13?1??n?15?1???1??2???1?????1?????1?????1?＝6n-56. ?27