組合數(shù)學(xué)第二章習(xí)題解答

1、第二章習(xí)題,2.3 已知序列{C(3,3),C(4,3),...,C(n+3,3),...},求母函數(shù)。,2.5 設(shè)Gn=F2n,證明：Gn-3Gn-1+Gn-2=0,n=2,3,4,...求Gn的母函數(shù),2.7 G=1+2x2+3x4+4x6+...+(n+1)x2n+...,解：令t=x2代入上式G=1+2t+3t2+4t3+...+(n+1)tn+... =1/(1-x)2 =1/(1-x2)2,證明（1-3x+3x2-

2、x3)G是一個(gè)多項(xiàng)式，并求母函數(shù)G,2.12已知,求序列{an}的母函數(shù),2.13已知,求序列{an}的母函數(shù),2.16 用數(shù)學(xué)歸納法證明C(m,m),C(m+1,m),C(m+2,m),...,C(m+n,m),...的母函數(shù)為(1-x)-m-1,當(dāng)m=1時(shí)成立，設(shè)m=k時(shí)成立。也就是：C(k,k),C(k+1,k),C(k+2,k),...,C(k+n,k),...的母函數(shù)為(1-x)-k-1,因此，m=k+1時(shí)成立,2.1

3、7 已知：,證明：,2.24 設(shè)an-2an-1+an-2=5,a0=1,a1=2,求解這個(gè)遞推關(guān)系。,可認(rèn)為是(1)n5,1是2重根，特解是kn2代入遞推關(guān)系：kn2-2k(n-1)2+k(n-2)2=5,k=5/2一般解是：k1+k2n+5n2/2,2.23 設(shè)an=(k1+k2n)(-3)n, k1,k2 是常數(shù)，求{an}的遞推關(guān)系。,特征方程為(x+3)2=x2+6x+9=0,遞推關(guān)系為an+6an-1+9an-2=0,2

4、.25 分母展開求出an的遞推關(guān)系，再求出bn的遞推關(guān)系,2.26 逐項(xiàng)展開，兩邊合并。,將分母展開(1-x)(1+x-x2)=1-2x2+x3,因此an滿足遞推關(guān)系：an-2an-2+an-3=0,a0=4,a1=-3,b0=4,b1=-7,母函數(shù)為：,an-an-1+an-1-an-2-an-2+an-3 = bn+bn-1-bn-2=0,2.27 求下列遞推關(guān)系的一般解,(a)an-4an-1=5n,2.27 求下列遞推關(guān)系的

5、一般解,(e)an-4an-1=2×5n-3×4n,2.28,2.30,2.31,2.32(a),2.32(b),2.32(c),2.33 F0,F1,F2是費(fèi)卜拉契序列，求解：an-an-1=Fn+2Fn-1,2.34 求解：an=an-1+C(n+2,3),a0=0,2.35 求解：an=an-1+C(n+3,4),a0=0,2.36 利用迭代法解,2.37 利用置換an=bn2,解：,2.38 利用

6、置換an=n!bn,解：,2.39 利用置換an=bn/n,解：,2.40 解下列遞推關(guān)系,2.41 設(shè)an滿足：an+b1an-1+b2an-2=5rn,2.42 設(shè)an滿足：an-an-1-an-2=0, bn滿足：bn-2bn-1-bn-2=0,cn=an+bn,證cn滿足一個(gè)四階線性常系數(shù)齊次遞推關(guān)系。,2.42 設(shè)an滿足：an-an-1-an-2=0, bn滿足：bn-2bn-1-bn-2=0,cn=anbn,

7、證cn滿足一個(gè)四階線性常系數(shù)齊次遞推關(guān)系。,2.43 設(shè)an,bn滿足：xn+b1xn-1+b2xn-2=0, 證anbn滿足一個(gè)四階線性常系數(shù)齊次遞推關(guān)系。a0,a2,a4滿足,2.44 設(shè)an,bn滿足：xn+b1xn-1+b2xn-2=0, 證anbn滿足一個(gè)四階線性常系數(shù)齊次遞推關(guān)系。a0,a2,a4滿足一個(gè)二階線性常系數(shù)遞推關(guān)系。,2.45 設(shè)F0,F1,F2是費(fèi)卜拉契數(shù)列，試找出常數(shù)a,b,c,d使F3n=aFnFn+

8、1Fn+2 +bFn+1Fn+2Fn+3+cFn+2Fn+3Fn+4+dFn+3Fn+4Fn+5,2.47證明等式,2.求 中 項(xiàng)的系數(shù).,2. 題目解：,分析 的結(jié)構(gòu)可知僅當(dāng)時(shí)有 項(xiàng),三個(gè)系數(shù)相加即為所求,2.48有紅、黃、藍(lán)、白球各兩個(gè)，綠、紫、黑球各3個(gè)，問從中取出10個(gè)球，試問有多少種不同的取法？,用指數(shù)型母函數(shù)

9、，可得母函數(shù),系數(shù)即為所求。,2.49.求由A,B,C,D組成的允許重復(fù)的排列中AB至少出現(xiàn)一次的排列數(shù)目。,解：先求不出現(xiàn)的，設(shè)an-1,an-2分別是取n-1和n-2不出現(xiàn)AB的 排列數(shù)。,50、對(duì)符合題設(shè)要求的排列如果0可以出現(xiàn)在最高位，則可得母函數(shù)：,但是對(duì)n位四進(jìn)制數(shù)來說最高位不能為0。最高位等零等于n-1位的4進(jìn)制數(shù)。,2.51.試求由A,B,C, 這三個(gè)字母組成的n位符號(hào)串中不出現(xiàn)aa圖像的符號(hào)串的數(shù)目。,解遞推關(guān)系即可：

10、,2.52.證明：C(n,n)+C(n+1,n)+...+C(n+m,n)=C(n+m+1,m)。,2.54.8臺(tái)計(jì)算機(jī)分給3個(gè)單位，第1個(gè)單位的分配量不超過3臺(tái)，第2個(gè)單位的分配量不超過4臺(tái)，第3個(gè)單位的分配量不超過5臺(tái)，問共有幾種分配方案？,用歸納法可證明：1）當(dāng)k=1時(shí)命題成立2）設(shè)當(dāng)k=N時(shí)命題成立 即N可唯一表示成不同的F數(shù)之和。則當(dāng)k=N+1時(shí)，明顯可以分成N的序列再加上1（F1），但這可能會(huì)不能滿足“不同

11、”的條件。下面予以討論1、如果原來不存在F1，則命題成立。2、如果存在 F1則寫成F2，如果存在F2 ,F1與F2合并成F3,如果原來不存在F3,成立，否則3、 F2則與F3合成F4，..............,2.55. 證明正整數(shù)n都可以唯一地表示成不同的且不相鄰的Fibonacci數(shù)之和。即,56.,57. 相鄰位不同為0的n位2進(jìn)制數(shù)中一共出現(xiàn)了多少個(gè)0？ 解：...   &

12、#160; 設(shè)符合條件的n位二進(jìn)制數(shù)的個(gè)數(shù)為hn 這些數(shù)中一共有an個(gè)0      當(dāng)n位二進(jìn)制數(shù)最高位為1時(shí),符合條件的n位二進(jìn)制數(shù)的個(gè)數(shù)為hn-1    最高位為0時(shí)，次高位必為1符合條件的n位二進(jìn)制數(shù)的個(gè)數(shù)為hn-2hn=hn-1+hn-2,h1=2,h2=3,h0=1即hn是F數(shù)列,,,,58. 在Hanoi塔問題中，在柱A上從上到下套著n個(gè)

13、圓盤，其編號(hào)依次從1到n?，F(xiàn)要將奇數(shù)編號(hào)與偶數(shù)編號(hào)的圓盤分別轉(zhuǎn)移到柱B和柱C上。轉(zhuǎn)移規(guī)則仍然是每次移動(dòng)一個(gè)，始終保持上面的比下面的小。一共要移動(dòng)多少次？,設(shè)n為偶數(shù)1）先把n-1個(gè)盤通過C移到B2）把第n個(gè)盤移到C3）把n-3個(gè)盤通過C移到A4）把第n-2個(gè)盤移到B對(duì)n為奇數(shù)時(shí)上述四步仍然成立，但是B、C對(duì)調(diào)。,其中,為Hanota數(shù)列。,59. 作圖可證。,60. 證明。用歸納法。,61. 求長(zhǎng)度為n的0,1符號(hào)

14、串，只在最后兩位才出現(xiàn)00的符號(hào)串總數(shù)。,最后兩位是00，倒數(shù)第三位必須是1，最后三位是100，因此：,62. 在一圓周上取n個(gè)點(diǎn)，過一對(duì)頂點(diǎn)可作一弦，不存在三弦共點(diǎn)的現(xiàn)象。求弦把圓分割成幾部分？,設(shè)n-1個(gè)點(diǎn)把圓分為an-1個(gè)部分加上第n個(gè)點(diǎn)則增加了n-1條弦增加的第1條弦，被其他弦分成1段（沒被分割）增加的第2條弦，被其他弦分成1x(n-2-1)+1段…………增加的第n-2條弦，被其他弦分成(n-3)x(n-2-n+3)+

15、1段增加的第n-1條弦，被其他弦分成1段,63. 求n位二進(jìn)制數(shù)中相鄰兩位不出現(xiàn)11的數(shù)的個(gè)數(shù),64. 從n個(gè)文字中取k個(gè)文字作允許重復(fù)的排列，但不允許一個(gè)文字連續(xù)出現(xiàn)3次，求這樣的排列的數(shù)目。,首先，假設(shè)am-1的最后一位為“5”，最后一位與5不同的取法有(n-1)種，少算了最后一位也取5的情況，就是最后兩位都是5的情況，也就是最后兩位與倒數(shù)第三位不同的情況，有(n-1)am-1種。,是n的4次方,滿足第推關(guān)系,設(shè),65. 求1

16、4+24+...+n4之和,66. 求矩陣,只要求出K即可,69. 用an記具有整數(shù)邊長(zhǎng)、周長(zhǎng)為n的三角形的個(gè)數(shù)。,a. 證明,I 當(dāng)n是偶數(shù)時(shí) 對(duì)所有符合條件的 ar-3 來說，每邊增加一個(gè)單位，則可構(gòu)成符合條件的ar。,設(shè)短邊為a、b，長(zhǎng)邊為c，則(a+b)-c>=2即a+b-2>c-1，對(duì)所有符合條件的ar來說，每邊減少1各單位，則可構(gòu)成符合條件的 ar-3,II 當(dāng)n為奇數(shù)時(shí) 由I的討論知，ar比a

17、r-3多了a+b-c=1的三角形。由a+b+c=n，c=n-a-b, 可知：,當(dāng)(n+1)/2能被2整除時(shí)，這種三角形有(n+1)/4 個(gè),當(dāng)(n+1)/2 不能被2整除時(shí)，這種三角形有(n-1)/4 個(gè),70. (a)證明邊長(zhǎng)為整數(shù)、最大邊長(zhǎng)為l的三角形的個(gè)數(shù)是：,解：...     （a）l=1時(shí)，只有一種可能（即3邊都是長(zhǎng)度為1）。      &#

18、160; l=2時(shí)，有兩種可能（即“1，2，2”、 “2，2，2”）。  設(shè)三角形的3邊邊長(zhǎng)為x、y、z， 且 。x≤y≤z=l,x+y>z    l=2k+1時(shí),x+y>l,x+y≤2l    x+y=2k+2時(shí)，有k+1種方案，即“1，2k+1”、“2，2k”、...…、“k+1，k+1”。    

19、 x+y=2k+3時(shí)，有k種方案，即“2，2k+1”、“3，2k”、...…、“k+1，k+2”。     x+y=2k+4時(shí)，有k種方案，即“3，2k+1”、“4，2k”、...…、“k+2，k+2”。     … …     … …     x+y=4k+1時(shí)，有1種

20、方案，即“2k，2k+1”。     x+y=4k+2時(shí)，有1種方案，即“2k+1，2k+1”。,,l=2k時(shí)     x+y=2k+1時(shí)，有k種方案，即“1，2k”、“2，2k-1”、...…、“k，k+1”。     x+y=2k+2時(shí)，有k種方案，即“2，2k”、“3，2k-1”、...…、“k+1，k+1

21、”。     x+y=2k+3時(shí)，有k-1種方案，即“3，2k”、“4，2k”、...…、“k+1，k+2”。     … …     … …     x+y=4k-1時(shí)，有1種方案，即“2k-1，2k”。     x+y=4k時(shí)

22、，有1種方案，即“2k，2k”。,,(b)設(shè)fn記邊長(zhǎng)不超過2n的三角形的個(gè)數(shù)，而gn記邊長(zhǎng)不超過2n+1的三角形的個(gè)數(shù)，求fn和gn的表達(dá)式。,,,,,74.,,75.設(shè)F1=F2=1,Fn=Fn-1+Fn-2(a)證明：Fk= FkFn-k+1+ Fk-1Fn-k,n>k>1(b)證明：Fn ︱ Fm的充要條件是n ︱ m(c)證明： FmFn= Fm+n-2+ Fm+n-6+ Fm+n-10+...,(d)證明(

23、Fm,Fn)=F(m,n),(m,n)為m,n的最大公約數(shù)。,1）證明    用數(shù)學(xué)歸納法     I k=2時(shí) 成立， Fn= F2Fn-1+ F1Fn-2,II 設(shè)k=m時(shí)成立Fn= FmFn-m+1+ Fm-1Fn-m,III 當(dāng)k=m+1時(shí),Fm+1Fn-m+ FmFn-m-1= Fn-m(Fm +Fm-1)+FmFn-m-1=Fm(Fn-m +Fn-

24、m-1)+Fn-mFm-1= Fn,2）證明     Fm與Fm-1互素(用歸納法可證),作了k次后 若n-km<m,則上式,,3）證明  當(dāng)n是偶數(shù)時(shí)，最后一次會(huì)出現(xiàn)F0=0項(xiàng)  當(dāng)n是奇數(shù)時(shí)，最后一次會(huì)出現(xiàn)F1=1項(xiàng),4）證明     用2）的結(jié)論    &#

25、160;    下面證明是最大公約數(shù) 設(shè)F(n,m)不是最大公約數(shù)， FN是,則 m|N, n|N 則 N=(n,m)矛盾 是最大公約數(shù):,76.在從1到n的自然數(shù)中選取k個(gè)不同且不相鄰的數(shù)，設(shè)此選取方案數(shù)為f(n,k).(a)求 f(n,k)的遞推關(guān)系(b)用歸納法求 f(n,k).(c)若設(shè)1與n是相鄰的數(shù)，并設(shè)在此假定下從1到n的自然數(shù)中選取k個(gè)不同且不相鄰的k個(gè)數(shù)的