1、精選優質文檔-傾情為你奉上組合數學引論課后答案習題一1.1 任何一組人中都有兩個人，它們在該組內認識的人數相等。1.2 任取11個整數，求證其中至少有兩個數，它們的差是10的倍數1.3 任取n+1個整數，求證其中至少有兩個數，它們的差是n的倍數1.4 在1.1節例4中證明存在連續的一些天，棋手恰好下了k盤棋(k=1,2,，21).問是否可能存在連續的一些天，棋手恰好下了22盤棋1.5 將1.1節例5推廣成從1,2，2n中任選n+1個數的問題1.6 從1,2,200中任取100個整數，其中之一小于16，那么必有兩個數，一個能被另一個整除1.7 從1,2,200中取100個整數，使得其中任意兩個數

2、之間互相不能整除1.8 任意給定52個數，它們之中有兩個數，其和或差是100的倍數1.9 在坐標平面上任意給定13個整點（即兩個坐標均為整數的點），則必有一個以它們中的三個點為頂點的三角形，其重心也是整點。1.10 上題中若改成9個整點，問是否有相同的結論？試證明你的結論1.11 證明：一個有理數的十進制數展開式自某一位后必是循環的。1.12 證明：對任意的整數N，存在著N的一個倍數，使得它僅有數字0和7組成。（例如，N=3,我們有;N=4,有;N=5,有;）1.13(1) 在一邊長為1的等邊三角形中任取5個點，則其中必有兩個點，該兩點的距離至多為；(2) 在一邊長為1的等邊三角形中任取10個

3、點，則其中必有兩個點，該兩點的距離至多為；(3) 確定，使得在一邊長為1的等邊三角形中任取個點，則其中必有兩個點，該兩點的距離至多為；1.14 一位學生有37天時間準備考試，根據以往的經驗，她知道至多只需要60個小時的復習時間，她決定每天至少復習1小時，證明：無論她的復習計劃怎樣，在此期間都存在一些天，她正好復習了13個小時。1.15 從1,2,2n中任選n+1個整數，則其中必有兩個數，它們的最大公約數為1出的數屬于同一個鴿巢，即它們的最大公約數為11.16 針對1.1節的例6，當m,n不是互素的兩個整數時，舉例說明例中的結論不一定成立習題二2.1 證明：在一個至少有2人的小組中，總存在兩個人

4、，他們在組內所認識的人數相同。證明：假設沒有人誰都不認識：那么每個人認識的人數都為1,n-1，由鴿巢原理知，n個人認識的人數有n-1種，那么至少有2個人認識的人數相同。假設有1人誰都不認識：那么其他n-1人認識的人數都為1,n-2，由鴿巢原理知，n-1個人認識的人數有n-2種，那么至少有2個人認識的人數相同。假設至少有兩人誰都不認識，則認識的人數為0的至少有兩人。專心-專注-專業2.2 任取11個整數，求證其中至少有兩個數的差是10的整數倍。證明：對于任意的一個整數，它除以10的余數只能有10種情況：0，1，9。現在有11個整數，由鴿巢原理知，至少有2個整數的余數相同，則這兩個整數的差必是10

5、的整數倍。2.3 證明：平面上任取5個坐標為整數的點，則其中至少有兩個點，由它們所連線段的中點的坐標也是整數。證明：有5個坐標，每個坐標只有4種可能的情況：（奇數，偶數）；（奇數，奇數）；（偶數，偶數）；（偶數，奇數）。由鴿巢原理知，至少有2個坐標的情況相同。又要想使中點的坐標也是整數，則其兩點連線的坐標之和為偶數。因為 奇數+奇數 = 偶數 ； 偶數+偶數=偶數。因此只需找以上2個情況相同的點。而已證明：存在至少2個坐標的情況相同。證明成立。2.4 一次選秀活動，每個人表演后可能得到的結果分別為“通過”、“淘汰”和“待定”，至少有多少人參加才能保證必有100個人得到相同的結果？證明：根據推論

6、2.2.1，若將3*（100-1）+1=298個人得到3種結果，必有100人得到相同結果。2.5 一個袋子里裝了100個蘋果、100個香蕉、100個橘子和100個梨。那么至少取出多少水果后能夠保證已經拿出20個相同種類的水果？證明：根據推論2.2.1，若將4*（20-1）+ 1 = 77個水果取出，必有20個相同種類的水果。2.6 證明：在任意選取的n+2個正整數中存在兩個正整數，其差或和能被2n整除。（書上例題2.1.3）證明：對于任意一個整數，它除以2n的余數顯然只有2n種情況，即：0，1，2，2n-2，2n-1。而現在有任意給定的n+2個整數，我們需要構造n+1個盒子，即對上面2n個余數

7、進行分組，共n+1組：0,1，2n-1,2，2n-2,3,2n-3,，n-1,n+1，n。根據鴿巢原理，n+2個整數，必有兩個整數除以2n落入上面n+1個盒子里中的一個，若是0或n則說明它們的和及差都能被2n整除；若是剩下n-1組，因為一組有兩個余數，余數相同則它們的差能被2n整除，不同則它們的和能被2n整除。證明成立。2.7 一個網站在9天中被訪問了1800次，證明：存在連續的3天，這個網站的訪問量超多600次。證明：設網站在9天中訪問數分別為a1，a2，.，a9 其中a1+a2+.+a9 = 1800，令a1+a2+a3 = b1，a4+a5+a6 = b2，a7+a8+a9 = b3因為

8、（b1+b2+b3）/3 >= 600 由推論2.2.2知，b1，b2，b3中至少有一個數大于等于600。所以存在有連續的三天，訪問量大于等于600次。2.8 將一個矩形分成5行41列的網格，每個格子涂1種顏色，有4種顏色可以選擇，證明：無論怎樣涂色，其中必有一個由格子構成的矩形的4個角上的格子被涂上同一種顏色。證明：首先對一列而言，因為有5行，只有4只顏色選擇，根據鴿巢原理，則必有兩個單元格的顏色相同。另外，每列中兩個單元格的不同位置組合有=10種，這樣一列中兩個同色單元格的位置組合共有10*4=40種情況。而現在共有41列，根據鴿巢原理，無論怎樣涂色，則必有兩列相同，也就是必有一個由

9、格子構成的矩形的4個角上的格子是同一顏色。2.9 將一個矩形分成(m+1)行列的網格每個格子涂1種顏色，有m種顏色可以選擇，證明：無論怎么涂色，其中必有一個由格子構成的矩形的4個角上的格子被涂上同一種顏色。證明：（1）對每一列而言，有（m+1）行，m種顏色，有鴿巢原理，則必有兩個單元格顏色相同。（2）每列中兩個單元格的不同位置組合有種，這樣一列中兩個同色單元格的位置組合共有 種情況（3）現在有列，根據鴿巢原理，必有兩列相同。證明結論成立。2.10 一名實驗員在50天里每天至少做一次實驗，而實驗總次數不超過75。證明一定存在連續的若干天，她正好做了24次實驗。證明：令b1，b2，.，b50 分別

10、為這50天中他每天的實驗數，并做部分和a1 = b1，a2 = b1+b2 ，。a50 = b1+b2+.+b50 .由題，bi>=1(1<=i<=50)且a50<=75所以 1<=a1<a2<a3<<a50<=75 (*)考慮數列 a1，a2，.，a50，a1+24，a2+24，a50+24，它們都在1與75+24=99之間。由鴿巢原理知，其中必有兩項相等。由（*）知，a1，a2，.，a50互不相等，從而a1+24，.a50+24 也互不相等，所以一定存在1<=i<j<=50, 使得aj = ai+24，即 24=

11、aj-ai=(b1+b2+b3+bi+bj)-(b1+b2+bi)=所以從第i+1天到第j天這連續j-i天中，她正好做了24次實驗。2.11 證明：從S=1,3,5,599這300個奇數中任意選取101個數，在所選出的數中一定存在2個數，它們之間最多差4。證明：將S劃分為1,3,5，7,9,11, 595,597,599共100組，由鴿巢原理知任意選取101個數中必存在2個數來自同一組，即其差最多為4.2.12 證明：從1200中任意選取70個數，總有兩個數的差是4，5或9。證明：設這70個數為a1,a2,a70,a1+4,a2+4,a70+4,a1+9,a2+9,a70+9,取值范圍209，

12、共210個數2.13 證明：對于任意大于等于2的正整數n，都有R(2,n)=n。證明：要證R（2，n）= n，用紅藍兩色涂色Kn的邊。當n=2時，R(2,2)=2，因為不管用紅還是藍色都是完全二邊形。假設當n=k時 成立 ，即存在R(2,k)=k（沒有一條紅邊，只有藍邊），當n=k+1時，R（2，k+1）若無紅邊，要想有完全k+1邊形，必得有k+1個點，即R（2，k+1）=k+1。證明成立。習題三3.1 有10名大學生被通知參加用人單位的面試，如果5個人被安排在上午面試，5個人被安排在下午面試，則有多少種不同的安排面試的順序？解：上午的5個人全排列為5！下午的5個人全排列為5！所以有，共144

13、00種不同的安排方法。3.2 某個單位內部的電話號碼是4位數字，如果要求數字不能重復，那么最多可有多少個號碼？如果第一位數字不能是0，那么最多能有多少個電話號碼？解：由于數字不能重復，0-9共10個數字，所以最多有10*9*8*7=5040種號碼；若第一位不能是0，則最多有9*9*8*7=4536種號碼。3.3 18名排球運動員被分成A,B,C三個組，使得每組有6名運動員，那么有多少種分法？如果是分成三個組（不可區別），使得每組仍有6名運動員，那么有多少種分法？解：1)種2) /3!3.4 教室有兩排，每排8個座位。現有學生14人，其中的5個人總坐在前排，4個人總坐在后排，求有多少種方法將學生

14、安排在座位上？解：前排8個座位，5人固定，共種方法；后排8個座位，4人固定，共種方法；前排和后排還剩7個座位，由剩下的5人挑選5個座位，共種方法；則一共有種安排方法。3.5 將英文字母表中的26個字母排序，要求任意兩個元音字母不能相鄰，則有多少種排序方法？解：先排21個輔音字母，共有21！再將5個元音插入到22個空隙中，故所求為(插入法)3.6 有6名先生和6名女士圍坐一個圓桌就餐，要求男女交替就坐，則有多少種不同的排坐方式？解：6男全排列6!；6女全排列6！；6女插入6男的前6個空或者后6個空，即女打頭或男打頭6!*6!*2；再除以圍圈重復得(6!*6!*2)/12=6!*5!或男6的圓排列

15、為5！，對每個男的排列，女要在他們之間的6個位置，進行線性排列6！（而不是5！）。（圓排列可以通過線性排列來解決）3.7 15個人圍坐一個圓桌開會，如果先生A拒絕和先生B和C相鄰，那么有多少種排坐方式？解：15人圓排列14！；A與B相鄰有2*14!/14=2*13!；A與C相鄰有2*14!/14=2*13!；A與BC同時相鄰有2*13!/13=2*12!；于是A不與B、C相鄰的坐法共14!- 2*13!- 2*13!+ 2*12!（用到了容斥原理）3.8 確定多重集的11-排列數？解：M的11排列=M-a的11排列+M-b的11排列+M-c的11排列，即=27720當然了，容斥原理，生成函數也

16、可以做。3.9求方程，滿足的整數解的個數。解：令則有，由定理3.3.3，解個數為：3.10書架上有20卷百科全書，從中選出4卷使得任意兩本的卷號都不相鄰的選法有多少種？解：n=20，r=4，證明見38頁。若卷號差為2，3，。，公式為？3.11確定(2x-3y)5展開式中x4y和x2y4的系數。解：1）：，系數為-2402）：系數為0。3.12確定(1+x)-5展開式中x4的系數。解：，n=5，r=4，則系數為3.13 確定(x +2y+3z)8展開式中x4y2x2的系數。解：3.14 證明組合等式：，其中n,k為正整數。解：右邊是（n+k+1）元集合上k個元素子集的個數，這些子集可分為以下k+

17、1類：第1類：k元子集中不含a1的子集有 個;第2類：k元子集中含a1而不含a2的子集是 個;第3類：k元子集中含a1和a2，而不含a3的子集是第k+1類：k元子集中含a1，a2，, ak，而不含ak+1的子集是由加法原理得證。根據組合意義進行證明3.15利用 ，求。解： 首先有：（p51的(3)）根據已知條件代入以上等式得：又由得，則原式3.16在一局排球比賽中，雙方最終的比分是25:11，在比賽過程中沒有出現5平的比分，求有多少種可能的比分記錄？解：根據題意，相當于求從點(0,0)到點(25,11)且不經過(5,5)的非降路徑數，即為：3.17在一局乒乓球比賽中，運動員甲以11:7戰勝運動

18、員乙，若在比賽過程中甲從來沒有落后過，求有多少種可能的比分記錄？解：根據題意，相當于求從點(0,0)到點(11,7)且從下方不穿過y=x的非降路徑數，見58頁，即為：3.18把20個蘋果和20個橘子一次一個的分發給40個幼兒園的小朋友，如果要求分發過程中任意時刻籃子中余下的兩種水果數目都不相同（開始和結束時除外），求有多少種分法方法？解：根據題意，相當于求從點(0,0)到點(20,20)且不接觸y=x的非降路徑數，即為：n=20，則方法數為：3.19計算和。解：1）一個遞推公式，2）3.20 （1）證明 S(n,3)=方法一：先 考慮3個盒子不同，要保證每個盒子非空：總數為3n，排除到一個盒子

19、為空和兩個盒子為空的情況，即：一個盒子為空（放到兩個盒子去），例如第一個盒子為空,第二和第三不空：3（ 2n-2）兩個盒子為空，例如第一個和第二盒子為空：3*1（3n-3（ 2n-2）-3）/3!還可以直接考慮盒子相同。（2）證明：相當于n個不同球放到相同的n-2個盒子，每個盒子非空，至少為1個，這樣使得剩余的2個球要到n-2個盒子，即使得一個盒子有3個，或有二個盒子都裝2個球：使得一個盒子有3個球：C(n,3)有二個盒子都裝2個球：C（n,4）C(4,2)/2!3.21（1）會議室中有2n+1個座位，現擺成3排，要求任意兩排的座位都占大多數，求有多少種擺法？解：如果沒有附加限制則相當于把2n

20、個相同的小球放到3個不同的盒子里，有種方案，而不符合題意的擺法是有一排至少有n+1個座位。這相當于將n+1個座位先放到3排中的某一排，再將剩下的2n-(n+1)=n-1個座位任意分到3排中，這樣的擺法共有種方案，所以符合題意的擺法有：可以用代數法(2) 會議室中有2n個座位，現擺成3排，要求任意兩排的座位都占大多數，求有多少種擺法？習題四4.1在1到1000之間不能被2，5和11整除的整數有多少個？解：設S是這1000個數的集合，性質是可被2整除，性質是可被5整除，性質是可被11整除。，4.3一項對于A,B,C三個頻道的收視調查表明，有20%的用戶收看A，16%的用戶收看B，14%的用戶收看C

21、，8%的用戶收看A和B，5%的用戶收看A和C，4%的用戶收看B和C，2%的用戶都看。求不收看A,B,C任何頻道的用戶百分比？解4.2求1到1000之間的非完全平方，非完全立方，更不是非完全四次方的數有多少個？解：設S是1000個數的集合，性質是某數的完全平方，性質是某數的完全立方，性質是某數的完全四次方。，4.4某雜志對100名大學新生的愛好進行調查，結果發現他們都喜歡看球賽和電影、戲劇。其中58人喜歡看球賽，38人喜歡看戲劇，52人喜歡看電影，既喜歡看球賽又喜歡看戲劇的有18人，既喜歡看電影又喜歡看戲劇的有16人，三種都喜歡看的有12人，求有多少人只喜歡看電影？解：由題意可得，P1,P2,P

22、3分別表示喜歡看球賽、電影和戲劇的學生，相應的學生集合分別為A1,A2,A3，依題意，這100名大學生中每人至少有三種興趣中的一種，則所以可得既喜歡看球賽有喜歡看電影的人有因此只喜歡看電影的人有=52-(26+16)+12=22人4.5某人有六位朋友，他跟這些朋友每一個都一起吃過晚餐12次，跟他們中任二位一起吃過6次晚餐，和任意三位一起吃過4次晚餐，和任意四位一起吃過3次晚餐，任意五位一起吃過2次晚餐，跟六位朋友全部一起吃過一次晚餐，另外，他自己在外吃過8次晚餐而沒碰見任何一位朋友，問他共在外面吃過幾次晚餐?4.6計算多重集S=4a, 3b, 4c,6d 的12-組合的個數？解：令其中， ，4

23、.7計算多重集S=a, 4b, 5c,6d 的10-組合的個數？解：將，其他思想同上題。其中，4.8用容斥原理確定如下兩個方程的整數解的個數。1）x1+x2+x3=15，其中x1,x2, x3都是非負整數其都不大于7；2）x1+x2+x3+x4=20，其中x1,x2, x3, x4都是正整數其都不大于9；解：1）與7a,7b,7c的15組合數相等，為282），因此用代替，代替，代替，代替有與8a,8b,8c,8d的16組合數相等為4894.9 定義D0=1，證明：證明：考慮到n個數的全排列包含錯位排列和非錯排，其中表示在n個數中任選k個，這個k個數構成了一個錯排，而剩余的n-k個數還在原來的位

24、置。，顯然（另一種方法：組合分析法）4.10證明：Dn滿足：為整數且證明：由定理4.3.1得4.11有10名女士參加一個宴會，每人都寄存了一頂帽子和一把雨傘，而且帽子、雨傘都是互不相同的，當宴會結束的離開的時候，如果帽子和雨傘都是隨機的還回的，那么有多少種方法使得每位女士拿到的物品都不是自己的？解：由于帽子全部拿錯和雨傘全部拿錯是兩個相互獨立的事件，設帽子全錯為雨傘全錯為解4.13計算棋盤多項式R( )。解：R( ) = x*R()+R( )=x*(1+3x+x2)+(1+x)*R( )= x3+3x2+x+(1+x)xR()+R()= x3+3x2+x+(1+x)x(1+x)+(1+4x+2

25、x2)= 5x3+12x2+7x+14.14有A,B,C,D,E五種型號的轎車，用紅、白、藍、綠、黑五種顏色進行涂裝。要求A型車不能涂成黑色；B型車不能涂成紅色和白色；C型車不能涂成白色和綠色；D型車不能涂綠色和藍色；E型號車不能涂成藍色，求有多少種涂裝方案？解：A B C D E紅白藍綠黑1.若未規定不同車型必須涂不同顏色，則：涂裝方案2.若不同車型必須涂不同顏色，則：禁區的棋盤多項式為：1+8x+22x2+25x3+11x4+x5所以：5！-8*4！+22*3！-25*2！+11*1！-1=204.15計算（舍）4.16計算T=1, 2, 3，4的長度為4的圓排列數。（舍）補：（1）在12

26、000中能被7整除，但不能被6和10整除的個數。證明：A1,A2,A3表示被6、7和10整除的數的子集，所求：=219(2)在12000中至少被2、3和5兩個數整除的數的個數？=534習題五5.1 求如下數列的生成函數。（1）；（2）；（3）； （4）；（5）； （6）；解：（1）由已知得故（2）設則又因為故或者（3）（4）（5）（6）5.2 求如下數列的指數生成函數。（1）；（2）；（3）；解： （1）（2）(3) 則故5.3 已知數列的生成函數是，求.解： 而故5.4 求展開式中的系數是多少？(1) 若取0，則取5個，這種情況有種；(2) 若取1，則取3個，這種情況有或；(3) 若取2，則

27、取1個，這種情況有；故系數為= 。其他方法5.5 三個人每個人投一次骰子，有多少種方法使得總點數為9？解：這相當于有9個球，用隔板將其分成3組，共有種方法。又因為這次點數小于等于6，即711，171和117三種情況不符，故共有25種方法。5.6 求在102和104之間的各位數字之和等于5？解：(1) 三位數時，相當于的非負整數解的個數。故中為展開式的系數。(2) 四位數時，相當于的非負整數解的個數。5.7 一個1×n的方格圖形用紅、藍、綠和橙四種顏色涂色，如果有偶數個方格被涂成紅色，還有偶數個方格被涂成綠色，求有多少種方案？解：涂色方案數為則：因此：，所以有種方案。5.8 有4個紅球

28、，3個黃球，3個藍球，每次從中取出5個排成一行，求排列的方案數？解：設每次取出的k個球的排列數為，數列的指數型生成函數為則有而我們所求的是的系數。故有。5.9 計算用3個A，3個G，2個C和1個U構成長度為2不同的RNA鏈的數量。解： 中的系數，有=15.5.10計算和。解：(1)構造多項式則即的系數，則，故。(2)，的非負整數解為(0,0,4), (1,2,3), (0,2,2), (0,3,1), (0,4,0), (1,0,3), (1,1,2), (1,2,1) , (1,3,0), (2,0,2), (2,1,1) , (2,2,0) , (3,0,1), (3,1,0), (4,0

29、,0)5.11設表示把元集劃分成非空子集的方法數，我們稱為Bell數。證明：。證明：當有1個盒子時，方法數，當有2個盒子時，方法數，當有k個盒子時，方法數，當有n個盒子時，方法數，當有n+1個盒子時，至少有一個空盒，不符。故5.12有重為1g的砝碼重為1g的3個，重為2g的4個，重為4g的2個，求能稱出多少種重量？解：即求多項式中展開式有多少項(除1外)，原多項式故共有19種重量。5.13 已知數列的指數生成函數是，求.解：設ak=5, k不等于2ak=7, k =2補：3個l，2個2，5個3這十個數字能構成多少個4位數偶數。解 問題是求多重集S3個1，2個2，5個3的4排列數，且要求排列的末尾為2（偶數）。可以把問題轉化成求多重集S3個1，1個2，5個3,其指數生成函數為展開后得的系數為20，所以能組成20個4位數的偶數。習題六6.1 設，建立的遞推關系并求解。解：6.2 求解遞推關系：（1）解：（2）解：（3）解：（4）解：6.3 求解遞推關系：（1）解：（2）解：（3）解：（4）解：6.4 求解遞推關系：（1）（2）（3）（4）6.5 平面上有n條直線，它們兩兩相交且沿有三線交于一點，設這n條直線把平面分成個區域，求的遞推關系并求解.解：設n-1條直線把平面分成個區域，則第n