loading组合数学第二章答案
1. 解：? (1?x)2n?(1?x)n?(1?x)n? ??2n?0??? ??2n??2n??1??x??? ??2n??x2n? ?[ ??n?0??? ??n??n??1??x??? ??n??xn]2?? ??n??0??? ??n??n??n??n??, ??1??? ??n-1??,??比较n次方系数即可证。3. 解：用指数型母函数，可得母函数G(x)?(1?x?x2)4?(1?x?x2?x3)3? x10系数即为所求。?AB至少出现一次的排列为15P???P?P? ?e4x?e4x4n?(15n ???4)xnn?0n!?排列数为an?(15n?44)n?a1n?4(4n?2?2n?1)但是对n位四进制数来说最高位不能为0。?a?n?an?an?1?1[(4n?2?2n?1)?(4n?1?2?2n?14?1)]?1(3?4n?1?2n4)2. 解：? (1?x4?x8)100?[1?(x4?x8)]100 ?100?Ck100?(x4?x8)k?1100?kk?0分析(x4?x8)k的结构可知仅当k?3,4,5时有x20项k?3时， 系数?C32100?C3k?4时， 系数?C43100?C4k?5时， 系数?C5100?C05三个系数相加即为所求4. 解：A、B、C、D组成的全排列数为(1?x?x2P?2!??)41! ?e4x出现A后，其后续字母必为A、B、C、D中的一个，其概率相等。3?P??(1?x3(x)21!??)3?[1?4x?42!??]315 ?e3x?e4x?e4x5. 解：对符合题设要求的排列如果0可以出现在最高位，则可得母函数：G(x)?(1?x?x2x2x42!??)2?(1?2!?4!??)2 ?e2x?[1(ex?e?x)]22 ?1(e4x4?2e2x?1)1?xn ?4?(4n?2?2n?1)n?0n!6. 解：参见第四题解答前半部分。4
组合数学第二章答案
7. 解：题设中序列的母函数为：G(x)?C(n,n)?C(n?1,n)x?? ?C(n?k,n)xk?? ???C(n?k,n)xk8. 解：等式的右端相当于从n+m+1个球中取n+1个球的组合。把这n+m+1个球编号，如果取出的n+1个球中最小编号是一，则得到C(n?m,n)如果最小编号是二则得到C(n?m?1,n)k?0 ???(k?n)(k?n?1)?(k?1)kk?0n!x由$4性质3得，上式?1(1?x)n?19. 解：由推导过程知ln(G(x))?x1?x(1?1122?32??)? 1?11?222?32???6? ln(G(x))?x?21?x?6求导得y??1(1?x)2??2n6?x2令y??0即1?2n(1?x)2?6?x2?0解得x6n1???6n?(0,1), x6n2?6n???110. 解：把单位看成元素，共12个元素其中第1单位有3个第2单位有4个第3单位有5个则命题可看成从12个元素中取8个的组合。母函数为：G(x)?(1?x?x2?x3)?(1?x?x2?x3?x4) ?(1?x?x2?x3?x4?x5)????如果最小编号是m则得到C(n,n)。可证? ln(G(x))?lnp1n?nlnx?x?2? lnp1n1?x?6?nlnx ?x?21?x?6?nx?n令y?x1?x??26?nln1x将x1代入y得y?23n?2?p3n?n?e其中x8项系数为所求5
组合数学第二章答案
11. 解：用归纳法可证明：1）当k=1时命题成立2）设当k=N时命题成立即N可唯一表示成不同且不相邻的F数之和。则当k=N+1时，明显可以分成N的序列再加上1（F2），但这可能会不能满足“不同且不相邻”的条件。下面予以讨论12. 解：设n个满足条件的平面把空间分成an个域n-1个满足条件的平面把空间分成an?1个域则第n个平面与这n-1个平面有n-1条交线，且这些两两相交，任三线不共点。第n个平面被这n-1条线分成1?C2n个域增加了1?C2n个域。可得aa2n?n?1?1?Cn, a1?2, a0?113. 解：设符合条件的n位二进制数的个数为h这些数中一共有an当n位二进制数最高位为n个01时,符合条件的n位二进制数的个数为hn?1最高位为0时，次高位必为1符合条件的n位二进制数的个数为hn?2?hn?hn?1?hn?2, h1?2,h2?3,h0?1,分析上式结构可得：(An?B)?n?(Cn?D)?n?[A(n?1)?B]?n?1?[C(n?1)?D]?n?1?[A(n?2)?B]?n?2?[C(n?2)?D]?n?2?(?n??n)/5?A?n?1?2A?n?2??n?1/5?0 C?n?2C?n?2??n/5?0把n=2代入可解得：A??5, C??5先讨论相邻的F可用Fi，明显若有FiFi?1，则i?2代替。以此类推可解决相邻问题。再讨论相同F分解为FFi，可把超过1个的ii?1Fi?2再用结决相邻问题的方法即可解决命题得证设a?n??n?n?A0?A1n?A2??2???A3??3??解得?A?0?1??A1?1?A2?1??A3?1a?n???n??n?n?1?2?????3??即hn是F数列h?11?5n?2?n???5(2)???an?an?1?an?2?hn?2, a2?2,a3?5,a1?1,a0?0?an?2?an?1?an?hn特征方程为：(x2?x?1)2?0设aAn?B)?n?(Cn?D)?nn?(解得?、?为重根。代入anan?(??n?B)?n?(?5?n?D)?n5可得方程组?B?D?0??(?5?B)??(?5?D)??1解得?B?2??55??D??2556
组合数学第二章答案
22?an?(??n?)?n?(??n?)?n55555512 ??(??n?)??n5514. 解：设n为偶数1）先把n-1个盘通过C移到B2）把第n个盘移到C3）把n-3个盘通过C移到A4）把第n-2个盘移到B对n为奇数时上述四步仍然成立，但是B、C对调。?k(n)?h(n?1)?1?h(n?3)?1?k(n?3)?k(n)?k(n?3)?2n?1?2n?32[k(n?1)?k(n?4)]?2n?1?2n?3可得特征方程：(x?2)(x3?1)?0解得x1?1,x?i22?2,x3,4?e3?设k(n)?A2n?B?Ccosn?223??Dsinn3?代入初值可解得k(n)?52n27?316. 解：把AD看成1则AB为1?52B1B?AB?AB1?AB?AD\\ ?5?12ADB?1?1?5?AB1B5?12AD217. 解：满足条件的n条直线把平面分成其中n-1条直线分割成的域数为aan个域，n?1，第n条直线与这n条直线均相交。被分成n-1+1=n段。增加的域数为n。an?an?1?n, a0?1,a1?2其中k(1)?1,k(2)?2,k(3)?5h(k)为Hanota数列。15. 解：设m层中有k层不在原来的层上，m-k层在原有层上，但是每册都不在原来的位置。?N??m??m?k??Dk?(n!)k?Dm?knk?2??B1C1CB?ABCD同理可得其他矩形相似设an?A?n?0?A1n?A2??2???A0?1解得??A1?1??A2?1?a1?n???n?n??2??7