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

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

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

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

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

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

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

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

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

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由二項式定理知道(i-A-r=f(i-A-r=f(-i/k=0/兩邊分別求積分得j:“d一峪+卅詁所以n仏丿所以n仏丿20.求整數(shù)cb和c,使得對所有的加,因為=0,所以c=lo求級數(shù)的和l3+23+3,因為=0,所以c=lo解令/n=1,l3=a(2、+b,因為3(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.應用組合學論證方法，證明二項式系數(shù)的Xandemionde卷積:對所有的正整數(shù)叫9m2和h,/、叫(rnY+加2、UJ-k.l”)nEk=0作為特殊情形，推導恒等式(5J1)。證明設(shè)S=AjB,AnB=0,IAI=/nL,B=m2則|S|=“+加2。我們可以從集合A中取出k個元素，再從集合B中取出n-k個元素，把它們合起來構(gòu)成S的

11、有舁個元素的子集。因為4的有R個元素的子集有的有舁個元素的子集。因為4的有R個元素的子集有:卄個，因為B的有n-k個元素的子集有(2個，所以S的有川個元素的子集個數(shù)為心丿/“I+m2n=Einin_k37.在(勺-x2+2x3-2x4)9的展開式中xx3xl的系數(shù)是什么？解由多項式定理知道也+勺+兀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.用牛頓二項式定理近似計算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ù)個數(shù)。解設(shè)S是從I到10000的整數(shù)的集合，A是從1到10000的完全平方數(shù)的集合，A2是從1至IJ10000的完全立方數(shù)的集合。因為1002=10000,所以141=1

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

14、=6a,6b,3c的12-組合的個數(shù)。設(shè)S為廠二“，“，”的所有12-了23了23組合的集合，則|S|=12-=91o設(shè)4為r的所有至少有7個d的12組合r*的至少有7個a的同樣可得到丨血卜21r*的至少有7個a的同樣可得到丨血卜21A3+A2nA3-AlrA2nA3=91-(21+21+45)+0+3+3-0=109.確定方程X+x2+x3+x4=20滿足16,0 x27,4xs8,2x46的整數(shù)解的個數(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、非負整數(shù)解的集合，A2為方程兒+乃+兒+九=7的所有滿足）38的非負整數(shù)解的集合，人3為方程）1+2+3+4=7的所有滿足y35的非負整數(shù)解的集合，人4為方程）1+）?2+力+九=7的所有滿足45的非負整數(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ù)解的個數(shù)|nA.nA3nA41=1SI-IAJ-IA,|-|A3|-|A41=120-4-0-10-10=9624.把六個非攻擊型車放到具有如卜所述禁止位置的6行6列棋盤上的方法數(shù)是多少？（c）XXXXX

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

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

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

19、=16種方法；若在部分的禁止位置放兩個非攻擊型車，在許部分的禁止位置放一個非攻擊型車，則有2x5=10種方法。因此，心=18+5+1=24。若在許部分和心部分的禁止位置各放兩個非攻擊型車，則有4x2=8種方法。因此，;-4=8or5=0o把六個非攻擊型車放到具有上述禁止位置的6行6列棋盤上的方法數(shù)是6!qx5+r2x4!-r3x3!+r4x2!-r5xl!=720-9x120+26x24-26x6+8x2-0 x1=12427.8個女孩鬧坐在旋轉(zhuǎn)木馬上。她們可以有多少種方法改變座位，使得每個女孩前面的女孩都與原先的不同？解令S為1,2,3,4,5,6,7,8的全部7!個循壞排列的集合，&為出現(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,人，/”表示斐波那契序列。通過用小的值為卜列每一個表達式賦值，猜測一般公式，然后用數(shù)學歸納法和斐波那契遞歸證明Z。(c)fofi+f2+(-1)九-1-114.14.求解初始值/?o=O,/?1=1,/2=1和加=2的遞推關(guān)系(d)fo+fi+f?解(c)對小的值

21、,列出人和f解(c)對小的值,列出人和f(-爐齊的值如卜。n0fn067813821一2-44-912猜測：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)系當n=0時，/o=O,結(jié)論成立。當1時，=結(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)對F小的n列出f(d)

22、對F小的n列出fn和土辦2的值如下。“o5867813211540104273714-1-114.14.求解初始值/?o=O,/?1=1,/2=1和加=2的遞推關(guān)系-1-114.14.求解初始值/?o=O,/?1=1,/2=1和加=2的遞推關(guān)系猜測：/o+/l2+-+/,?=/nA+l當=0時，/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。因為(-1)4-5x(-1)3+6x(-1)2+4x(-1)-8=0,所以一1是該方程的

23、一個根。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、解對應齊次遞推關(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九_1+4(/?1)/g=311解法一對應齊次遞推關(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加嚴】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ù)個蘋果，最多兩個桔子，3的倍數(shù)個香蕉，最多一個梨。然后從該生成函數(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兩邊求導數(shù)得到1(17)2兩邊再求導數(shù)得到2(1-x)3兩雋得到護怙因此，該序列的生成函數(shù)=fvz,兩邊求導數(shù)得到1(17)2兩邊再求導數(shù)得到2(1-x)3兩雋得到護怙因此，該序列的生成函數(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ù)的個數(shù)，其中4和6每個都出現(xiàn)偶數(shù)次，5和7每個至少出現(xiàn)1次，但對于數(shù)字8和9則沒有限制。解設(shè)饑為滿足條件的位數(shù)的個數(shù)，序列h0JhJl2的指數(shù)生成函數(shù)是XTOC o 1-5 h z423?X_+)(”+)(l+X+)4!2!3!2!_宦+一尸2宀_(戶+2+嚴)(戶_2+1)戶441總*00=s?j=L_嚴一20+孔4X一4嚴+疝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個(等間隔的)點。證明將這些點成對連接起來所得到的”條線段不相交的方法數(shù)等丁第n個Catalan數(shù)Cn。證明設(shè)力“為將圓上的2個點成對連接起來得到n條不相交線段的方法數(shù)。我們證明序列h0,h2，與Catalan數(shù)序列Co,C,C2，滿足同樣的遞推關(guān)系和初始條件。設(shè)圓上的2個點順時針依次排列為a。衛(wèi)2，衛(wèi)若連接線段5你則其左邊和右邊的點不能相互連接，那樣會與aoak相交。aoak左邊的點的數(shù)目和它右邊的點的數(shù)目都應當是偶數(shù)，即k是奇數(shù)。若aoak左邊的點的數(shù)目是2i,則aoak右邊的點的數(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.求前川