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

20、

证明：?(-1)n-kk?mnn????nkkm?1，若n?m. ???0，若n?mkn-nnn?n??m?=1。 证明：若n=m：?(-1)n-k?nk??m??(-1)k?m若n>m：我们知道，(1+x) =

n

???xnkk?0nk

k!???(k?m)!xnknn!n?m对该式两边求m阶导数：(1?x)?(n?m)!k?0k?m

xm?n?2k乘以：xm?n?2km!n??(1?x)nmn-knkkmn?m??????xnkkmk?0nk?m

令x = -1：0 = 21、

mk?m?(-1)????

mnm证明下列等式：

（1）?k?0?????2??

n?kn-mnk?kn证明：?nn-m??k??(n?k)!n!n!??(n?m)!(m?k)!k!(n?k)!k!(n?m)!(m?k)!????

mknm?knmn因此，??nn-m??k??2?m?

k?0m（2）?i?0m??????n?im?ir?iin?r?1m?

证明：利用路径问题解决。

左边第i项相当于从点c (-r-1,0)到点(-1,i)，再经点(0,i)，最后到达b (n-m,m)的所有路径数。而右边为从c到b的所有路径数。因此得证。

12n2n?12n?12n2n?22、 证明：n???n?1???n?1???n???n?1? n?1证明：

2n?1n?11n?12n)!1 ???(n?!n!n?12nn2n?1)!(2n?1)!(2n?1)!(n?1)!(n?2)!?(2n?1)!(n?1)!n!??????((n???1)!n!(n?1)!(n?2)!(n?2)!(n?1)!n!(n?1)!2n?1n?1?(2n)!(2n)!2??2nn!(n?1)!(n?1)n!n!(n?1) 5

2n)!(2n)!(2n)!(n?1)!(n?1)!?(2n)!n!n!(2n)!??????(n???

!n!(n?1)!(n?1)!n!n!(n?1)!(n?1)!n!n!(n?1)2nn2nn?1因此 23、

n1n?1??????????????

2nn2n?1n?12n?1n?12nn2nn?1试证明：

（1）?k2k?0???n(n?1)2nkn?2

n

证明：由二项式定理知：??nxk = (1+x) k?k?0nn-2

等式两边对x求2次导数得：?(k2?k)?nxk = n(n-1) (1+x) k?k?0nn-2 令x=1，则：?(k2?k)?nk? = n(n-1) 2

k?0n整理得：?k?0m?????2??

n?kn-mnkmnm（2）n???(k?1)???k??

nknk?1nk证明：n?nk??n?n!

k!(n?k)!nk(k?1)?n!n!???k???(k?1)(k?1)!(n?k?-k-1)!k!(n?k)!nk?1n!n!?k?(k?1)!(n?k?1)!(n?k)(k?1)!(n?k?1)!n?k?k?k(n?k)(k?1)!(n?k?1)!n!?n?k!(n?k)!

得证。 24、

1证明：?k?0(k?1)(k?2)nn??nk2n?2?n?3. ?(n?1)(n?2)n

证明：由二项式定理知：??nxk = (1+x) k?k?0等式两边对x积分得：?6

1k?0(k?1)n??xnkk?1?11?(1?x)n?1 n?1(n?1)

1再次积分：

k?0(k?1)(k?2)?n??xnkk?2(1?x)n?2x1 ???n?1(n?1)(n?2)(n?1)(n?2)令x＝1。整理，得证。 25、 展开(a+3b-7c-d)5.

解：??5。 an1(3b)n2(?7c)n3(?d)n4（n1+n2+n3+n4 = 5）n1?n2?n3?n4?k?0526、

(4x + 3y – 2z)20的展开式中，x5y7z8的系数是什么？x5y15的呢？

20!57?4?3?(?2)8 5!7!8!20!515 x5y15的系数：?4?3

5!15!解：x5y7z8的系数：

27、 解：

求(3+x+x2+2x3)6的展开式中x5的系数.

6!6!26!6!6!?2?12?34??1?1?33??1?13?32??2?12?33??3?15 1!1!4!2!1!3!1!3!2!1!2!3!1!5!28、 证明：整数n的m分拆数等于整数n-

??的m分拆数.

m

2

证明：设n=a1+ a2+?+am是n的一个m项分拆，并假定a1≥a2≥?≥am≥1，则

(a1-1)+( a2-1)+?+( am-1)=n-m

是n-m的一个项数不超过m的拆分。

反之，设a1+ a2+?+ar=n-m(r≤m)是n-m的一个分拆，则

(a1?1)?(a2?1)?????(ar?1)?1?1??????1 = ((n-m)+r)+(m-r)=n ?????????????????r项m?r项是n的一个m项拆分。于是这两种拆分一一对应，故其拆分数相等。 得证。

29、 设将N无序分拆成正整数之和且使得这些正整数都小于等于m的方法数

为B’(N,m). 证明：B’(N,m) = B’(N,m-1) + B’(N-m,m).

证明：B’(N,m)分为两类：一类是m不是其中一个，则为B’(N,m-1)；一类是m是其中一个，即B’(N-m,m)。故B’(N,m) = B’(N,m-1) + B’(N-m,m).

30、 证明：周长为2n，边长为整数的三角形的个数等于数n的3分拆数. 证明：设n的一个拆分n=x+y+z，则

2(x+y+z)=(x+y)+(x+z)+(y+z)＝2n

其中 (x+y)+(x+z)=2x+(y+z)>y+z

同理 (y+z)+(x+z)>(x+y)，(x+y)+(y+z)>(x+z)

因此(x+y)，(x+z)，(y+z)可以组成一个三角形，且周长为2n。

反之，设一个周长为2n的三角形，其三条边长a，b，c是整数，则

n=

a?b?c 2设x=n-a，y=n-b，z=n-c。显然x，y，z都是正整数，而

x+y+z=n-a+n-b+n-c=3n-(a+b+c)=n

即构成n的一个拆分。 得证.

7

31、 n个人出去野炊，其中r个人围一圈，另外n-r个人围一圈，问共有多少

种不同的方案？ 解：?nr??r!(n?r)! ?rn?r32、 把n个不同颜色的小球放入r个不同形状的盒子，恰好有1个空盒的放

法有多少种？恰好有m（m

33、 一凸十边形内任意三条对角线不共点（即不相交于同一点），问这些对角

线被它们的交点分成多少条线段？

10解：该10边形的对角线条数为：?102??10?35，交点数为?4??210。

设第i条对角线上交点数为ni，则线段有ni+1条；即总数为：

??ni?135i?1???ni?13535i?35

＝2*210＝420

每个交点由2条对角线相交而成，因而?i?1ni故总线段数为420+35＝455。

34、 一次小型聚会中，主人要把4块相同的蛋糕、6杯不同的饮料和5盘不

同的水果分给5个客人，其余各项可随便使用。问任一客人接到3份不同食物的概率是多少？

?5?1解：先把4块相同的蛋糕分给5个人：?4??70； 4再分6杯不同的饮料：56＝15625； 再分5盘不同的水果：55＝3125。

而一位客人接到3种物品的情况有：1*6*5＝30种。因此所求概率为：

630*3*45*44*100。

70*15625*3125??35、

(x1 + x2 +?+ xm)n的展开式有多少项？

n!nnnx11x22???xmm,其中ni≥0，且

n1!n2!???nm!解：(x1?x2?????xm)n??n1+n2+…+nm=n （*）

?n?1?。 则原题即相当于求方程（*）的非负整数解的个数。即为：?mn36、 10个人进行排名，其中甲必须在乙的前面，丙必须在丁的后面，问共有

多少种排名方案？

解：先排好甲、乙。则可把除丙、丁外的6人插入，方案数为36。

那么现在有9个位置可以插入丁；然后再把丙放在它后面的位置，方案数为：1+2+?+9＝45。

8

故总方案数为45*36。

37、 10套试验设备由15位学生使用，其中第一与第二、第三套使用人数相

同，与第四、第五套不同。问有多少种分配方案？ 提示：分情况考虑。

(1)第一、二、三套没有学生使用： 715-615?215

1?+5

；

(2)第一、二、三套各由一位学生使用： P(15,3)*712-P(15,4)*611

?2?10

1+P(15,5)*5

；

(3) 第一、二、三套各由两位学生使用：

?15??6??4?*79

-?15??864721510864562282??2??2?*6?1?+?10??2??2??2??2?*5；

(4) 第一、二、三套各由三位学生使用：

?15??9??6?*76

-?15??12??9??6?*63?21512960933123331?+?3??3??3??3?*5；

(5) 第一、二、三套各由四位学生使用：

?15??1483

124??4?*7；

(6) 第一、二、三套各由五位学生使用：；

?15??10??5555?。

综合以上六种情况和得分配方案数。

9