李凡長版-組合數(shù)學課后習題答案

PAGEPAGE17第三章遞推關系XE"遞推關系"\y"dìtuīguānxì"在平面上畫n條無限直線,每對直線都在不同的點相交,它們構(gòu)成的無限區(qū)域數(shù)記為f(n),求f(n)滿足的遞推關系XE"遞推關系"\y"dìtuīguānxì".解：f(n)=f(n-1)+2f(1)=2,f(2)=4 解得f(n)=2n.n位三進制數(shù)中,沒有1出現(xiàn)在任何2的右邊的序列的數(shù)目記為f(n),求f(n)滿足的遞推關系XE"遞推關系"\y"dìtuīguānxì".解：設an-1an-2…a1是滿足條件的n-1位三進制數(shù)序列，則它的個數(shù)可以用f(n-1)表示。an可以有兩種情況：不管上述序列中是否有2，因為an的位置在最左邊，因此0和1均可選；當上述序列中沒有1時，2可選；故滿足條件的序列數(shù)為 f(n)=2f(n-1)+2n-1n1, f(1)=3 解得f(n)=2n-1(2+n).n位四進制數(shù)中,2和3出現(xiàn)偶數(shù)次的序列的數(shù)目記為f(n),求f(n)滿足的遞推關系XE"遞推關系"\y"dìtuīguānxì".解：設h(n)表示2出現(xiàn)偶數(shù)次的序列的數(shù)目，g(n)表示有偶數(shù)個2奇數(shù)個3的序列的數(shù)目，由對稱性它同時還可以表示奇數(shù)個2偶數(shù)個3的序列的數(shù)目。則有h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3（1）f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1)（2）將（1）得到的h(n)=(2n+4n)/2代入（2），可得f(n+1)=(2n+4n)/2-2f(n),f(1)=2.求滿足相鄰位不同為0的n位二進制序列中0的個數(shù)f(n).解：這種序列有兩種情況：1)最后一位為0，這種情況有f(n-3)個； 2)最后一位為1，這種情況有2f(n-2)個； 所以f(n)=f(n-3)+2f(n-2) f(1)=2,f(2)=3,f(3)=5.求n位0,1序列中“00”只在最后兩位才出現(xiàn)的序列數(shù)f(n).解：最后兩位是“00”的序列共有2n-2個。f(n)包含了在最后兩位第一次出現(xiàn)“00”的序列數(shù)，同時排除了在n-1位第一次出現(xiàn)“00”的可能；f(n-1)表示在第n-1位第一次出現(xiàn)“00”的序列數(shù)，同時同時排除了在n-2位第一次出現(xiàn)“00”的可能；依此類推，有f(n)+f(n-1)+f(n-2)+…+f(2)=2n-2 f(2)=1,f(3)=1,f(4)=2.求n位0,1序列中“010”只出現(xiàn)一次且在第n位出現(xiàn)的序列數(shù)f(n).解：最后三位是“010”的序列共有2n-3個。包括以下情況：f(n)包含了在最后三位第一次出現(xiàn)010的個數(shù)，同時排除了從n-4到n-2位第一次出現(xiàn)010的可能；f(n-2)包含了從n-4到n-2位第一次出現(xiàn)010的個數(shù)；f(n-3)包含了從n-5到n-3位第一次出現(xiàn)010的個數(shù)；2f(n-4)包含了從n-6到n-4位第一次出現(xiàn)010的個數(shù)（因為在第n-3位可以取0或1）；同理，k3時，第n-k-2到n-k位第一次出現(xiàn)010的個數(shù)為2k-3f(n-k)(因為第n-k位～n-3位中間的k-3位可以取0、1，所以有2k-3種狀態(tài))。 所以滿足條件的遞推關系為 f(n)+f(n-2)+f(n-3)+…+2n-6f(3)=2n-3n6 f(3)=1,f(4)=2,f(5)=3.有多少個長度為n的0,1序列,在這些序列中,既不包含“010”,也不包含“101”？解：設滿足條件的序列數(shù)為f(n)考慮n-1位時最左邊的情況：1)最左邊為1，則左邊可選0或1生成滿足要求的序列，這種情況有2f(n-2)個；最左邊為01，則左邊只能選1才能滿足要求，這種情況有f(n-3)個； f(n)=2f(n-2)+f(n-3) f(2)=1,f(3)=1,f(4)=2.在信道上傳輸a,b,c三個字母組成的長為n的字符串,若字符串中有兩個a連續(xù)出現(xiàn),則信道就不能傳輸.令f(n)表示信道可以傳輸?shù)拈L為n的字符串的個數(shù),求f(n)滿足的遞推關系XE"遞推關系"\y"dìtuīguānxì".解：信道上能夠傳輸?shù)拈L度為n（n2）的字符串可分成如下四類：最左字符為b；最左字符為c；最左兩個字符為ab；最左兩個字符為ac；前兩類字符串分別有f(n-1)個，后兩類字符串分別有f(n-2)個。容易求出f(1)=3,f(2)=8。從而得到f(n)=2f(n-1)+2f(n-2)(n3)f(1)=3,f(2)=8.求解下列遞推關系XE"遞推關系"\y"dìtuīguānxì"：（1）；解：先求這個遞推關系的通解，它的特征方程為x2-2x－2=0 解這個方程，得,.在一個平面上畫一個圓,然后一條一條地畫n條與圓相交的直線.當r是大于1的奇數(shù)時,第r條直線只與前r－1條直線之一在圓內(nèi)相交.當r是偶數(shù)時,第r條直線與前r－1條直線都在圓內(nèi)相交.如果無3條直線在圓內(nèi)共點,這n條直線把圓分割成多少個不重疊的部分？解：當r是奇數(shù)時，它只與原來r－1條直線之一相交，因此多了兩個部分；當r是偶數(shù)時，它與原來的r－1條都相交，因此多了r個交點；故有f(n)=f(n-1)+2n為奇數(shù)；f(n)=f(n-1)+nn為偶數(shù)；從1到n的自然數(shù)中選取k個不同且不相鄰的數(shù),設此選取的方案數(shù)位f(n,k).求f(n,k)滿足的遞推關系XE"遞推關系"\y"dìtuīguānxì"；用歸納法求f(n,k)；若設1與n算是相鄰的數(shù),并在此假定下從1到n的自然數(shù)中選取k個不同且不相鄰的數(shù)的方案數(shù)位g(n,k),試利用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.從1到n的自然數(shù)中選取兩兩之差均大于r的k個數(shù)求它所滿足的遞推關系XE"遞推關系"\y"dìtuīguānxì"；證明解：可將本題轉(zhuǎn)換為構(gòu)造相應的0－1串的問題。將這樣的n位0－1串與1到n的正整數(shù)對位，與1相應的整數(shù)選取，與0相應的不取。一個0－1串對應一個選取方案。這也對應將相同的球放入不同的盒子的方案數(shù)。所以。試證：證明：可用數(shù)學歸納法證明當n=1時，左邊=，右邊=，成立。假設n=k時，等式成立，則有.n=k+1時，有 由1)、2）可得等式成立。設,,,用Fibonacci數(shù)來表示和.解： 同理可得。由此可得兩個序列的生成函數(shù)為。聯(lián)立解可得。由Fibonacci數(shù)定義可知，f(n)=f(n-1)+f(n-2)，其生成函數(shù)為。令，可得所以＝f(2n),＝f(2n-1).某人有n元錢,他每天買一次物品,每次買物品的品種很單調(diào),或者買一元的甲物品,或者買二元錢的乙物品,或者買二元錢的丙物品.問,他花完這n元錢有多少種不同的方式？解：f(n)表示花完這n元錢的方案數(shù)。則f(n)=f(n-1)+2f(n-2)f(1)=1,f(2)=3.證明：任一個正整數(shù)n都可以寫成不同的Fibonacci數(shù)的和.證明：任意正整數(shù)n可以表示為Fibonacci序列的有限和，即n=,其中Si=(0,1),i=1,2,…m;SiSi+1=0,i=1,2,…,m-1.可以用數(shù)學歸納法進行證明。n=1=f(0)=f(1),成立。假設n=k時等式成立，則n=k+1亦成立，因為1也是Fibonacci數(shù)。由1)、2）可證等式成立。證明：有n個葉子的完全二叉樹的個數(shù)為Catalan數(shù).證明：令Pn表示給n個葉子安排位置的方案數(shù),則有 Pn=P1Pn-1+P2Pn-2+…+Pn-1P1,P1=P2=1.顯然，Pk=Ck+1,k=1,2,…,n.證明：從（0,0）點到（n,n）點的除端點外不接觸直線y=x的路徑數(shù)為2h(n),其中,h(n)為Catalan數(shù).證明：此題可劃分為兩部分：一部分從（0，0）到（n，n）的路徑全部在y=x上方，另一部分全部在下方，由于對稱性，故只要考慮一部分即可。記O點（0，0），A點（n，n），O'點（0，1），A'點（n，n＋1）。從O點出發(fā)經(jīng)過OA及OA上方的點到達A點的路徑對應一條從O'點出發(fā)經(jīng)過O'A'點及O'A'上方的點到達A'點的路徑。這是很顯然的。從O'點出發(fā)途經(jīng)OA上的點到達A'點的路徑，即為從O'點出發(fā)穿越O'A'到達A'點的路徑。故對應一條從O點出發(fā)穿越OA到達A點的路徑。所以，從O點出發(fā)經(jīng)過OA及OA上方的點最后到達A點的路徑數(shù)，等于從O'出發(fā)到達A'點的所有路徑數(shù)，減去從O'點出發(fā)途經(jīng)OA上的點到達A'的路徑數(shù)。即?？偟穆窂綌?shù)為。定理3.2.2設是遞推關系(3.2.2)的全部不同的特征根,其重數(shù)分別為,那么遞推關系(3.2.2)的通解為其中證明：由前面的討論知,是遞推關系（3.2.2）的解.再由初值,得到關于的聯(lián)立方程組,其系數(shù)行列式的值為,故可由初值唯一地確定,這說明遞推關系(3.2.2)的任意解均可寫成,其中如前所示.例3求解遞推關系解先求這個遞推關系的通解.它的特征方程為解這個方程,得.所以,通解為代入初值來確定,和,得求解這個方程組,得,,.因此,所求的遞推關系為.3.3常系數(shù)線性非齊次遞推關系的求解階常系數(shù)線性非齊次遞推關系的一般形式為(3.3.1)其中,為常數(shù),.它對應的齊次遞推關系為(3.3.2)定理3.3.1階常系數(shù)線性非齊次遞推關系(3.3.1)的