組合數(shù)學(xué)第四版(RichardA.Brualdi著)機(jī)械工業(yè)出版社作業(yè)答案

1、第二章作業(yè)答案證明，對(duì)任意給定的52個(gè)整數(shù)，存在兩個(gè)整數(shù)，要么兩者的和能被100整除，要么兩者的差能被100整除。證明用100分別除這52個(gè)整數(shù)，得到的余數(shù)必為0,1,-,99這100個(gè)數(shù)之一。將余數(shù)是0的數(shù)分為一組，余數(shù)是1和99的數(shù)分為一組，余數(shù)是49和51的數(shù)分為一組，將余數(shù)是50的數(shù)分為一組。這樣，將這52個(gè)整數(shù)分成了51組。由鴿巢原理知道，存在兩個(gè)整數(shù)分在了同一組，設(shè)它們是。和工若。和b被100除余數(shù)相同，貝a-b能被100整除。若。和b被100除余數(shù)之和是100,則d+b能被100整除。11.一個(gè)學(xué)生有37天用來(lái)準(zhǔn)備考試。根據(jù)過(guò)去的經(jīng)驗(yàn)，她知道她需要不超過(guò)60小時(shí)的學(xué)習(xí)時(shí)間。她還希

2、望每天至少學(xué)習(xí)1小時(shí)。證明，無(wú)論她如何安排她的學(xué)習(xí)時(shí)間(不過(guò)，每天都是整數(shù)個(gè)小時(shí))，都存在連續(xù)的若干天，在此期間她恰好學(xué)習(xí)了13小時(shí)。證明設(shè)從第一天到第i天她共學(xué)習(xí)了勺小時(shí)。因?yàn)樗刻熘辽賹W(xué)習(xí)1小時(shí)，所以山衛(wèi)2,衛(wèi)37和他+13,02+幻7+13都是嚴(yán)格單調(diào)遞增序列。因?yàn)榭偟膶W(xué)習(xí)時(shí)間不超過(guò)60小時(shí),所以a3760,a37+131個(gè)人中，存在兩個(gè)人，他們?cè)谶@群人中有相同數(shù)目的熟人(假設(shè)沒有人與他/她自己是熟人)。證明因?yàn)槊總€(gè)人都不是自己的熟人，所以每個(gè)人的熟人的數(shù)目是從0到”-1的整數(shù)。若有兩個(gè)人的熟人的數(shù)目分別是0和H-1,則有人誰(shuí)都不認(rèn)識(shí)，有人認(rèn)識(shí)所有的人，這是不可能的。因此，這個(gè)人的熟人的

3、數(shù)目是-1個(gè)整數(shù)之一，必有兩個(gè)人有和同數(shù)目的熟人。第三章作業(yè)答案6.有多少使卜列性質(zhì)同時(shí)成立的人5400的整數(shù)？各位數(shù)字互異。數(shù)字2和7不出現(xiàn)。解因?yàn)橹荒艹霈F(xiàn)數(shù)字0,1,3,4,5,6,8,9,所以整數(shù)的位數(shù)至多為8?？紤]8位整數(shù)。最高位不能為0,因此8位整數(shù)有7xP(7,7)個(gè)?？紤]7位整數(shù)。最高位不能為0,因此8位整數(shù)有7xP(7,6)個(gè)?？紤]6位整數(shù)。最高位不能為0,因此8位整數(shù)有7xP(7,5)個(gè)。考慮5位整數(shù)。最高位不能為0,因此8位整數(shù)有7xP(7,4)個(gè)?？紤]4位整數(shù)。若千位數(shù)字人丁-5,有3xP(7,3)個(gè)。若千位數(shù)字等丁-5,則百位數(shù)字必須大于等于4,有4xP(6,2)個(gè)。根

4、據(jù)加法原理，符合條件的整數(shù)的個(gè)數(shù)為7xP(7,7)+7xP(7,6)+7xP(7,5)+7xP(7,4)+3xP(7,3)+4xP(6,2)=9483015人圍坐一個(gè)圓桌。如杲B拒絕挨著4坐，有多少種圍坐方式？如果B只拒絕坐在A的右側(cè)，又有多少種圍坐方式？解15人圍坐一個(gè)圓桌，有14!種圍坐方式。若B固定坐在4的左側(cè)，則可將54看作一個(gè)整體，有13!種圍坐方式。若B固定坐在4的右側(cè)，則可將43看作一個(gè)整體，有13!種圍坐方式。因此,B不挨著A坐的圍坐方式有14!-2x13!=12x13!種，3不坐在4的右側(cè)的圍坐方式有14!-13!=13x13!種。11.從15個(gè)球員的集合中選人組成11個(gè)球員

5、的足球隊(duì)，其中5人只能踢后衛(wèi)，8人只能踢邊衛(wèi)，2人既能踢后衛(wèi)又能踢邊衛(wèi)。假設(shè)足球隊(duì)有7個(gè)人踢邊衛(wèi)4個(gè)人踢后衛(wèi)，確定足球隊(duì)可能的組隊(duì)方法數(shù)。解設(shè)甲和乙既能踢后衛(wèi)又能踢邊衛(wèi)。若甲和乙均不入選，組隊(duì)方法數(shù)為8、7丿若甲和乙均入選，組隊(duì)方法數(shù)為若甲入選且乙不入選，組隊(duì)方法數(shù)為(5)若甲和乙均不入選，組隊(duì)方法數(shù)為8、7丿若甲和乙均入選，組隊(duì)方法數(shù)為若甲入選且乙不入選，組隊(duì)方法數(shù)為(5)8)78、(8)若乙入選且甲不入選，組隊(duì)方法數(shù)也為因此，組隊(duì)方法數(shù)總共為+2x+2x+n、=11204b丿3e丿4丿21一位秘書在距離家以東9個(gè)街區(qū)、以北7個(gè)街區(qū)的一座人樓里工作。每天他都耍步行16個(gè)街區(qū)去上班。(盯刈他來(lái)

6、說(shuō)可能有多少不同的路線？(b丿如果在他家以東4個(gè)街區(qū)、以北3個(gè)街區(qū)開始向東方向的街區(qū)在水卜(而他又不會(huì)游泳),則有多少條不同的路線？解(a)用E表示向東步行1個(gè)街區(qū)，用N表示向北步行1個(gè)街區(qū)。因?yàn)樵撁貢枰驏|步行9個(gè)街區(qū)，向北步行7個(gè)街區(qū)，總共步行16個(gè)街區(qū)，因此他的上班路線是多重集169E,7N的排列。這樣的排列的個(gè)數(shù)為一=11440o9!7(b)若他從水卜的街區(qū)走過(guò)，則他先要走到離家以東4個(gè)街區(qū)、以北3個(gè)街區(qū)的地方，再向東走一個(gè)街區(qū)，最后走到工作的人樓。他從家走到離家以東4個(gè)街區(qū)、以北3個(gè)街區(qū)的地方7的路線的數(shù)目是多重集4巴3小的排列數(shù)，即=35。他從離家以東5個(gè)街區(qū)、4!3!以北3個(gè)街

7、區(qū)的地方走到工作的人樓的路線的數(shù)目是多重集4巴4N的排列數(shù)，即=70o所以，如果他從水卜的街區(qū)走過(guò)，則他可能有的路線數(shù)是35x70=2450o因4!4!此如果他不從水卜的街區(qū)走過(guò)，他可能有的路線數(shù)是11440-2450=899032&確定多重集S=3s,4b,5c的10-排列的個(gè)數(shù)。10解S的有1個(gè)a,4個(gè)k5個(gè)c的】0排列的個(gè)數(shù)為一=1260。1!4!5!S的有3個(gè)d,2個(gè)b,105個(gè)c的10排列的個(gè)數(shù)為-2520o3!2!5!S的有3個(gè)d,4個(gè)b,10*3個(gè)c的10排列的個(gè)數(shù)為-4200o3!4!3!S的有2個(gè)d,3個(gè)b,105個(gè)c的10排列的個(gè)數(shù)為-2520o3!2!5!S的有2個(gè)d,4

8、個(gè)b,1014個(gè)c的10排列的個(gè)數(shù)為-31502!4!4!10S的有3“個(gè)以個(gè)C的心排列的個(gè)數(shù)為麗亍4200。S的10排列的個(gè)數(shù)為1260+2x2520+2x4200+3150=1785031.方程丑+兀2+心+心=30有多少滿足%!2,x2-5,x48的整數(shù)解?解進(jìn)行變彊代換：)1=-2,y2=x2,旳=兀3+5，)4=兀4_8則方程變?yōu)樵匠虧M足條件的解的個(gè)數(shù)等J噺方程的非負(fù)整數(shù)解的個(gè)數(shù)。新方程的非負(fù)整數(shù)解的個(gè)數(shù)為Q5+4-1、28Q5+4-1、28、(28)、25丿耳丿28x27x263!=3276第五章作業(yè)答案8.用二項(xiàng)式定理證明2=S(2=S(-l/jt=oykyk證明由二項(xiàng)式定理知

9、道(x+y)n=18求和解法1由:1,即一nn解法1由:1,即一nnk+1吐因此,rnyz1/7+1(7k=0H+l工(j=1rnyz1/7+1(7k=0H+l工(j=11n+1+(1)”n72+1M丿(n+1n+l工(d0(n+n+Ik丿解法2由二項(xiàng)式定理知道(i-A-r=f(i-A-r=f(-i/k=0/兩邊分別求積分得j:“d一峪+卅詁所以n仏丿所以n仏丿20.求整數(shù)cb和c,使得對(duì)所有的加,因?yàn)?0,所以c=lo求級(jí)數(shù)的和l3+23+3,因?yàn)?0,所以c=lo解令/n=1,l3=a(2、+b,因?yàn)?(2丿丄=09所以b=82c=6。22,所以a=273b3c=6。卩+23+33+n+6

10、工/n=0kJ)卩+23+33+n+6工/n=0kJ)n+工m=0(n+r(n+1A(n+P(n+2)5+1、+6+-6+4丿(3丿l2)I4J2)3+723=工加=6工m=0m=06(+2)(n+1)/?(/?-1)(n+1)/?n2(n+1)2=+=4!2425.應(yīng)用組合學(xué)論證方法，證明二項(xiàng)式系數(shù)的Xandemionde卷積:對(duì)所有的正整數(shù)叫9m2和h,/、叫(rnY+加2、UJ-k.l”)nEk=0作為特殊情形，推導(dǎo)恒等式(5J1)。證明設(shè)S=AjB,AnB=0,IAI=/nL,B=m2則|S|=“+加2。我們可以從集合A中取出k個(gè)元素，再?gòu)募螧中取出n-k個(gè)元素，把它們合起來(lái)構(gòu)成S的

11、有舁個(gè)元素的子集。因?yàn)?的有R個(gè)元素的子集有的有舁個(gè)元素的子集。因?yàn)?的有R個(gè)元素的子集有:卄個(gè)，因?yàn)锽的有n-k個(gè)元素的子集有(2個(gè)，所以S的有川個(gè)元素的子集個(gè)數(shù)為心丿/“I+m2n=Einin_k37.在(勺-x2+2x3-2x4)9的展開式中xx3xl的系數(shù)是什么？解由多項(xiàng)式定理知道也+勺+兀3+心)=L”聲球嘆孑叨；?1+?2+,l3+,4=n令兀2為-勺，兀3為2*3，可為-2可，川為9,得到(X(X1-X2+2兀3-2%4)9=工+2+川3+川4=9聲(-1產(chǎn)球223垮(_2)心城4葉234丿因此，挿勺瑋的系數(shù)是x(-1)3x(-1)3x2x(-2)2=9心)一403203!x3!

12、xl!x2!42.用牛頓二項(xiàng)式定理近似計(jì)算101/解101/3=(8+2)13=2(1+0.25)1/300=2Sk=032x(1+r1121112511433216333664匕10叫00=2Sk=032x(1+r1121112511433216333664匕10叫2x(l+lxl-34121XXX332116ixlxxlx)3336642.1547第六章作業(yè)答案3.求出從1到10000既不是完全平方數(shù)也不是完全立方數(shù)的整數(shù)個(gè)數(shù)。解設(shè)S是從I到10000的整數(shù)的集合，A是從1到10000的完全平方數(shù)的集合，A2是從1至IJ10000的完全立方數(shù)的集合。因?yàn)?002=10000,所以141=1

13、00o因?yàn)?13=92611000010648=223,所以|血1=21。因?yàn)橐粋€(gè)整數(shù)既是完全平方數(shù)也是完全立方數(shù)的允分必要條件是它是完全六次方數(shù)，46=40961000015625=56,所以|九cA?丨=4。從1到10000既不是完全平方數(shù)也不是完全立方數(shù)的整數(shù)個(gè)數(shù)|n2|=|S|-(|+1A2|)+1nA2|=10000-(100+21)+4=98836.面包店出俗巧克力的、肉桂的和素的炸面包圈，并在一特定時(shí)刻有6個(gè)巧克力、6個(gè)肉桂和3個(gè)素炸面包圈。如果一個(gè)盒子裝12個(gè)面包圈，那么可能有多少種不同的盒裝面包圈組合？解用a,b,c分別表示巧克力的、肉桂的和素的炸而包圈。本題要求的是多重集T

14、=6a,6b,3c的12-組合的個(gè)數(shù)。設(shè)S為廠二“，“，”的所有12-了23了23組合的集合，則|S|=12-=91o設(shè)4為r的所有至少有7個(gè)d的12組合r*的至少有7個(gè)a的同樣可得到丨血卜21r*的至少有7個(gè)a的同樣可得到丨血卜21A3+A2nA3-AlrA2nA3=91-(21+21+45)+0+3+3-0=109.確定方程X+x2+x3+x4=20滿足16,0 x27,4xs8,2x46的整數(shù)解的個(gè)數(shù)。解引入新變看=6X)2=7兀2y3=8_兀3)4=6_兀4則方程X1+x2+x3+x4=2滿足16,0 x27,4xs8,2x4?2+?3+?4=7滿足0）5,0y2-0y34,0y46的

15、非負(fù)整數(shù)解的集合，A2為方程兒+乃+兒+九=7的所有滿足）38的非負(fù)整數(shù)解的集合，人3為方程）1+2+3+4=7的所有滿足y35的非負(fù)整數(shù)解的集合，人4為方程）1+）?2+力+九=7的所有滿足45的非負(fù)整數(shù)解的集合，M|A|=4,|A2|=0,丫2+4-1、|A3|=|A4|=10o若心八則Ac列=0。因此，方程2377+?2+?3+）?4=7滿足0S兒55,0y2-,0y34,0y44的整數(shù)解的個(gè)數(shù)|nA.nA3nA41=1SI-IAJ-IA,|-|A3|-|A41=120-4-0-10-10=9624.把六個(gè)非攻擊型車放到具有如卜所述禁止位置的6行6列棋盤上的方法數(shù)是多少？（c）XXXXX

16、XXX解禁放位置可分成兩個(gè)“獨(dú)立”部分，左上角的人部分，包含5個(gè)位置，右卜角的尸2部分，包含3個(gè)位置。用Q表示把R個(gè)非攻擊型車都放在禁止位置的方法數(shù)。幾=8。若在林部分的禁止位置放兩個(gè)非攻擊型車，則有3+2+1=6種方法；若在尸2部分的禁止位置放兩個(gè)非攻擊型車，則有1種方法：若在人部分和尸2部分的禁止位置各放一個(gè)非攻擊型車，則有5x3=15種方法。因此，廠2=6+1+15=22。若在人部分的禁止位置放兩個(gè)非攻擊型車，在尸2部分的禁止位置放一個(gè)非攻擊型車，則有6x3=18種方法；若在尸2部分的禁止位置放兩個(gè)非攻擊型車，在仟部分的禁止位置放一個(gè)非攻擊型車，則有1x5=5種方法;若在林部分的禁止位置

17、放三個(gè)非攻擊型車，則有1種方法。因此，廠3=18+5+1=24。若在林部分的禁止位置放三個(gè)非攻擊型車，在心部分的禁止位置放一個(gè)非攻擊型車，則有1x3=3種方法；若在許部分和心部分的禁止位置各放兩個(gè)非攻擊型車，則有6x1=6種方法。因此，/-4=3+6=93若在耳部分的禁止位置放三個(gè)非攻擊型車，在尸2部分的禁止位置放兩個(gè)非攻擊型車，則有1種方法，r5=lo把六個(gè)非攻擊型車放到具有上述禁止位置的6行6列棋盤上的方法數(shù)是6!qx5+r2x4!-r3x3!+r4x2!-r5xl!=720-8x120+22x24-24x6+9x2-1=16126.計(jì)算1,2,3,4,5,6的排列込中4中6的個(gè)數(shù)，其中4

18、1,2,3；H1；3工1；，5工5,6以及心工5,6。解所耍求的排列個(gè)數(shù)等把六個(gè)非攻擊型車放到具有如卜所述禁止位置的6行6列棋盤上的方法數(shù)。XXXXXXXXX禁放位置可分成兩個(gè)“獨(dú)立”部分，左上角的人部分，包含5個(gè)位置，右下角的尸2部分，包含4個(gè)位置。用q表示把R個(gè)非攻擊型車都放在禁止位置的方法數(shù)。兒=9。若在許部分的禁止位置放兩個(gè)非攻擊型車，則有4種方法；若在尸2部分的禁止位置放兩個(gè)非攻擊型車，則有2種方法：若在R部分和心部分的禁止位置各放一個(gè)非攻擊型車，則有5x4=20種方法。因此廠2=4+2+20=26。若在林部分的禁止位置放兩個(gè)非攻擊型車，在巧部分的禁止位置放一個(gè)非攻擊型車，則有4x4

19、=16種方法；若在部分的禁止位置放兩個(gè)非攻擊型車，在許部分的禁止位置放一個(gè)非攻擊型車，則有2x5=10種方法。因此，心=18+5+1=24。若在許部分和心部分的禁止位置各放兩個(gè)非攻擊型車，則有4x2=8種方法。因此，;-4=8or5=0o把六個(gè)非攻擊型車放到具有上述禁止位置的6行6列棋盤上的方法數(shù)是6!qx5+r2x4!-r3x3!+r4x2!-r5xl!=720-9x120+26x24-26x6+8x2-0 x1=12427.8個(gè)女孩鬧坐在旋轉(zhuǎn)木馬上。她們可以有多少種方法改變座位，使得每個(gè)女孩前面的女孩都與原先的不同？解令S為1,2,3,4,5,6,7,8的全部7!個(gè)循壞排列的集合，&為出現(xiàn)

20、模式f(f+l)的循環(huán)排列的集合(lz7),人8為出現(xiàn)模式81的循壞排列的集合。若且九,是8集合1,2,3,4,567,8中的不同整數(shù)，則|如|=(7-燈!。|人|=1。因此,/=!0、6!+5!-4!+廠8、3!-2!+8、1!-3Z0?V丿0!+1=1625|As|=7!-她們可以有1625種方法改變座位。第七章作業(yè)答案1設(shè)To,人，/”表示斐波那契序列。通過(guò)用小的值為卜列每一個(gè)表達(dá)式賦值，猜測(cè)一般公式，然后用數(shù)學(xué)歸納法和斐波那契遞歸證明Z。(c)fofi+f2+(-1)九-1-114.14.求解初始值/?o=O,/?1=1,/2=1和加=2的遞推關(guān)系(d)fo+fi+f?解(c)對(duì)小的值

21、,列出人和f解(c)對(duì)小的值,列出人和f(-爐齊的值如卜。n0fn067813821一2-44-912猜測(cè)：Z(-I)kfkk=00(-1)“九7-1若=0若1-1-114.14.求解初始值/?o=O,/?1=1,/2=1和加=2的遞推關(guān)系-1-114.14.求解初始值/?o=O,/?1=1,/2=1和加=2的遞推關(guān)系當(dāng)n=0時(shí)，/o=O,結(jié)論成立。當(dāng)1時(shí)，=結(jié)論成立。設(shè)心1且f九“-1,則k=0TOC o 1-5 h zn+Ln工(-1)人=(-1)fk+(-1)，+1/?1+1=(-1)九-1-1+(-1)/1+1/+1R=0R=0=九+L-九-1)-1=九-1(d)對(duì)F小的n列出f(d)

22、對(duì)F小的n列出fn和土辦2的值如下?！皁5867813211540104273714-1-114.14.求解初始值/?o=O,/?1=1,/2=1和加=2的遞推關(guān)系-1-114.14.求解初始值/?o=O,/?1=1,/2=1和加=2的遞推關(guān)系猜測(cè)：/o+/l2+-+/,?=/nA+l當(dāng)=0時(shí)，/o=0=結(jié)論成立。設(shè)荒+/12+用=九九+則fo+/?+fn+fnL=九九+1+fLl=fnfn+A+l)=九+1九+2hn=5/?i-6/爪2-4/?3+敗-4，(24)。解特征方程為J-5宀6“+4兀-8=0。因?yàn)?-1)4-5x(-1)3+6x(-1)2+4x(-1)-8=0,所以一1是該方程的

23、一個(gè)根。x4一5x3+6x2+4x-8=x4+x3-6x3-6x2+12x2+12x-8x-8=x3(x+1)-6x2(x+l)+12x(x+l)-8(x+1)=(x3-6x2+12x-8)(x+l)=(x-2)3(x+1)因此，一般解為hn=cL2+c2n2ft+c3n22n+c4(-l)n(77=0)q+C4=0(/?=!)2q+2c2+2c3-c4=1(n=2)4q+8c2+16cs+c4=15=3)8q+24c2+72c3-c4=2解該方程組得到C=靂c2=C3=_寺。4=-尋因此，尋x2“+卻x2”-加2心_尋x(l)“18.求解非齊次遞推關(guān)系hn=4/q_i+3x2(/?1)民=1

24、解對(duì)應(yīng)齊次遞推關(guān)系的特征方程為x-4=0,它的特征根為4。設(shè)該非齊次遞推關(guān)系的特解為p2n,貝Ijp2,:=4p2z,1+3x2z,因而p=2p+3,因此卩=一3。該非齊次遞推關(guān)系的一般解為hn=c4-3x2o令n=0,得c-3=l,解得c=4。因此，心=4+i3x2。26.求解非齊次遞推關(guān)系hn=4九_(tái)1+4(/?1)/g=311解法一對(duì)應(yīng)齊次遞推關(guān)系的特征方程為x-4=0,它的特征根為4。設(shè)該非齊次遞推關(guān)系的特解為pn4n,則刃4=4xpS-l)x4+4J解得p=l。該非齊次遞推關(guān)系的一般解為hn=c4n+4,lno令n=0.得c=3。因此，心=(“+3)x4。00解法二該序列的生成函數(shù)g

25、=工饑HOH=0(1-4x)g(x)=(1-4x)hxft=hxft-f4加嚴(yán)】n=0n=0n=Q=ho+Shnx，t-丈4心2“0+丈(/?“-4也)兀71=1?T=1?T=11l-4x=h0+丈4“於=3+士4”於=2+丈4”於=1l-4xTOC o 1-5 h z?i=l?:=1n=02t甘E+序coco8=24x+(“+1)4x=(n+3)40n=0n=0n=0因此，hn=(m+3)x4/:o30.確定蘋呆、桔子、香蕉和梨的袋裝水果的袋數(shù)心的生成函數(shù)，其中各袋要有偶數(shù)個(gè)蘋果，最多兩個(gè)桔子，3的倍數(shù)個(gè)香蕉，最多一個(gè)梨。然后從該生成函數(shù)求出九的公式。解生成函數(shù)TOC o 1-5 h z88

26、g(X)=(宀)(1+X+”)(戶)(1+工)刃=0n=0(l+x+x2)(l+x)_1?j=0(1-兀2)(1-P)(1-X)2?j=0因此，hn=/?+1o32.令屁,九，力2,，饑，是由幾=定義的序列(0)。確定該序列的生成函數(shù)。28n=08n=01-X44兩邊求導(dǎo)數(shù)得到1(17)2兩邊再求導(dǎo)數(shù)得到2(1-x)3兩雋得到護(hù)怙因此，該序列的生成函數(shù)=fvz,兩邊求導(dǎo)數(shù)得到1(17)2兩邊再求導(dǎo)數(shù)得到2(1-x)3兩雋得到護(hù)怙因此，該序列的生成函數(shù)=fvz,=/=0/?=0)/2=0(IF32.令他,九，力2,九，是由九=；J定義的序列5X0)。確定該序列的指數(shù)生成函數(shù)。解該序列的指數(shù)生成函

27、數(shù)n200n00g%)也訃工H=0；T=0k7=?川兀B_1?兀”+2=2麗匚麗=矗-2)!=殆41確定所有的數(shù)字至少是4的位數(shù)的個(gè)數(shù)，其中4和6每個(gè)都出現(xiàn)偶數(shù)次，5和7每個(gè)至少出現(xiàn)1次，但對(duì)于數(shù)字8和9則沒有限制。解設(shè)饑為滿足條件的位數(shù)的個(gè)數(shù)，序列h0JhJl2的指數(shù)生成函數(shù)是XTOC o 1-5 h z423?X_+)(”+)(l+X+)4!2!3!2!_宦+一尸2宀_(戶+2+嚴(yán))(戶_2+1)戶441總*00=s?j=L_嚴(yán)一20+孔4X一4嚴(yán)+疝2訂+11總*00=s?j=L6n-2x5+3x4-4x3+3x2-2*4庚1201200若川=0因此，心62x5+3x44x3+3x2-2

28、“4若淪1第八章作業(yè)答案1.設(shè)在圓上選擇2個(gè)(等間隔的)點(diǎn)。證明將這些點(diǎn)成對(duì)連接起來(lái)所得到的”條線段不相交的方法數(shù)等丁第n個(gè)Catalan數(shù)Cn。證明設(shè)力“為將圓上的2個(gè)點(diǎn)成對(duì)連接起來(lái)得到n條不相交線段的方法數(shù)。我們證明序列h0,h2，與Catalan數(shù)序列Co,C,C2，滿足同樣的遞推關(guān)系和初始條件。設(shè)圓上的2個(gè)點(diǎn)順時(shí)針依次排列為a。衛(wèi)2，衛(wèi)若連接線段5你則其左邊和右邊的點(diǎn)不能相互連接，那樣會(huì)與aoak相交。aoak左邊的點(diǎn)的數(shù)目和它右邊的點(diǎn)的數(shù)目都應(yīng)當(dāng)是偶數(shù)，即k是奇數(shù)。若aoak左邊的點(diǎn)的數(shù)目是2i,則aoak右邊的點(diǎn)的數(shù)目就是2(rz-l-/)o隨著k從1變到2/7-1,j從0變到1。因此序列力0血，力2,滿足遞推關(guān)系hn=z+h片2+h10-2、令則幻？=一.。由定理7.6.111道序列g(shù)i，g2，g3,滿足遞推關(guān)系心-1丿S8/1-1+g2g“-2+gn-.S1因此，C”=g”+L=S.8n+g2g”-L+SnSl=+ClCn-2+Cn-lCQ又有/?O=1=CO,序列h0J,h2，與Catalan數(shù)序列C0,C15C2,-滿足同樣的遞推關(guān)系和初始條件。8.求前川