发布时间 : 星期二 文章李凡长版 组合数学课后习题答案 习题1更新完毕开始阅读49bd574333687e21af45a9f2
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