組合數(shù)學(xué)第二章母函數(shù)與遞推關(guān)系習(xí)題解答

1、1. 題目解：,比較n次方系數(shù)即可證。,2. 題目解：,分析 的結(jié)構(gòu)可知僅當(dāng)時有 項,三個系數(shù)相加即為所求,3. 題目解：,用指數(shù)型母函數(shù)，可得母函數(shù),系數(shù)即為所求。,4. 題目解：,A、B、C、D組成的全排列數(shù)為,出現(xiàn)A后，其后續(xù)字母必為A、B、C、D中的一個，其概率相等。,AB至少出現(xiàn)一次的排列為,排列數(shù)為,5. 題目解：,對符合題設(shè)要求的排列如果0可以出現(xiàn)

2、在最高位，則可得母函數(shù)：,但是對n位四進(jìn)制數(shù)來說最高位不能為0。,6. 題目解：,參見第四題解答前半部分。,7. 題目解：,題設(shè)中序列的母函數(shù)為：,由$4性質(zhì)3得，上式,8. 題目解：,等式的右端相當(dāng)于從n+m+1個球中取n+1個球的組合。 把這n+m+1個球編號，如果取出的n+1個球中最小編號是一，則得到 如果最小編號是二則得到 如果最小編號是m則得到

3、 。 可證,9. 題目解：,由推導(dǎo)過程知,令,求導(dǎo)得,令,即,解得,將 代入 得,10. 題目解：,把單位看成元素，共12個元素其中 第1單位有3個第2單位有4個第3單位有5個則命題可看成從12個元素中取8個的組合。母函數(shù)為：,其中 項系數(shù)為所求,11. 題目解：,用歸納法可證明：1）當(dāng)k=1時命題成立2）設(shè)當(dāng)k=N時命題成立

4、 即N可唯一表示成不同且不相鄰的F數(shù)之和。則當(dāng)k=N+1時，明顯可以分成N的序列再加上1（ ），但這可能會不能滿足“不同且不相鄰”的條件。下面予以討論,先討論相鄰的 ，明顯若有 ，則可用 代替。以此類推可解決相鄰問題。 再討論相同 ，可把超過1個的分解為 再用結(jié)決相鄰問題的方法即可解決 命題得證,12. 題目解：

5、,設(shè)n個滿足條件的平面把空間分成 個域n-1個滿足條件的平面把空間分成 個域則第n個平面與這n-1個平面有n-1條交線，且這些兩兩相交，任三線不共點。 第n個平面被這n-1條線分成 個域 增加了 個域。可得,設(shè),解得,13. 題目解：,當(dāng)n位二進(jìn)制數(shù)最高位為1時,最高位為0時，次高位必為1,即 是F數(shù)列,14. 題目解

6、：,設(shè)n為偶數(shù)1）先把n-1個盤通過C移到B2）把第n個盤移到C3）把n-3個盤通過C移到A4）把第n-2個盤移到B對n為奇數(shù)時上述四步仍然成立，但是B、C對調(diào)。,其中,為Hanota數(shù)列。,15. 題目解：,這是一個錯排問題把某種排列狀態(tài)看成暫時狀態(tài)則,16. 題目解：,把AD看成1則AB為,同理可得其他矩形相似,滿足條件的n條直線把平面分成 個域，其中n-1條直線分割成的域數(shù)為 ，第n

7、條直線與這n條直線均相交。被分成n-1+1=n段。 增加的域數(shù)為n。,17. 題目解：,設(shè),解得,18. 題目解：,n-1個點把圓分為 部分，加上第n個點則增加了n-1條弦增加第1條弦，被其他弦分成0段增加第2條弦，被其他弦分成1x(n-2-1)段…………增加第n-2條弦，被其他弦分成(n-3)(n-2-n+3)段增加第n-1條弦，被其他弦分成0段,19. 題目解：,設(shè)n-1位不出

8、現(xiàn)11的個數(shù)為n-2位不出現(xiàn)11的個數(shù)為n位不出現(xiàn)11的個數(shù)為則,即特征方程為,設(shè)代入得,20. 題目解：,設(shè)所求為則,21. 題目解：,是n的4次方,滿足第推關(guān)系,設(shè),代入可解得,22. 題目解：,由矩陣的結(jié)構(gòu)知,只要求出K即可,24. 題目解：,當(dāng)r是奇數(shù)（>1）時,當(dāng)r是偶數(shù)時,25. 題目解：,I 當(dāng)n是偶數(shù)時 對所有符合條件的 來說，每邊增加1各單位，則

9、可構(gòu)成符合條件的 。,,設(shè)短邊為a、b，長邊為c，則(a+b)-c>=2即a+b-2>c-1，對所有符合條件的 來說，每邊減少1各單位，則可構(gòu)成符合條件的 。,II 當(dāng)n為奇數(shù)時 由I的討論知， 比 多了a+b-c=1的三角形。 而這種三角形可知,當(dāng) 能被2整除時，這種三角形有 個,當(dāng) 不能被2