李凡長(zhǎng)版組合數(shù)學(xué)課后習(xí)題測(cè)驗(yàn)答案習(xí)題測(cè)驗(yàn)3

1、第三章遞推關(guān)系1 .在平面上畫(huà)n條無(wú)限直線，每對(duì)直線都在不同的點(diǎn)相交，它們構(gòu)成的無(wú)限 區(qū)域數(shù)記為f(n),求f(n)滿足的遞推關(guān)系.解:/(n)=f(n-1)+21f(1)=2,f(2)=4解得 f(n)=2n.2 . n位三進(jìn)制數(shù)中，沒(méi)有1出現(xiàn)在任何2的右邊的序列的數(shù)目記為f(n),求 f(n)滿足的遞推關(guān)系.解：設(shè)an-ian-2ai是滿足條件的n-1位三進(jìn)制數(shù)序列，則它的個(gè)數(shù)可以用f(n-1) 表示。an可以有兩種情況：1)不管上述序列中是否有2,因?yàn)閍n的位置在最左邊，因此0和1均可選；2)當(dāng)上述序列中沒(méi)有1時(shí)，2可選；故滿足條件的序列數(shù)為f(n)=2f(n-1)+2n-1 n 1,-

2、f(1)=3解得 f(n)=2 n-1(2+n).3 . n位四進(jìn)制數(shù)中，2和3出現(xiàn)偶數(shù)次的序列的數(shù)目記為f(n),求f(n)滿足 的遞推關(guān)系.解：設(shè)h(n)表示2出現(xiàn)偶數(shù)次的序列的數(shù)目，g(n)表示有偶數(shù)個(gè)2奇數(shù)個(gè)3 的序列的數(shù)目，由對(duì)稱性它同時(shí)還可以表示奇數(shù)個(gè) 2偶數(shù)個(gè)3的序列的數(shù)目。 則有1h(n)=3h(n-1)+4 n-1-h(n-1),h(1)=3(1)tf(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1)(2)將(1)得到的h(n)=(2 n+4n)/2代入(2),可得f(n+1)= (2 n+4n)/2-2f(n),f(1)=2.4 .求滿足相鄰位不同為0的n

3、位二進(jìn)制序列中0的個(gè)數(shù)f(n).解：這種序列有兩種情況：1)最后一位為0,這種情況有f(n-3)個(gè)；2)最后一位為1,這種情況有2f(n-2)個(gè)；所以f(n)=f(n-3)+2f(n-2)-f(1)=212)=3,fG3)=5.5.求n位0,1序列中“00”只在最后兩位才出現(xiàn)的序列數(shù)f(n).解：最后兩位是“ 00”的序列共有2n-2個(gè)。f(n)包含了在最后兩位第一次出現(xiàn)“ 00”的序列數(shù)，同時(shí)排除了在 n-1位第一次出現(xiàn)“ 00”的可能；f(n-1)表示在第n-1位第一次出現(xiàn)“ 00”的序列數(shù)，同時(shí)同時(shí)排除了在n-2位第一次出現(xiàn)“ 00”的可能；依此類推，有f(n)+f(n-1)+f(n-2

4、)+f(2)=2-f(2)=1,f(3)=1,f(4)=2.6 .求n位0,1序列中“010”只出現(xiàn)一次且在第n位出現(xiàn)的序列數(shù)f(n).解：最后三位是“ 010”的序列共有2n-3個(gè)。包括以下情況：f(n)包含了在最后三位第一次出現(xiàn) 010的個(gè)數(shù)，同時(shí)排除了從n-4到n-2位第一次出現(xiàn)010的可能；f(n-2)包含了從n-4到n-2位第一次出現(xiàn)010的個(gè)數(shù)；f(n-3)包含了從n-5到n-3位第一次出現(xiàn)010的個(gè)數(shù)；2f(n-4)包含了從n-6到n-4位第一次出現(xiàn)010的個(gè)數(shù)(因?yàn)樵诘趎-3位可以取0或1);同理，k 3時(shí)，第n-k-2到n-k位第一次出現(xiàn)010的個(gè)數(shù)為2k-3f(n-k)(因

5、為第n-k位n-3位中間的k-3位可以取0、1,所以有2k-3種 狀態(tài))。所以滿足條件的遞推關(guān)系為rf(n)+f(n-2)+f(n-3)+ +2n-6f(3)=2 n-3 n 6二 f(3)=1,f(4)=2,f(5)=3.7 .有多少個(gè)長(zhǎng)度為n的0,1序列，在這些序列中，既不包含“ 010”，也不包 含 “101” ？解：設(shè)滿足條件的序列數(shù)為f(n)考慮n-1位時(shí)最左邊的情況：1)最左邊為1,則左邊可選0或1生成滿足要求的序列，這種情況有2f(n-2)個(gè)；2)最左邊為01,則左邊只能選1才能滿足要求，這種情況有f(n-3)個(gè)；jf(n)=2f(n-2)+f(n-3)If=1,f(3)=1,4

6、4)=2.8 .在信道上傳輸a,b,c三個(gè)字母組成的長(zhǎng)為n的字符串，若字符串中有兩個(gè) a連續(xù)出現(xiàn)，則信道就不能傳輸.令f(n)表示信道可以傳輸?shù)拈L(zhǎng)為n的字 符串的個(gè)數(shù)，求f(n)滿足的遞推關(guān)系.解：信道上能夠傳輸?shù)拈L(zhǎng)度為n (n 2)的字符串可分成如下四類：1)最左字符為b;2)最左字符為c；3)最左兩個(gè)字符為ab;4)最左兩個(gè)字符為ac；前兩類字符串分別有f(n-1)個(gè)，后兩類字符串分別有f(n-2)個(gè)。容易求出f(1)=32)=8。從而得到rf(n)=2f(n-1)+2f(n-2) (n 3)，f(1)=3,42)=8.9 .求解下列遞推關(guān)系：(1) f(n) 2f(n 1) 2f(n 2

7、).f(1) 3,f(2) 8解：先求這個(gè)遞推關(guān)系的通解，它的特征方程為x2-2x2=0解這個(gè)方程，得Xi 13, X2 13.所以，通解為f(n) g(1 J3)nC2(1 3)n.代入初值來(lái)確定Cl和C2,得G2 ,3232 32.3因此，f(n)2,3(1 2 E3 (一 3)n.2.32、3f(n) 4f(n 1) 4f(n 2)(2) ;f(0) 1,f 3解：此遞推關(guān)系的特征方程為x2-4x+4=0解這個(gè)方程，得Xi=X2=2.所以通解為 f(n)=c i2n+c2n2n.代入初值來(lái)確定Ci和C2,得Ci=1, C2=1/2.因此，f(n)=2 n+2n-1n. f(n) f(n

8、1) 3f(n 2) 5f(n 3) 2f(n 4) f(0) 1,f 0, f(2) 1,f(3) 2解：該遞推關(guān)系的特征方程為x4+x3-3x2-5x-2=0,解得特征根為Xl=X2=X3=-1,X 4=2.所以通解為 f(n)=C i(-1) n+C2n(-1) n+C3n2(-1) n+C42n.代入初值，得 g -,C2-,C3 0,C4 -.939n 7 n 12 n因此，f (n) ( 1) - ( 1) -n - 2 .939/、 f (n) 4f (n 1) 4f(n 2) n 2n(4) ；f(0) 0,f(1) 1解：由于2是特征方程的二重根，所以該遞推關(guān)系的特解為 f

9、(n)=n 2(b1n+b0) - 2n.將它代入遞推關(guān)系化簡(jiǎn)，得到-6b1=1,1-6b1+2b0=0而相應(yīng)齊次遞推關(guān)系的通解為(C+cn) 2n,從而非齊次遞推關(guān)系的通解為2 n 1 nf (n)(C0 C1n) n 2 .62代入初值可得C 0C1.6一 L132n于是 f(n) (n 3n n) 2 . 6f(n) nf(n 1) n! (n 1)(5) ;f(0) 2解：f(1)=f(0)+1!f(2)=2f(1)+2!=2f(0)+2*2!=2!(f(0)+2)f(3)=3f(2)+3!=6f(0)+3*3!=3!(f(0)+3)f(n)=n!(f(0)+n)=n!(n+1).f(

10、n) (n 2)f(n 1) (n 1)(6) ;f(0) 1解：f(n)=(n+2)f(n-1)=(n+2)(n+1)f(n-2)=(n+2)(n+1) 3f(0)=(n+2)!/2.10 .在一圓周上取n個(gè)點(diǎn)，過(guò)每對(duì)點(diǎn)作一弦，且任何三條弦不在圓內(nèi)共點(diǎn)，試 求這些弦把圓分成的區(qū)域的個(gè)數(shù).解：n-1個(gè)點(diǎn)把圓分為f(n-1)部分，在加第n個(gè)點(diǎn)則對(duì)于前n-1個(gè)點(diǎn)來(lái)說(shuō)， 每選3個(gè)點(diǎn)都有3條弦構(gòu)成了一個(gè)三角形。而中間的一點(diǎn)和第n點(diǎn)的連線把 中間和第n點(diǎn)間的弦分成了 2個(gè)部分，增加了 1 一個(gè)域。第n個(gè)點(diǎn)和其它n-1 個(gè)點(diǎn)的連線又把第1, n-1, n點(diǎn)構(gòu)成的三角形分為n個(gè)域。故滿足條件的遞推關(guān)系為rf

11、(n)=f(n-1)+C(n-1,3)+n-1,f(0)=1,f(1)=1,f(2)=2,f(3)=4,f(4)=8.解得 f(n)=1+C(n,2)+C(n-4).11 .設(shè)有n條橢圓曲線，兩兩相交于兩點(diǎn)，任意3條橢圓曲線不相交于一點(diǎn). 問(wèn)這樣的n個(gè)橢圓將平面分割成多少部分？解：設(shè)f(n)表示n個(gè)橢圓將平面分割成的部分的個(gè)數(shù)，則有：一個(gè)橢圓將平面分成內(nèi)、外兩個(gè)部分，兩個(gè)橢圓將平面分成4個(gè)部分。第二個(gè)橢圓的周界被第一個(gè)橢圓分成兩部分，這恰恰是新增加的域的邊界。依此類推，第三個(gè) 橢圓曲線被前面兩個(gè)橢圓分割成 4部分，將平面分割成4 + 4 = 8個(gè)部分。若 n1個(gè)橢圓將平面分割成f(n-1)個(gè)部

12、分，第n個(gè)橢圓和前n1個(gè)橢圓兩兩 相交于兩點(diǎn)，共2 (n-1)個(gè)交點(diǎn)，即新增加的域有2 (n1)個(gè)。故有f(n)=f(n-1)+2(n-1)f(1)=2解得 f(n)=n(n-1)+212 .求n位十進(jìn)制正數(shù)中出現(xiàn)偶數(shù)個(gè)5的數(shù)的個(gè)數(shù).解：設(shè)f(n)表示n位十進(jìn)制正數(shù)中出現(xiàn)個(gè) 5的數(shù)的個(gè)數(shù)，d=d1d2-d-1表示 n-1位十進(jìn)制數(shù)，則若d含有偶數(shù)個(gè)5,則dn取5以外的任何一個(gè)數(shù)；若d 含有奇數(shù)個(gè)5,則dn取5。另n-1位十進(jìn)制的數(shù)共有9X10n-2個(gè)，故遞推關(guān)系r-f(n)=9f(n-1)+ 9義 10n-2-f(n-1)= 9義 10n-2+8f(n-1)f(1)=8.13 . 在一個(gè)平面上

13、畫(huà)一個(gè)圓 , 然后一條一條地畫(huà) n 條與圓相交的直線. 當(dāng) r 是大于 1 的奇數(shù)時(shí) , 第 r 條直線只與前r 1 條直線之一在圓內(nèi)相交. 當(dāng) r是偶數(shù)時(shí) , 第 r 條直線與前r 1 條直線都在圓內(nèi)相交. 如果無(wú) 3 條直線在圓內(nèi)共點(diǎn) , 這 n 條直線把圓分割成多少個(gè)不重疊的部分？解 ：當(dāng) r 是奇數(shù)時(shí)，它只與原來(lái)r 1 條直線之一相交，因此多了兩個(gè)部分；當(dāng) r 是偶數(shù)時(shí)，它與原來(lái)的 r 1 條都相交，因此多了 r 個(gè)交點(diǎn)；故有f(n)=f(n-1)+2 n為奇數(shù)；f(n)=f(n-1)+n n為偶數(shù)；14 . 從 1 到 n 的自然數(shù)中選取k 個(gè)不同且不相鄰的數(shù), 設(shè)此選取的方案數(shù)位f

14、(n,k).1) 求 f(n,k) 滿足的遞推關(guān)系；2) 用歸納法求f(n,k) ；3) 若設(shè) 1 與 n 算是相鄰的數(shù), 并在此假定下從1 到 n 的自然數(shù)中選取k個(gè)不同且不相鄰的數(shù)的方案數(shù)位g(n,k), 試?yán)?f(n,k) 求 g(n,k).解：1)有兩類：選n為f(n-2,k-1)；不選n為f(n-1,k).所以f(n,k)=f(n-2,k-1)+f(n-1,k).2)f(n,k)=C(n-k+1,k).3)f(n,k)=C(n-k+1,k-1)*n/k.15 . 從 1 到 n 的自然數(shù)中選取兩兩之差均大于r 的 k 個(gè)數(shù)1) 求它所滿足的遞推關(guān)系；2) 證明 f (n, k) n

15、 r r ,n r k(r 1)rk解 ：可將本題轉(zhuǎn)換為構(gòu)造相應(yīng)的 0 1 串的問(wèn)題。將這樣的 n 位 0 1 串與 1 到 n 的正整數(shù)對(duì)位，與1 相應(yīng)的整數(shù)選取，與0 相應(yīng)的不取。一個(gè)0 1 串對(duì)應(yīng)一個(gè)選取方案。這也對(duì)應(yīng)將相同的球放入不同的盒子的方案數(shù)。6 4 4 44 7k 4 4 4 4810 .010.0110.01rrr所以fr (n,k)n r(k 1)kk 1 n k r(k 1) 1n k r(k 1)16. 試證： 11Fn 1FnFnFn 1證明 ：可用數(shù)學(xué)歸納法證明1) 當(dāng) n=1 時(shí)，左邊 = 111 ，右邊 = 1 1 ，成立。 0102) 假設(shè) n=k 時(shí)，等式成

16、立，則有10Fk 1FkFk Fk 123n=k+1 時(shí)，有17.解:an 1由1)、2)2kanb,同理可得bnFk 1 FkFk Fk1 可得等式成立。2k2k0 2kbn。由此可得兩個(gè)序列的生成函數(shù)為2kA(x)1 x聯(lián)立解可得A(x) ,B(x)x 3x 1由Fibonacci 數(shù)定義可知Fk FFk1 F,用 FibonacciB(x)1 x2n2k2n1,B(x)x-20x 3x 1,f(n)=f(n-1)+f(n-2)Fk1Fk數(shù)來(lái)表示an和bn.2 k 0 2k 1xA(x)。1 x,其生成函數(shù)為1F(x) 21 x x令 P(x) f (2n)xn,Q(x) f (2n 1)

17、xn ,可得 n 0n 11 xxP(x) -,Q(x)-x 3x 1 x 3x 1所以 an =f(2n),bn=f(2n-1).18 .某人有n元錢，他每天買一次物品，每次買物品的品種很單調(diào)，或者買一 元的甲物品，或者買二元錢的乙物品，或者買二元錢的丙物品.問(wèn)，他花完 這n元錢有多少種不同的方式？解：f(n)表示花完這n元錢的方案數(shù)。則f(n)=f(n-1)+2f(n-2)f(1)=1,f(2)=3.19 .證明：任一個(gè)正整數(shù)n都可以寫(xiě)成不同的Fibonacci數(shù)的和.證明：任意正整數(shù)n可以表示為Fibonacci序列的有限和，即mn= SFi ,其中 S=(0,1),i=1,2,m;SS

18、+1=0,i=1,2,m-1.可以用數(shù)學(xué)歸納法進(jìn)行證明。1) n=1=f(0)=f(1),成立。2)假設(shè)n=k時(shí)等式成立，則n=k+1亦成立，因?yàn)?也是Fibonacci數(shù)。3)由1)、2)可證等式成立。20 .證明：有n個(gè)葉子的完全二叉樹(shù)的個(gè)數(shù)為 Catalan數(shù).證明：令Pn表示給n個(gè)葉子安排位置的方案數(shù)，則有Pn=P R-l+BR-2 +Pn-1 Pl,Pl = P2=1.顯然，R=Q+i,k=1,2,n.21 .證明：從(0,0)點(diǎn)到(n,n)點(diǎn)的除端點(diǎn)外不接觸直線y=x的路徑數(shù)為2h(n),其中,h(n)為 Catalan 數(shù).證明：此題可劃分為兩部分：一部分從(0, 0)到(n, n)的路徑全部在y=x 上方，另一部分全部在下方，由于對(duì)稱性，