《組合數(shù)學》測試題含答案.doc

《《組合數(shù)學》測試題含答案.doc》由會員分享，可在線閱讀，更多相關《《組合數(shù)學》測試題含答案.doc（35頁珍藏版）》請在裝配圖網(wǎng)上搜索。

測 試 題 ——組合數(shù)學 一、選擇題 1. 把101本書分給10名學生，則下列說法正確的是（） A.有一名學生分得11本書 B.至少有一名學生分得11本書 C.至多有一名學生分得11本書 D.有一名學生分得至少11本書 2. 8人排隊上車，其中A，B兩人之間恰好有4人，則不同的排列方法是（） A. B. C. D. 3. 10名嘉賓和4名領導站成一排參加剪彩，其中領導不能相鄰，則站位方法總數(shù)為（） A. B. C. D. 4. 把10個人分成兩組，每組5人，共有多少種方法（） A. B. C. D. 5. 設x,y均為正整數(shù)且，則這樣的有序數(shù)對共有（）個 A.190 B.200 C.210 D.220 6. 僅由數(shù)字1，2，3組成的七位數(shù)中，相鄰數(shù)字均不相同的七位數(shù)的個數(shù)是（） A.128 B.252 C.343 D.192 7. 百位數(shù)字不是1且各位數(shù)字互異的三位數(shù)的個數(shù)為（） A.576 B.504 C.720 D.336 8. 設n為正整數(shù)，則等于（） A. B. C. D. 9. 設n為正整數(shù)，則的值是（） A. B. C. D.0 10. 設n為正整數(shù)，則當時，=() A. B. C. D. 11. 中的系數(shù)是（） A.1440 B.-1440 C.0 D.1 12. 在1和之間只由數(shù)字1，2或3構成的整數(shù)個數(shù)為（） A. B. C. D. 13. 在1和300之間的整數(shù)中能被3或5整除的整數(shù)共有（）個 A.100 B.120 C.140 D.160 14. 已知是Fibonacci數(shù)列且，則（） A.89 B.110 C.144 D.288 15. 遞推關系的特征方程是（） A. B. C. D. 16. 已知，則當時，（） A. B. C. D. 17. 遞推關系的解為（） A. B. C. D. 18. 設，則數(shù)列的常生成函數(shù)是（） A. B. C. D. 19. 把15個相同的足球分給4個人，使得每人至少分得3個足球，不同的分法共有（）種 A.45 B.36 C.28 D.20 20. 多重集的5-排列數(shù)為（） A.5 B.10 C.15 D.20 21. 部分數(shù)為3且沒有等于1的部分的15-分拆的個數(shù)為（） A.10 B.11 C.12 D.13 22. 設n,k都是正整數(shù)，以表示部分數(shù)為k的n-分拆的個數(shù)，則的值是（） A.6 B.7 C.8 D.9 23. 設A，B，C是實數(shù)且對任意正整數(shù)n都有，則B的值是（） A.9 B.8 C.7 D.6 24. 不定方程的正整數(shù)解的個數(shù)是（） A.26 B.28 C.30 D.32 25. 已知數(shù)列的指數(shù)生成函數(shù)是，則該數(shù)列的通項公式是（） A. B. C. D. 二、填空題 1. 在1和2000之間能被6整除但不能被15整除的正整數(shù)共有_________個 2. 用紅、黃、藍、黑4種顏色去圖棋盤，每個方格涂一種顏色，則使得被涂成紅色的方格數(shù)是奇數(shù)的涂色方法共有_______種 3. 已知遞歸推關系的一個特征根為2，則其通解為___________ 4. 把個人分到3個不同的房間，每個房間至少1人的分法數(shù)為__________ 5. 棋盤的車多項式為___________ 6. 由5個字母a,b,c,d,e作成的6次齊次式最多可以有_________個不同類的項。 7. =_____________________ 8. 求由2個0，3個1和3個2作成的八位數(shù)的個數(shù)______________ 9.含3個變元x, y, z的一個對稱多項式包含9個項，其中4項包含x,2項包含,1項是常數(shù)項，則包含的項數(shù)為____________ 10．已知是n的3次多項式且,,,,則____________ 11. 已表示把n元集劃分成k個元素個數(shù)均不小于2的子集的不同方法數(shù)， 則=___________ 12.部分數(shù)為3且沒有等于k的部分的n-分拆數(shù)________________ 13. 把24顆糖分成5堆，每堆至少有3顆糖，則有___________種分法 三、計算題 1．在1000至9999之間有多少個數(shù)字不同的奇數(shù)？ 2、以3種不同的長度，8種不同的顏色和4種不同的直徑生產粉筆，試問總共有多少種不同種類的粉筆？ 3、至多使用4位數(shù)字可以寫成多少個2進制數(shù)！（2進制數(shù)只能用符號0或1） 4、由字母表L={a,b,c,d,e}中字母組成的不同字母且長度為4的字符串有多少個？如果允許字母重復出現(xiàn)，則由L中字母組成的長度為3的字符串有多少個？ 5、從{1，2，3……9}中選取不同的數(shù)字且使5和6不相鄰的7位數(shù)有多少？ 6、已知平面上任3點不共線的25個點，它們能確定多少條直線？能確定多少個三角形？ 7、計算數(shù)字為1，2，3，4，5且滿足以下兩個性質的4位數(shù)的個數(shù)： (a)數(shù)字全不相同； (b)數(shù)為偶數(shù) 8、正整數(shù)7715785有多少個不同的正因子（1除外）？ 9、50！中有多少個0在結尾處？ 10、比5400大并且只有下列性質的數(shù)有多少？ (a)數(shù)字全不相同； (b)不出現(xiàn)數(shù)字2和7 11. 將m=3761寫成階乘和的形式。 12. 根據(jù)序數(shù)生成的排列(p)=(3214)，其序號是多少？ 13. 如果用序數(shù)法對5個文字排列編號，則序號為117的排列是多少？ 14. 設中介數(shù)序列為（120），向它所對應的4個文字的全排列是什么？ 15. 按字典序給出所有3個文字的全排列。 16. 按遞歸生成算法，依次寫出所有的4個文字的全排列。 17. 根據(jù)鄰位互換生成算法，4個文字的排列4231的下一個排列是什不同的方案? 18. 有5件不同的工作任務，由4個人去完成它們，每件工作只能由一個人完成，問有多少種方式完成所有這5件工作？ 19. 有紀念章4枚，紀念冊6本，分送給十位同學，問有多少種分法？如限制每人得一件物品，則又有多少種分法？ 20．寫出按次序產生的所有從1，2，3，4，5，6中任取2個的組合。 21．給定一個n邊形，能畫出多少個三角形使得三角形的頂點為n邊形的頂點，三角形的邊為n邊形的對角線（不是邊）？ 22．試問（x+y+z）的6次方中有多少不同的項？ 23. 如果沒有兩個相鄰的數(shù)在同一個集合里，由{1，2，…20}中的數(shù)可形成3個數(shù)的集合有多少？ 24. 試列出重集{2a,1b,3c}的所有3組合和4組合。 25. 設{Fn}為fibonna序列，求出使Fn = n的所有的n。 26. 試求從1到1000中,不能被4,5或6整除的個數(shù)? 27. 計算12+22+……+n2 28. 設某地的街道把城市分割成矩形方格，每個方格叫它塊，某甲從家里出發(fā)上班，向東要走過7塊，向北要走過5塊，問某甲上班的路經(jīng)有多少條？ 29. 設n=253273114,試求能除盡數(shù)n的正整數(shù)的數(shù)目。 30. 求（1+x4+x8）10 中x20項的系數(shù)。 31. 試給出3個文字的對稱群S3中的所有元素，并說出各個元素的格式。 32. 有一BIBD，已知b=14,k=3,λ=2,求v和r。 33. 將39寫成∑ai i!(0≤ai≤i)的形式。 34. 8個人圍坐一圈，問有多少種不同的坐法？ 35. 求 36. 試給出兩個正交的7階拉丁方。 37. 在3n+1個球中，有n個相同，求從這3n+1個球中選取n個的方案數(shù)。 38. 用紅、黃兩種顏色為一個等邊三角形的三個頂點著色，問有多少種實質不同的著色方案？ 39. 在r,s,t,u,v,w,x,y,z的排列中，求y居x和z中間的排列數(shù)。 40. 求1040和2030的公因數(shù)數(shù)目。 41. 求1到1000中不被5和7整除，但被3整除的數(shù)的數(shù)目。 42. 求的和。 43. 用母函數(shù)法求遞推關系的解，已知a0=0,a1=1。 44. 試求由a,b,c這3個文字組成的n位符號串中不出現(xiàn)aa圖像的符號串的數(shù)目。 45. 26個英文小寫字母進行排列，要求x和y之間有5個字母的排列數(shù)。 46. 8個盒子排成一列，5個有標志的球放到盒子里，每個盒子最多放一個球，要求空盒不相鄰，問有多少種排列方案？ 47. 有紅、黃、藍、白球各兩個，綠、紫、黑球各3個，從中取出6個球，試問有多少種不同的取法。 48. 用b、r、g這三種顏色的5顆珠子鑲成的圓環(huán)，共有幾種不同的方案？ 49. n個完全一樣的球放到r（n≥r）個有標志的盒中，無一空盒，試問有多少種方案？ 50. 假設某個凸n邊形的任意三條對角線不共點，試求這凸n邊形的對角線交于多少個點？ 51. 求從k個不同文字中取n個文字作允許重復的排列，但不允許一個文字連續(xù)出現(xiàn)3次，求這樣的排列的數(shù)目。 52. 求下圖中從A點出發(fā)到n點的路徑數(shù)。 53. n條直線將平面分成多少個區(qū)域？假設無三線共點，且兩兩相交。 54. 四位十進制數(shù)a b c d，試求滿足a+b+c+d=31的數(shù)的數(shù)目。 55. 兩名教師分別對6名學生面試，每位教師各負責一門課，每名學生面試時間固定，6名學生面試時間定于下周一的第1節(jié)至第6節(jié)課，兩門課的面試分別在901和902兩個教室進行。試問共有多少種面試的順序。 56. 對正六角形的6個頂點用5種顏色進行染色，試問有多少種不同的方案？旋轉或翻轉使之重合的視為相同的方案。 58. 生成矩陣 試求相應的校驗矩陣H。 59. 由m個0，n個1組成的n+m位符號串，其中n≤m+1,試求不存在兩個1相鄰的符號串的數(shù)目。 60. n個男人與n個女人沿一圓桌坐下，問兩個女人之間坐一個男人的方案數(shù)，又m個女人n個男人，且m2)，則 其中α=（1+√5）/2，β=（1-√5）/2 8. N個代表參加會議，試證其中至少有兩個人各自的朋友數(shù)相等。 9. 證明： 10. 證明：是整數(shù)。 11. 證明：在邊長為1的等邊三角形內任取5點，試證至少有兩點的距離小于1/2。 12.證明： 其中定義為：， 13. 任取11個整數(shù)，求證其中至少有兩個數(shù)它們的差是10的倍數(shù)。 14. 在邊長為1的正方形內任取5點，試證其中至少有兩點，其間距離小于。 15. 若H是群G的子群，試證：|xH|=K, 其中K＝|H|，x∈G。 16. 二維空間的點（x,y）的坐標x和y都是整數(shù)的點稱為格點。任意5個格點的集合A，試證A中至少存在兩個點，它們的中點也是格點。 17. 證明：在由字母表{0，1，2}生成的長度為n的字符串中，0出現(xiàn)偶數(shù)次的字符串有（3n+1）/2個。 18. 試證任意r個相鄰的正整數(shù)的連乘積（n+1）(n+2)…(n+r)必被r!除盡。 19. 證明： 20. 證明 21. 任取5個整數(shù)，試求其中必存在3個數(shù)，其和能被3整除。 22. 若H是群G的子群，x和y 是G的元素。試證xH∩yH或為空集，或xH=yH. 23. 令S={1，2，…，n+1},n≥2, 試證：。 24. 證明：任何K個相繼的正整數(shù)之積，必是r的倍數(shù)，其中r=1，2，…，K。 25. 求證：=。 26. 使用二項式定理證明,試推廣到任意實數(shù)r，求。 27. 證明 28. 證明任何k個相繼正整數(shù)中，有一個必能被k整除。 29. 證明在小于或等于2n的任意n+1個不同的正整數(shù)中，必有兩個是互等的。 30. 證任一正整數(shù)n可唯一地表成如下形式:,0≤ai≤i,i＝1,2,…。 31. 對于給定的正整數(shù)n,證明當 時，是最大值。 32. 證明在由字母表{0,1,2}生成的長度為n的字符串中,0出現(xiàn)偶數(shù)次的字符串有個； 33. 設有三個7位的二進制數(shù)：，，。試證存在整數(shù)i和j，，使得下列之一必定成立，。 34.證明：在n階幻方中將每個數(shù)碼a換成，所得的陣列仍是一個n階幻方。（注：所謂幻方是指一個方陣，其中的元素分別是，且每列的元素和均相等） 35.證明：把有n個元素的集合s劃分為k個有序集合的個數(shù)等于 36.試證明： 37.證明：如果在邊長為1的等邊三角形內任取10個點，則必有2個點，它們的距離不大于1/3。 測 試 題 答 案 ——組合數(shù)學 一、選擇題 1.D 2.C 3.A 4.C 5.A 6.D 7.A 8.B 9.C 10.C 11.B 12.C 13.C 14.A 15.C 16.B 17.D 18.A 19.D 20.C 21.C 22.B 23.D 24.B 25.D 二、填空題 1. 267 2. 3. 4. 5. 6. 210 7. 0 8. 420 9. 2 10. 11. 12. 13. 23 三、計算題 1、 在1000至9999之間的數(shù)都是4位數(shù)。我們可以先選個位，再選千位，百位和十位。因為我們要的數(shù)是奇數(shù)，所以個位數(shù)字可以是1，3，5，7，9中的任何一個，即有5種選擇。選定個位數(shù)之后，十位就只有8種選擇了。百位也只有8種選擇，而十位則只有7種選擇，因此應用乘法原則，問題的答案是5887=2240種。 2、 在這個問題中，我們要計算的是組合數(shù)，因為粉筆的特性與上面三種數(shù)的順序無關，利用乘法法則可知共有384=96種不同種類的粉筆。 3、 因為2進制數(shù)必須考慮其數(shù)字的次序，故要計算的是排列問題。有4種選擇要做，并且每種都可以獨立地選擇0或1，于是有2222=24=16種至多4位數(shù)字的2進制數(shù)，它們分別是{0，1，10，11，100，101，111，1000，1001，1010，1011，1100，1101，1110，1111} 4、 從5個字母中選取4個組成的字符串共有p(5,4)=5432=120種。如果允許字母重復出現(xiàn)，則長度為3的字符串共有555=125種。 5、 可以這樣考慮：在9個數(shù)字中不重復地選取7個作排列共有種，其中出現(xiàn)5和6相鄰的排列數(shù)共有種，因為出現(xiàn)5和6相鄰的排列可看成是從1，2，3，4，7，8，9七個數(shù)中選5個排列后，將56或65插入到這5個數(shù)的6個間隔位置上（數(shù)前、數(shù)后及兩個數(shù)字之間的間隔共6個位置），所以包含相鄰的5和6的7位數(shù)共有，于是所求數(shù)的個數(shù)為。 6、 因為任3點均不共線，所以25個點中每兩個點組成一條直線，每3個點了構成一個三角形，所以共有條直線和個三角形。 7、 因為所求的數(shù)為偶數(shù)，所以個位只有2種選擇：2或4。因為4位數(shù)字全不相同，所以乘余3位數(shù)只能是1，2，3，4，5中去掉用于個位數(shù)的數(shù)字之后的4個數(shù)字的3排列，可是共有2P(4,3)=24個這樣的數(shù)。 8、 因為，所以共有個不同的正因子 9、因為在1到50中共有10個數(shù)含有因子5而這10個數(shù)中又有2個包含有因子25。因此50！中含有10+2=12個5因子，顯然50！中至少含有12個因子2，因為在1到50這50個數(shù)中有25個是偶數(shù)所以50！中含有12個因子10，即50！在結尾處有12個0。 10、符合條件的數(shù)可分成以下幾類： （1）8位數(shù)：共有7P（7，7）=35280個 （2）7位數(shù)：共有7P（7，6）=35280個 （3）6位數(shù)：共有7P（7，5）=17640個 （4）5位數(shù)：共有7P（7，4）=5880個 （5）4位數(shù)：8位數(shù)>5的有3P（7，3）=630個 8位數(shù)=5，百位數(shù)>4的有4P（6，2）=120個 8位數(shù)=5，百位數(shù)=4的有P（6，2）=30個 所以符合條件的數(shù)共有94860個 11. 3761 =56!+5!+4!+23!+2!+1 12. 因為和(p)=(3214)對應的中介數(shù)是（021），所以（p）的序號為m=03!+22!+1=5,即(p)是第5個排列 13. 因為117=44!+33!+2!+1，則中介數(shù)為（4311），所以序號為117的5個文字的全排列為54231。 14. 因為a1=0,所以2在1的右邊，a2=2，所以3在1和2的左邊,a3=1，所以4在2的前面且在3和1的后面，因此所對應的排列為3142。 15. 123，132，213，231，312，321 16. 1234 1243 1423 4123 1324 1342 1432 4132 3124 3142 3412 4312 2134 2143 2413 4213 2314 2341 2431 4231 3214 3241 3421 4321 17. 排列4231的下一個排列是4213。 18. 因為5件工作中的每一件工作都可由4個人中的任一人完成，因此每件工作有4種分配方法，所以總共有44444=1024種完成任務的方案。 19. 因為沒有限制一個同學可得紀念章和紀念冊的個數(shù)，所以將4枚紀念章分給十個同學的方法有C（10+4-1,4）=C(13,4),將6本紀念冊分給十個同學的方法有C（10+6-1，6）=C（15，6），所以若有C（13，4）、C（15，6）種方案。 20. 如果限制每人得1件物品，則共有10！/（4！6?。?2，13，14，15，16，23，24，25， 26，34，35，36，45，46，56 21. 因為n邊形的每個頂點有n-3條對角線，要使另一邊也是對角線，則選中的兩條對角線不能相鄰，于是相當于在n-4條對角線中選2條對角線作三角形的兩邊，另一條邊即為此二對角線頂點的連線。所以共有C(n-4,2)個這樣的三角形，有n個頂點，共有nc(n-4,2)個三角形。但這里有重復，因為每一個滿足條件的三角形在三個頂點處重復了3次，所以真正不同的三角形只有nc(n-4,2)/3.例如，6邊形中可以找出6c(2,2)/3=2個這樣的三角形。 22. 共有C（3+6-1,6）=C(8,6)=C(8,2)=28項。 23. 因為可以在{1,2,…,18}中任取3個的組合同在{1,2,…,20}中任取3個沒有相鄰的數(shù)組成的集合之間建立起一一對應關系,所以答案是C(18,3)=816 24. {c,c,c},{b,c,c},{a,c,c},{a,b,c},{a,a,c},{a,a,b}，共6個3組合， {a,c ,c,c},{b,c,c,c},{a,b,c,c},{a,a,c,c},{a,a,b,c}共5個4組合。 25. F1 = 1, F 5 = 5 26. 因為能被4整除的有10000/4=2500，能被5整除的有1000/5=2000，能被6整除的有10000/6=1666，能同時被4，5整除的有10000/20=500，能同時被4，6整除的有10000/24=416，能同時被5，6整除的有10000/30=333，能同時被4，5，6整除的有10000/120=83，所以符合要求的有10000-（2500+2000+1666）+（500+416+333）-83=5000（個） 27. 因為k2=2C(k,2)+C(k,1)=2k(k－1)/2+k= k2 所以12+22+……+n2=2(C(1,2)+C(2,2)+……+C(n,2))+C(1,1)+C(2,1)+……+C(n,1) =2C(n+1,3)+C(n+1,2) =2(n+1)n(n－1)/(32)+(n+1)n/2 =n(n+1)(2n+1)/6 28. N=C(7+5,7)=C(7+5,5)=C(12,5)=792 一般情況 N=C(m+n,n) 29. N=(1+5)(1+2)(1+3)(1+4)=360 30. 令x4=y, 則x8=y2, x20=y5,于是（1+y+y2）10中y5項的系數(shù)N即為(1+x4+x8)10中x20項的系數(shù)，而y5=y?yyyy=yyyy2=yy2y2，于是 N=C(10,5)+c(10,3)c(7,1)+c(10,1) c(9,2)=1326 31 S3={(1)(2)(3),(23),(12),(13),(123),(132)} (1)(2)(3)的格式是(1)3 (23),(12),(13)的格式是(1)1(2)2 (123),(132)的格式是(3)1 32 因為bk=vr , r(k-1)=λ(v-1),已知 b=14,k=3,λ=2 所以 143=vr 即時 vr=42 求得 v=7 r(3-1)=2(v-1) 2r=2(v-1) r=6 33. 39=4!+2?3!+2!+1!=24+12+2+1 34. N=7!=5040 35. 因為C(n,1)+2C(n,2)+…+nC(n,n)=n?2n-1 所以C(10,1)+2C(10,2)+…+10C(10,10)=10?210-1=5120 36. 和 37. N=C(2n+1,0)+C(2n+1,1)+…+C(2n+1,2)+…+C(2n+1,n) =2(C(2n+1,0)+C(2n+1,1)+…+C(2n+1,n))/2 =(C(2n+1,0)+C(2n+1,2n+1)+C(2n+1,1)+C(2n+1,2n)+… +C(2n+1,n)+C(2n+1,n+1))/2 =22n+1/2=22n=4n 38. N=(23+2??????21+3???22)/6=4 39. 解：N=2?7！=10080 40. 解：∵M=gcd(1040,2030)=240?530,∴N=(40+1)(30+1)=1271 41. 解：N=int(1000/3)-int(1000/15)-int(1000/21)+int(1000/105)=333-66-47+9=229 42. 解： ∵ △Sn=Sn+1-Sn=(n+1)4 ∴可設Sn=A?C(n,0)+B?C(n,1)+C?C(n,2)+D?C(n,3)+E?C(n,4)+F???C(n,5),于是可知： A=0 解得： A=0 A+B=1 B=1 A+2B+C=17 c=15 A+3B+3C+D=98 D=50 A+4B+6C+4D+E=354 E=60 A+5B+10C+10D+5E+F=979 F=24 所以 Sn=C(n,1)+15C(n,2)+50C(n,3)+60C(n,4)+24C(n,5) =(n(n+1)(2n+1)(3n2+3n-1))/30 43．解：特征函數(shù)為x2-6x+8=0,x1=2,x2=4,所以可設 an=A?2n+B?4n,于是 a0=0=A+B 解得 A=-1/2 a1=1=2A+4B B=1/2 即an=(4n-2n)/2 44．解：設an為n位符號串中不出現(xiàn)aa圖像的符號串的個數(shù)， 則an=2an-1+2an-2,即 an－2an-1－2an-2＝０，a1=3,a2=8，由此知 a0=1。 特征方程為x2-2x-2=0, x1=1+√3 , x2=1-√3 ，可設 an=A(1+√3)n+B(1-√3)n,于是有 a0 = 1 =Ａ＋Ｂ a1 = 3 = (1+√3)A+ (1-√3)B 解此方程組得 Ａ=(３＋2√3)/6 B=(３-2√3)/6 an=[(３＋2√3)(1+√3)n+(３-2√3)(1-√3)n]/6 45．解：M=2?20! ?5! ?C(24,5)=40?24! 46. 解：如圖_0_0_0_0_0_ ,3個空盒可插在兩個球之間,共有C(6,3)=20種方案,5個有標志的球共有5!種排序,所以總計有M=20?5!=2400種排列方案。 47. 解：母函數(shù)為G(x)= (1+x+x2)4(1+x+x2+x3)3,其中x6的系數(shù)為 M=1?10+4?12+10?12+16?10+19?6+16?3+10?1=510,因為 G(x)= (1+4x+10x2+16x3+19x4+16x5+10x6+4x7+x8) 48. 解：運動群G={(1)(2)(3)(4)(5),(1 2 3 4 5),(1 3 5 2 4),(1 4 2 5 3), (1 5 4 3 2 ), (1)(25)(34), (2)(13)(45), (3)(24)(15), (4)(35)(12), (5)(14)(23)}={ p1,p2,p3,p4,p5,p6,p7,p8,p9,p10} c( p1)=5, c(p2)=c(p3)= c(p4)=c(p5)=1, c(p6)=c(p7)= c(p8)= c(p9)= c(p10)=3, m=3, |G|=10,據(jù)Plya定理,M=(1/|G|)?(mc(p1)+ mc(p2)+ mc(p3)+。。。+ mc(p10))=(1/10)（35+4?31+5?33） =(1/10)（243+12+45）=30。 49．Ｃ（ｎ－１，ｒ－１） 將ｎ個球排成一行，兩球之間有一間隔，共有ｎ－１個間隔。在此ｎ－１個間隔中任?。颍眰€，將ｎ個球分成ｒ段，將第ｉ段的球（其中至少有１球）放入第ｉ個盒子，所以共有Ｃ（ｎ－１，ｒ－１）種方案。 50. Ｃ（ｎ，４） 凸ｎ邊形有ｎ個頂點，任取其中４個頂點可以組成一個凸４邊形，該４邊形的兩條對角線有一個交點，所以凸ｎ邊形的對角線交于Ｃ（ｎ，４）個交點（根據(jù)假設，沒有３條對角線相交于一點）。 51. Ｓｎ＝ｎ（ｎ＋１）（ｎ＋２）（ｎ＋３）／４ Ｓｎ＝１２３＋２３４＋．．．＋ｎ（ｎ＋１）（ｎ＋２） ?。剑常。ǎ保玻常常。玻常矗常。睿ǎ睿保ǎ睿玻常。? ?。剑常。ǎ茫ǎ?，３）＋Ｃ（４，３）＋．．．＋Ｃ（ｎ＋２，３）） ?。剑常。ǎ茫ǎ?，０）＋Ｃ（４，１）＋．．．＋Ｃ（ｎ＋２，ｎ－１）） ?。剑常。茫ǎ睿?，ｎ－１） ?。剑常。茫ǎ睿?，４） 　＝ｎ（ｎ＋１）（ｎ＋２）（ｎ＋３）／４ 52. ａｎ＝（ｋ／（２（ｋ－１））＋ｋ／（２ｓｑｒｔ（（ｋ－１）（ｋ＋３））） 　　　　?。ǎǎ耄保螅瘢颍簦ǎǎ耄保ǎ耄常玻? 　　　　＋（ｋ／（２（ｋ－１））－ｋ／（２ｓｑｒｔ（（ｋ－１）（ｋ＋３））） 　　　　?。ǎǎ耄保螅瘢颍簦ǎǎ耄保ǎ耄常玻? 假設從ｋ（ｋ＞１）個不同文字取出ｎ個（可以重復）作排列，但不允許一個文字連續(xù)出現(xiàn)３次的排列所組成的集合為Ａｎ，則所求排列數(shù)ａｎ＝｜Ａｎ｜。將Ａｎ中的字符串按最后一個文字可以分成兩類：一類是最后一個文字同其前一個文字不相同的那些字符串，共有（ｋ－１）ａｎ－１個（最后一位有ｋ－１種選擇，而前ｎ－１位是沒有一個文字連續(xù)出現(xiàn)３次的字符串），另一類是最后兩個文字相同，但與倒數(shù)第３個文字不相同的字符串，共有（ｋ－１）ａｎ－２個，所以有遞推關系 ａｎ＝（ｋ－１）ａｎ－１＋（ｋ－１）ａｎ－２（ 而ａ１＝ｋ，ａ２＝ｋ２，ａ３＝ｋ３－ｋ＝ｋ（ｋ－１）（ｋ＋１ 遞推關系的特征方程為 　?。玻ǎ耄保ǎ耄保剑? 其根為： 　　α１＝（ｋ－１＋ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２ 　　α２＝（ｋ－１－ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２ 于是知　?。幔睿剑粒宝粒保睿粒拨粒玻? 由于ａ１＝ｋ，ａ２＝ｋ２，由遞推關系知ａ０＝ｋ／（ｋ－１），所以 ａ０＝ｋ／（ｋ－１）＝Ａ１α１０＋Ａ２α２０Ａ＝Ａ１＋Ａ２ ａ１＝ｋ＝Ａ１α１１＋Ａ２α２１＝Ａ１（ｋ－１＋ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２ 　　　　　　　　　　　?。粒玻ǎ耄保螅瘢颍簦ǎǎ耄保ǎ耄常? 解得 Ａ１＝（ｋ／（２（ｋ－１））＋ｋ／（２ｓｑｒｔ（（ｋ－１）（ｋ＋３））） Ａ２＝（ｋ／（２（ｋ－１））－ｋ／（２ｓｑｒｔ（（ｋ－１）（ｋ＋３））） 所以 ａｎ＝（ｋ／（２（ｋ－１））＋ｋ／（２ｓｑｒｔ（（ｋ－１）（ｋ＋３））） 　　　　　（（ｋ－１＋ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２）ｎ 　　　?。ǎ耄ǎ玻ǎ耄保耄ǎ玻螅瘢颍簦ǎǎ耄保ǎ耄常? 　　　　?。ǎǎ耄保螅瘢颍簦ǎǎ耄保ǎ耄常玻? 53. f（n）＝（（（１＋√５）／２）n＋1－（（１－√５）／２）n＋1）／√５ 假設從A（編號為０）到編號為i的頂點有f（i）條路徑，則f（１）＝１，f（２）＝２，當i＞2時，f（i）＝f（i-1）＋f（i－2），由此知f（０）＝f（A）＝１。當i＝n時，f（n）＝f（n-1）＋f（n－2）,即f（n）－f（n-1）－f（n－2）＝０。其特征方程為： x2－x－1=0，它的兩個根分別為：α１＝（１＋√５）／２，α２＝（１－√５）／２。 于是知f（n）＝Ａ１α１ｎ＋Ａ２α２ｎ，根據(jù) f（０）＝１＝A1＋A2 f（１）＝１＝A1（１＋√５）／２＋A2（１－√５）／２， 解得 　　 A1＝（１＋√５）／（２√５），A2＝（１－√５）／（２√５） 所以， f（n）＝（（（１＋√５）／２）n＋1－（（１－√５）／２）n＋1）／√５＝F（n＋1） 其中F（n）為第n個Fibonacci數(shù)。 54. an＝（n2＋n＋２）／２ 設n條符合條件的直線將平面分成an個區(qū)域，那么n－１條直線可將平面分成an－１個區(qū)域，而第n條直線與前n-1條直線均相交，有n－１個交點，因此第n條直線被分成n段，而每一段對應一個新增的區(qū)域，所以有an＝an－１＋n，即an－an－１＝n。于是 an－１－an－２＝n－１，由此得an－２an－１＋an－２＝１，同樣有an－１－２an－２＋an－３＝１，故得an－３an－１＋３an－２－an－３＝０，其特征方程為x3－３x2＋３x－1＝０，解此方程得α＝α１＝α２＝α３＝１，所以an＝（A0＋A1n＋A2n2）αn＝A0＋A1n＋A2n2 ，而 a0＝１＝A0　　　　　　　　　　　　　　　　　　　　 a1＝２＝A0＋A1＋A2 a２＝４＝A0＋２A1＋４A2 　　　　解得 　　　　A0=1 A1=1/2 A2=1/2 由此知 an＝（n2＋n＋２）／２ 55、56 因為x1＋x2＋x3＋x４＝31,xi≥0（i＝１，２，３，４）的整數(shù)解共有C（4+31-1，31）＝C（34，３）＝343332/6＝5984（個）。 再考慮x1＋x2＋x3＋x４＝31,xi≥１0（i＝１，２，３，４）的整數(shù)解的個數(shù)。令N為全體非負整數(shù)解，則｜N｜＝5984。 令Ai(i＝１，２，３，４)為其中xi≥１0的解集合。則｜A1｜即為（x1＋10）＋x2＋x3＋x４＝31，也就是x1＋x2＋x3＋x４＝21的非負整數(shù)解的個數(shù)。所以， ｜A1｜＝C（４＋21－１，21）＝C（24，3）＝242322/6＝2024。同理可知 ｜A２｜＝｜A３｜＝｜A４｜＝｜A1｜＝2024。類似地， ｜Ai∩Aj｜＝C（4＋11－１,11）＝C（14，3）＝141312/6＝364（１≤i120，所以n1或n2中必有一數(shù)∈{2，3，5，7}。 設A1表示S中能被2整除的數(shù)，則| A1|=int（120/2）=60（int（x）表示不超過x的最大整數(shù)）， 設A2表示S中能被3整除的數(shù)，則| A2|=int（120/3）=40， 設A3表示S中能被5整除的數(shù)，則| A3|=int（120/5）=24， 設A4表示S中能被7整除的數(shù)，則| A4|=int（120/7）=17， 而且， | A1 ∩A2|=20，| A1 ∩A3|=12，| A1 ∩A4|=8， | A2 ∩A3|=8，| A2 ∩A4|=5，| A3 ∩A4|=3， | A1 ∩A2 ∩A3|=4，| A1 ∩A2 ∩A4|=2，| A1 ∩A3 ∩A4|=1，| A2 ∩A3 ∩A4|=1， | A1 ∩A2 ∩A3 ∩A4|=0， 所以，根據(jù)容斥原理知，S中既不是2、3、5的倍數(shù)，也不是7的倍數(shù)的個數(shù)共有 120-（60+40+24+17）+（20+12+8+8+5+3）-（4+2+1+1）+0=176-149=27 但是，這27個數(shù)中包含了1，它不是素數(shù)，卻沒有包含2、3、5、7，所以，1至120之間的素數(shù)共有27-1+4=30個。 64．因為A4={（1）（2）（3）（4），（123），（124），（132），（134），（142），（143），（234）， （243），（12）（34），（13）（24），（14）（23）}，它共有12個置換，其中 格式為（1）4的有1個：（1）（2）（3）（4）， 格式為（1）1（3）1的有8個：（123），（124），（132），（134），（142），（143），（234），（243）， 格式為（2）2的有3個：（12）（34），（13）（24），（14）（23） 65． (a) w1=(1111)G=(1111111) (b) w2=(1000)G=(1000011) (c) w3=(0001)G=(0001111) (d) w4=(1101)G=(1101001) 66．（n-2）2n-1+1 從n個不相同的數(shù)a1，a2，. . . ，an中取出r（r=2，3，. . . ，n）個,將這r個數(shù)從小到大排序：ai1≤ai2≤. . . ≤air。將這r個數(shù)分成前后兩部分，使每一部分非空，共有r-1種分法。前面部分形成第2組，后面部分形成第1組，則第1組中的最小數(shù)大于第2組中的最大數(shù)。所以滿足條件的取法共有 r=2∑nC（n，r）（r-1）= r=2∑nrC（n，r）- r=2∑nC（n，r） =（ r=1∑nrC（n，r）-C（n，1））-（r=0∑nC（n，r）- C（n，1）- C（n，0）） =（n2n-1-n）-（2n-n-1）=（n-2）2n-1+1 67. 解 根據(jù)題設，無論選哪一名，有26種可能結果；余下選一名只有25種可能結果；最后選一名就只有24種可能結果。由于同時選出三名，所以由積的法則知，共有262524=15600種選法。 68. 解 （1）這100個數(shù)的前7個數(shù)，任選取兩個數(shù)的差不可能等于7，只有100－7=9