清華版組合數(shù)學(xué)第二版第二章習(xí)題答案

1、組合數(shù)學(xué)第二章答案 2. 1. 1008100448解：n2nn解：)?(x?xx)?1x? (1?)x(1?1?x? (1?x)?(1002n2n2n?k?k100k481C?(x)? ?xn2xx? ? ? ?1002n01?0?k54,k?3,k48)?(xx的結(jié)構(gòu)可知僅當(dāng)分析nnn?20x2n項(xiàng)時(shí)有 x? ? ? ?x?n0123C系數(shù)?C?k?3時(shí)， ?310034C?C?4k?時(shí)， 系數(shù)nnnn?4100?, ? ? ,?05C?C?k?5時(shí)， 系數(shù)110nn-?5100三個(gè)系數(shù)相加即為所求?次方系數(shù)即可證。比較n4. 3. 解：解：組成的全排列數(shù)為D、BC、A、2xx用指數(shù)型母函

2、數(shù)，可得母函數(shù)4)?P(1!2!132423)G(xx?xx?)?(1?1?x)(? 1 系數(shù)即為所求出后，其后續(xù)字母必中的一個(gè)，其概率相等1 5. 至少出現(xiàn)一次的排列A解可以出對(duì)符合題設(shè)要求的排列如1在最高位，則可得母函數(shù)1 ) 排列數(shù) 1 6. 解位四進(jìn)制數(shù)來說最高位不能但是參見第四題解答前半部分)4 4 組合數(shù)學(xué)第二章答案 8. 7. 解：解：題設(shè)中序列的母函數(shù)為：個(gè)球中取等式的右端相當(dāng)于從n+m+1?1,n)x?(x)?C(n,n)?C(nG個(gè)球的組合。n+1k?)x?n ?C(n?k,n+1n+m+1個(gè)球編號(hào)，如果取出的把這)n?m,C(n個(gè)球中最小編號(hào)是一，則得到?kxn ?,)C

3、(n?k)n?1,C(n?m如果最小編號(hào)是二則得到?0k?)?(k?1?(k?n)(kn?1)?),nC(n。m則得到如果最小編號(hào)是?kx? 可證!n0k?1?得，上式性質(zhì)3由$41?n)x(1? 19. ln?n(x)?lnp ?ln(Gn由推導(dǎo)過程知解：x2?1x11xln? lnp?n?)?)x?(1ln(G(n22xx61?3?1x l) ln代求導(dǎo)解 )10. 項(xiàng)系數(shù)為所其解個(gè)元把單位看成元素，1其單位單位單位個(gè)則命題可看成個(gè)元素中1組合。母函數(shù)為 5 組合數(shù)學(xué)第二章答案 11. FFF，則先討論相鄰的，明顯若有i1ii?解：F代替。以此類推可解決相鄰問可用2i?題。用歸納法可證明：

4、FF個(gè)的1再討論相同，可把超過i時(shí)命題成立1）當(dāng)k=1iFF再用結(jié)決相鄰問題的方法分解為1?i時(shí)命題成立）設(shè)當(dāng)k=N22i?即可解決F可唯一表示成不同且不相鄰的N即命題得證數(shù)之和。的序列則當(dāng)k=N+1時(shí)，明顯可以分成NF），但這可能會(huì)不能滿足（再加上12“不同且不相鄰”的條件。下面予以討論 nn?A?An?A?Aa?設(shè)12. 3n12032?解：1A?解得?a0個(gè)域個(gè)滿足條件的平面把空間分成設(shè)nn?a1A?個(gè)域n-1個(gè)滿足條件的平面把空間分成?1?n1?條交線，n-1個(gè)平面有則第n個(gè)平面與這n-11A?2且這些兩兩相交，任三線不共點(diǎn)。?21A?C?1個(gè)第n個(gè)平面被這n-1條線分成?n3域nn?

5、2C1?個(gè)域。可得增加了?n?1a?nn32?21a?,1?C a2, aa?0n11nn? 數(shù)n13. ?解n25?h位二進(jìn)制數(shù)的個(gè)數(shù)為n設(shè)符合條件的na0個(gè)這些數(shù)中一共有 ?a?ah,?a?n2n?1nn?n2?符合條件1,時(shí)當(dāng)n位二進(jìn)制數(shù)最高位為01,a?aa?2,?5,a? h位二進(jìn)制數(shù)的個(gè)數(shù)為n的02311?nh?a?aann2?1nn?符合條件時(shí)，次高位必為10最高位為220x(?x?1)h位二進(jìn)制數(shù)的個(gè)數(shù)為n的特征方程為：2?nnn?()?Cn?aAn?B)D?(, h?h?hh3?,?h2h,1設(shè)01?nn?n221n?為重根。、解得 a代入分析上式結(jié)構(gòu)可得：n?nn?)?(A

6、nB?()?CnDnn?)?D?(?(a?nB)n55n1?n1?n?CB?)?(?An1?(?1?)Dn可得方程組2n?2?n?2n(CB)2?(An?)D0BD?nn?5)/(?1(?B)?(?D)?55n?n1?n2?02?A?A?/5?解得2n?nn21?0/C2?C ?5?B?55代入可解得：把n=2?2?A ?C,?D?55?55 6 組合數(shù)學(xué)第二章答案 14. 解：22?nn?)?)(n?a?(?n?為偶數(shù)設(shè)n55n5555BC移到）先把n-1個(gè)盤通過121Cn個(gè)盤移到2）把第n?(?)?n ?AC移到）把n-3個(gè)盤通過355Bn-2個(gè)盤移到4）把第、為奇數(shù)時(shí)上述四步仍然成立，但

7、是B對(duì)n對(duì)調(diào)。C)3(n?3)?1?k(n?1)?1?h(n?k?(n)?h5)?,k(32?1,k()?2(k1)其中)(kh數(shù)列。為Hanota 15. 3n?1?n2?32?)?n?k()?k(n解：3?nn?12?4?2k(n1)?k(n?)?2層在m-k層中有k層不在原來的層上，設(shè)m可得特征方程：原有層上，但是每冊(cè)都不在原來的位置。30x?1)2(x?)解cosi代入初值可解16. ABCC解看A同理可得其他矩形相AAAAA AAA17. 解個(gè)域滿足條件條直線把平面分其，n-條直線分割成的域數(shù)解條直線均相交條直線與段n-1+1=被分增加的域數(shù) 7 組合數(shù)學(xué)第二章答案 19. 18.

8、解：解：a個(gè)點(diǎn)n-1個(gè)點(diǎn)把圓分為n部分，加上第na的個(gè)數(shù)為位不出現(xiàn)11設(shè)n-11?n條弦n-1則增加了a的個(gè)數(shù)為位不出現(xiàn)11n-22?n段條弦，被其他弦分成0增加第1a的個(gè)數(shù)為位不出現(xiàn)11nn段1x(n-2-1)增加第2條弦，被其他弦分成a?aa則2?n?n1n3a?a?2,?0, a?1,a?a?a(n-3)(n-2-增加第n-2條弦，被其他弦分成即210nn?1n?2段n+3)201?xx?段n-1增加第條弦，被其他弦分成0特征方程為1n?51?51?n?a?a? ?xx,1nn?321?22 20. nnBx?Ax設(shè)21解：a代入得設(shè)所求為n535?A?1111代入可解21. 解1次滿足

9、第推關(guān) 521162261524. 22. 解解由矩陣的結(jié)構(gòu)）是奇數(shù)是偶數(shù)即只要求) 8 組合數(shù)學(xué)第二章答案 為奇數(shù)時(shí)nII 當(dāng)25. aaa+b-c=1比由I的討論知，多了解：r3?r是偶數(shù)時(shí)當(dāng)nI 的三角形。而這種三角形可知a1來說，每邊增加對(duì)所有符合條件的3r?a。各單位，則可構(gòu)成符合條件的1?nr?a?ba?a23rr?1nn?1?(a+b)-c=2，則b，長邊為c設(shè)短邊為a、整除時(shí)，這種三角形有2當(dāng)能被22a來即a+b-2c-1，對(duì)所有符合條件的個(gè)r1n?各單位，則可構(gòu)成符合條說，每邊減少1整除時(shí)，這種三角形有不能被當(dāng)2a。件的23r?1?naa?3rr?個(gè)a?a?23?rr 27.

10、 1n?）證明1n1)?(2?aa?3n?n41?nk?n?kn?1NN?(2） 同理可28. ）證）證用數(shù)學(xué)歸納I k=次作成立，時(shí)成II k= k時(shí)k=m+kk則上用歸納假知題設(shè)成立I 9 組合數(shù)學(xué)第二章答案 F?F?F?上式?F）證明30mn?m?6nn?m?2?FF?FF?FF?F?F?1n?m?nmn?m11?2m?m?6?nn?m?2?n)?FF?F(F2nm?m?1n?m?32?n?1F?項(xiàng)n是奇數(shù)時(shí)，最后一次會(huì)出現(xiàn)當(dāng)1FF?FFF?上式?FF2?2nm?n?m21m?1nn?m?2?n?m?6FF?FFF?F?F?4n?n?m246n?m?m16?n?m?2mnn?m?F?F6?2mnmn?0F?項(xiàng)當(dāng)n是偶數(shù)時(shí)，最后一次會(huì)出現(xiàn)0 30. ）證明4證明）的結(jié)論用2個(gè)，這樣，號(hào)球同盒的球有n-k設(shè)與第n+1)mn nm|(,m),n|(,個(gè)盒子，個(gè)球就放入另外m-1其他k。,nk=m-1,m,的公約數(shù)是?FF個(gè)相個(gè)放m-即個(gè)不同的球中下面證明是最大公約的盒子的方案不是最大公約數(shù) 矛是最大公約31. 解 特征方程解32. 解代入，相鄰不同設(shè)所求的串的個(gè)數(shù)串的個(gè)