（4）由题意知，M1=M2=M3=M4={6,7,8,…}，故该组合数序列的生成函

?1?n?3?n??n?3?24?n67842424

x. 数为(x+x+x+…)=x·= x·?x=???4(1?x)n?0?n?n?0?n????n?21?X的系数为??. 3??n

16. 设多重集合S?{??e1,??e2,??e3,?,??ek},an表示集合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,…}，故该组合数序列的生成

函数为(1?x222!4!?（2）由题意知，M1=M2=M3=…=Mk={4,5,6,…}，故该组合数序列的生成 函数为

23x4x5xxkk(??...)=(e(x)?1??) 4!5!2!3!kk??ii? e((k?i)x)[e(1)?e(2)?e(3)]?i?=(-1)

i?0?x4?...)k=??e(x)?e(?x)?k?.

???ki??in((?1)n[1?e(2)?e(3)])x/n! ???i?=

n?0i?0???k

?k?an??(?1)??(k?i)n[1?e(2)?e(3)]i

i?0?i?kn（3）由题意知，M1=M2=M3=…=Mk={0,1,2,…,i}，故该组合数序列的生

x2xik成函数为(1?x??...?).

2!i!（4）由题意知，M1=M2=M3=…=Mk={i,i+1,i+2,…}，故该组合数序列的

xixi?1生成函数为 (??...)k.

i!(i?1)!17. 用生成函数法证明下列等式：

?n?2??n?1??n??n?（1）???2????????

?r??r??r??r?2?证明：(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

?n??n?1??n??n?2??2???，对比左右两边xr的系数，左边=?，右边= ??????r??r?2??r??r??n?2??n?1??n??n?整理得：???2????????.

?r??r??r??r?2?等式得证.

28

（2）

?n?j?q??n?q?j?(?1)????????

rj?0?j????r?q?q证明：(1+x)n[(1+x)-1]q=xq(1+x)n，

对比左右两边xr的系数，

qq??n?q?j??n??q?q?jq?左边=(1?x)???(1?x)??(?1)???，右边=?， ??jj?0?j?j?0?r?q??r???qn

因此等式得证.

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+3x14+3x15+2x16+2x17+x18+x19 故共能称出20种重量，指数即为重量类型，系数为方案数. 19. 求方程x1+2x2+4x3=21的正整数解的个数. 解：由题目可以看出，x1为奇数，故生成函数为

??k?2?4k3524648127911

(x+x+x+…)(x+x+x+…)(x+x+x+…)=(x+2x+x)???x， 2k?0??展开式中x21的系数为20，亦即该方程正整数解的个数。

?n?3?n2320. H?1?4x?10x?20x????x?? ??3???n?2?nx （1）证明：(1?x)H????2?n?0?（2）求H的表达式. 解：H的生成函数为G????n?3??1=，所以 ??4??n??(1?x)?1?n?2?n(1?x)H??x. ???32?(1?x)n?0?21. 数1,2,3,… ,9的全排列中,求偶数在原来位置上,其余都不在原来位置上

的错排数目.

解：实际上是1，3，5，7，9这5个数的错排问题，总数为

5！-C(5,1)4!+C(5,2)3!-C(5,3)2!+C(5,4)1!-C(5,5)=44.

22. 求整数n拆分成1,2,…,m的和,并允许重复的拆分数.如若其中m至少出

现1次,试求它的方案数和生成函数.

解：因为n拆分成1，2，…，m的和允许重复，故其生成函数为

G(x)=(1+x+x2+…)(1+x2+x4+…)…(1+xm+x2m+…)

=

111··…· 2m1?x1?x1?x若要m至少出现1次，则生成函数为

G1(x)=(1+x+x2+…)(1+x2+x4+…)…(xm+x2m+…)

29

xm11

= ··…· 2m

1?x1?x1?x

即：整数n拆分成1到m的拆分数，减去n拆分成1到m－1的拆分数，即为拆分成1到m，至少出现一个m的拆分数。

23. n个完全相同的球放到m个有标志的盒子,不允许有空盒,问共有多少种

不同的方案？其中m≤n.

解：令n个球放到m个有标志的盒子的方案数为an，由于不允许有空盒，因

此序列{an}的生成函数为

xmG(x)=(x+x+…)(x+x+…)…(x+x+…)= . m(1?x)2

2

2

(1-x)-m=1+mx+

m(m?1)2!x2+…

故其中xn-m的系数为 m(m?1)...(m?n?m?1)(n?m)!(n?m)!(m?1)!(n?m)! 即an=C(n-1,m-1)

24. 求在8个字母A,B,C,D,E,F,G,H的全排列中,只有4个元素不在原来的位

置上的排列数.

解：8个字母中只有4个不在原来的位置上，其余4个字母保持不动，相当

于4个元素的错排，其数目为4!?1??m(m?1)...(n?1)?(n?1)!?C(n?1,m?1)??11!?12!3!?1?1???9. 4!?故8个字母的全排列中有4个不在原来位置上的排列数应为C(8,4)·9=630.

30