李凡长版 组合数学课后习题答案习题4 下载本文

(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??q?q?jj?左边=(1?x)?(?1)??(1?x)??(?1)???rj?0j?0?j??j???n?=?, ??r?q?qnjj??,右边?

因此等式得证.

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为奇数,故生成函数为

(x?x3?x5?...)(x2?x4?x6?...)(x4?x8?x12?...)?x7(1?x2?x4?...)(1?x2?x4?...)(1?x4?x8?...)?x7711?(1?x2)21?x41(1?x2)2(1?x2)2?x?(1?x2)2(1?x4)3(1?x2)217911?x?(x?2x?x)(1?x4)3(1?x4)37

?k?2?4k?(x?2x?x)???xk?0?2?展开式中x21的系数为20,亦即该方程正整数解的个数。

?n?3?n23x?? 20. H?1?4x?10x?20x??????3?7911?(1)证明:(1?x)H???(2)求H的表达式.

?n?2?nx ?2?n?0????n?3??1解:H的生成函数为G??=??(1?x)4,所以 n?????1?n?2?n(1?x)H??x. ???32?(1?x)n?0?21. 数1,2,3,… ,9的全排列中,求偶数在原来位置上,其余都不在原来位置上

的错排数目.

29

解:实际上是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+…)

xm11= ··…· m21?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+

n-m

m(m?1)2!x2+…

故其中x的系数为 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个字母保持不动,相当

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

30