《組合數(shù)學(xué)》測試題含標(biāo)準(zhǔn)答案

《《組合數(shù)學(xué)》測試題含標(biāo)準(zhǔn)答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《《組合數(shù)學(xué)》測試題含標(biāo)準(zhǔn)答案（41頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、組合數(shù)學(xué)測試題含答案作者:日期:測試題組合數(shù)學(xué)一、選擇題1 .把101本書分給10名學(xué)生，則下列說法正確的是（）A.有一名學(xué)生分得11本書B.至少有一名學(xué)生分得 11本書C.至多有一名學(xué)生分得 11本書 D.有一名學(xué)生分得至少 11本書2 . 8人排隊(duì)上車，其中 A, B兩人之間恰好有4人，則不同的排列方法是（）A. 3 6! B. 4 6! C. 6 6!D. 8 6!3 . 10名嘉賓和4名領(lǐng)導(dǎo)站成一排參加剪彩，其中領(lǐng)導(dǎo)不能相鄰，則站位方法總數(shù)為（）A.10! P 11,4B. 10! P 9,4C. 10! P 10,4D. 14! 3!4 .把10個(gè)人分成兩組，每組 5人，共有多少種方

2、法（）10A.510 10B.559C.499D.445 .設(shè)x,y均為正整數(shù)且x y 20,則這樣的有序數(shù)對(duì)x, y共有（）個(gè)A.190B.200C.210D.2206 .僅由數(shù)字1, 2, 3組成的七位數(shù)中，相鄰數(shù)字均不相同的七位數(shù)的個(gè)數(shù)是（）A.128B.252C.343D.1927 .百位數(shù)字不是1且各位數(shù)字互異的三位數(shù)的個(gè)數(shù)為（）A.576B.504C.720n n 8 .設(shè)n為正整數(shù)，則等于（）k 0 2kD.336A. 2n B. 2n 1nn 1C. n 2 D. n 2n9.設(shè)n為正整數(shù)，則k 0k1 n 3k的值是（）knnA. 2 B. 2nC. 2D.010.設(shè)n為正整

3、數(shù)，則當(dāng)n 2時(shí)， k =（）k2 k 2nA.3n 1B.2n 1C.3D.11. 2xi6 ,3X2 X3 中3x1x2x32的系數(shù)是A.1440B.-1440C.0D.112.在1和106之間只由數(shù)字1 , 2或3構(gòu)成的整數(shù)個(gè)數(shù)為（）36 136 3A. -B. -C.7D.二213.在1和300之間的整數(shù)中能被3或5整除的整數(shù)共有（）個(gè)A.100B.120C.140D.16014.已知o是Fibonacci數(shù)列且21, f 834,則 f 10()A.89B.110C.144D.28815.遞推關(guān)系an3an14an 3的特征方程是A. X23xB.3xC. X33x2D.3x216.

4、已知anQ1,2,2 時(shí)，an ()A. 3an2anB.3a n 12an 2C. 3an 12anD.3an 12an 217.遞推關(guān)系an2an11的解為a0A. an2nB. an1 2n 2C. an2nD. an18.設(shè) an5 2nn 0,1,2,ann 0的常生成函數(shù)是（）5A.1 2xB.一152x 2C.51 2xD. 5 12x 219.把15個(gè)相同的足球分給 4個(gè)人，使得每人至少分得3個(gè)足球，不同的分法共有（）種A.45B.36C.28D.2020.多重集S 2 a,4 b的5-排列數(shù)為（）A.521.部分?jǐn)?shù)為A.10B.103且沒有等號(hào)B.11C.15D.201的部分

5、的15-分拆的個(gè)數(shù)為（）C.12D.1322.設(shè)n,k都是正整數(shù),Pk n表本部分?jǐn)?shù)為k的n-分拆的個(gè)數(shù)，則P6 11的值是（）A.6B.7C.8D.923.設(shè) AC是實(shí)數(shù)且對(duì)任意正整數(shù)n都有是（）A.9B.8C.7D.624.不定方程x1 2x22x317的正整數(shù)解的個(gè)數(shù)是t 2 5te 1 e ,則該數(shù)列的通項(xiàng)公式是（）A.26B.28C.30D.3225.已知數(shù)列an no的指數(shù)生成函數(shù)是Etn n n nA. an 765n 八n nB. an 765C. an7n 2 6n5nD. an7n、填空題1 .在1和2000之間能被6整除但不能被15整除的正整數(shù)共有 個(gè)2 .用紅、黃、藍(lán)、

6、黑4種顏色去圖1 n棋盤，每個(gè)方格涂一種顏色，則使得被涂成紅色的方格數(shù)是奇數(shù)的涂色方法共有 種3 .已知遞歸推關(guān)系an3an 1 4an 2 12an 3 n 3的一個(gè)特征根為 2,則其通解為4 .把n n 3個(gè)人分到3個(gè)不同的房間，每個(gè)房間至少1人的分法數(shù)為 5 .棋盤的車多項(xiàng)式為個(gè)不同類的項(xiàng)。6 .由5個(gè)字母a,b,c,d,e作成的6次齊次式最多可以有n7.k 0k1 k28 .求由2個(gè)0, 3個(gè)1和3個(gè)2作成的八位數(shù)的個(gè)數(shù) 9 .含3個(gè)變?cè)獂, y, z的一個(gè)對(duì)稱多項(xiàng)式包含9個(gè)項(xiàng)，其中4項(xiàng)包含x,2項(xiàng)包含xyz ,1項(xiàng)是1 f 2 3 f 3 19常數(shù)項(xiàng)，則包含xy的項(xiàng)數(shù)為10 .已知小

7、是門的3次多項(xiàng)式且f0 1 , f 111 .已g n,k表示把n元集劃分成 k個(gè)元素個(gè)數(shù)均不小于2的子集的不同方法數(shù)，則g n,2 =12 .部分?jǐn)?shù)為3且沒有等于k的部分的n-分拆數(shù)13 .把24顆糖分成5堆，每堆至少有3顆糖，則有 種分法三、計(jì)算題1 .在1000至9999之間有多少個(gè)數(shù)字不同的奇數(shù)？2、以3種不同的長度，8種不同的顏色和4種不同的直徑生產(chǎn)粉筆，試問總共 有多少種不同種類的粉筆？3、至多使用4位數(shù)字可以寫成多少個(gè)2進(jìn)制數(shù)！ （2進(jìn)制數(shù)只能用符號(hào)0或1）4、由字母表L=a,b,c,d,e中字母組成的不同字母且長度為 4的字符串有多少個(gè)？如果允許字母重復(fù)出現(xiàn)，則由L中字母組成的

8、長度為3的字符串有多少個(gè)？5、從1, 2, 39中選取不同的數(shù)字且使5和6不相鄰的7位數(shù)有多少？6、已知平面上任3點(diǎn)不共線的25個(gè)點(diǎn)，它們能確定多少條直線？能確定多少個(gè)三角形？7、計(jì)算數(shù)字為1, 2, 3, 4, 5且滿足以下兩個(gè)性質(zhì)的4位數(shù)的個(gè)數(shù)：（a）數(shù)字 全不相同；（b）數(shù)為偶數(shù)8、正整數(shù)7715785有多少個(gè)不同的正因子（1除外）？9、50!中有多少個(gè)0在結(jié)尾處？10、比5400大并且只有下列性質(zhì)的數(shù)有多少？（a）數(shù)字全不相同；（b）不出現(xiàn)數(shù)字2和711 .將m=3761寫成階乘和的形式。12 .根據(jù)序數(shù)生成的排列（p）=（3214）,其序號(hào)是多少？13 .如果用序數(shù)法對(duì)5個(gè)文字排列編

9、號(hào)，則序號(hào)為117的排列是多少？14 .設(shè)中介數(shù)序列為（120）,向它所對(duì)應(yīng)的4個(gè)文字的全排列是什么？15 .按字典序給出所有3個(gè)文字的全排列。16 .按遞歸生成算法，依次寫出所有的 4個(gè)文字的全排列。17 .根據(jù)鄰位互換生成算法，4個(gè)文字的排列4231的下一個(gè)排列是什不同的方案？18 .有5件不同的工作任務(wù)，由4個(gè)人去完成它們，每件工作只能由一個(gè)人完成，問有多少種方式完成所有這5件工作？19 .有紀(jì)念章4枚，紀(jì)念冊(cè)6本，分送給十位同學(xué)，問有多少種分法？如限制每 人得一件物品，則又有多少種分法？20 .寫出按次序產(chǎn)生的所有從1, 2, 3, 4, 5, 6中任取2個(gè)的組合。21 .給定一個(gè)n邊

10、形，能畫出多少個(gè)三角形使得三角形的頂點(diǎn)為n邊形的頂點(diǎn)，三角形的邊為n邊形的對(duì)角線（不是邊）？22 .試問（x+y+z）的6次方中有多少不同的項(xiàng)？23 .如果沒有兩個(gè)相鄰的數(shù)在同一個(gè)集合里，由1,2,？。中的數(shù)可形成3個(gè) 數(shù)的集合有多少？24 .試列出重集2 a,1 - b,3 - c的所有3組合和4組合。25 .設(shè)Fn為fibonna序列，求出使Fn = n的所有的n。26 .試求從1到1000中,不能被4,5或6整除的個(gè)數(shù)？27 .計(jì)算12+22+n228 .設(shè)某地的街道把城市分割成矩形方格，每個(gè)方格叫它塊，某甲從家里出發(fā)上班，向東要走過7塊，向北要走過5塊，問某甲上班的路經(jīng)有多少條？29

11、.設(shè)n=2532731 14,試求能除盡數(shù)n的正整數(shù)的數(shù)目。30 .求(1+x4+x8) 10中x20項(xiàng)的系數(shù)。31 .試給出3個(gè)文字的對(duì)稱群注中的所有元素，并說出各個(gè)元素的格式。32 .有一 BIBD,已知 b=14,k=3,入=2,求 v 和 r。33 .將39寫成三ai i!(0 ai r)個(gè)有標(biāo)志的盒中，無一空盒，試問有多少種 萬案？50 .假設(shè)某個(gè)凸n邊形的任意三條對(duì)角線不共點(diǎn)，試求這凸n邊形的對(duì)角線交于多少個(gè)點(diǎn)？51 .求Sn 1 2 3 2 3 4 n n 1 n 2從k個(gè)不同文字中取n個(gè)文字作允許重復(fù)的排列，但不允許一個(gè)文字連續(xù)出現(xiàn) 3次，求這樣的排列的數(shù)目。52 .求下圖中從

12、A點(diǎn)出發(fā)到n點(diǎn)的路徑數(shù)。53 .n條直線將平面分成多少個(gè)區(qū)域？假設(shè)無三線共點(diǎn)，且兩兩相父54 .四位十進(jìn)制數(shù)a b c d ,試求滿足a+b+c+d=31的數(shù)的數(shù)目55 .兩名教師分別對(duì)6名學(xué)生面試，每位教師各負(fù)責(zé)一門課，每名學(xué)生面試時(shí)間 固定，6名學(xué)生面試時(shí)間定于下周一的第 1節(jié)至第6節(jié)課，兩門課的面試分 別在901和902兩個(gè)教室進(jìn)行。試問共有多少種面試的順序。56 .對(duì)正六角形的6個(gè)頂點(diǎn)用5種顏色進(jìn)行染色，試問有多少種不同的方案？旋 轉(zhuǎn)或翻轉(zhuǎn)使之重合的視為相同的方案。58 .生成矩陣10001 0 10100111G001011000010 1 1試求相應(yīng)的校驗(yàn)矩陣H。59 .由m個(gè)0,

13、 n個(gè)1組成的n+m位符號(hào)用,其中n&m+1,試求不存在兩個(gè)1相鄰 的符號(hào)用的數(shù)目。60 .n個(gè)男人與n個(gè)女人沿一圓桌坐下，問兩個(gè)女人之間坐一個(gè)男人的方案數(shù)， 又m個(gè)女人n個(gè)男人，且m2),則 n1.5/2其中 a = (1+，5)/2, B=(1-，5) /28 . N個(gè)代表參加會(huì)議，試證其中至少有兩個(gè)人各自的朋友數(shù)相等。9 .證明：12 22n2 n n 1 2n 1 /61/2 。10 .證明：2n!/2n是整數(shù)11 .證明：在邊長為1的等邊三角形內(nèi)任取5點(diǎn)，試證至少有兩點(diǎn)的距離小于12.證明:11 n Fn 1 Fn10 Fn Fn 1其中 Fn 定義為：Fi F2 1, Fn Fn

14、1 Fn 213 .任取11個(gè)整數(shù)，求證其中至少有兩個(gè)數(shù)它們的差是10的倍數(shù)。14 .在邊長為1的正方形內(nèi)任取5點(diǎn)，試證其中至少有兩點(diǎn)，其間距離小于 衣/2,15 .若H是群G的子群，試證：|xH|=K,其中K=|H| , xCG16 .二維空間的點(diǎn)(x,y )的坐標(biāo)x和y都是整數(shù)的點(diǎn)稱為格點(diǎn)。任意5個(gè)格點(diǎn)的 集合A,試證A中至少存在兩個(gè)點(diǎn)，它們的中點(diǎn)也是格點(diǎn)。17 .證明：在由字母表0,1, 2生成的長度為n的字符串中，0出現(xiàn)偶數(shù)次的字 符串有(3n+1) /2個(gè)。c m, n c m n,02n c m,n18 .試證任意r個(gè)相鄰的正整數(shù)的連乘積(n+1) (n+2) - (n+r)必被r

15、!除盡。19 .證明： c m,0 c m,n c m,1 c m 1, n 120 .證明 cn,1 2c n,2nc n, n n2n 121 .任取5個(gè)整數(shù)，試求其中必存在3個(gè)數(shù)，具和能被3整除。22 .若H是群G的子群，x和y是G的元素。試證xHC yH或?yàn)榭占?，或xH=yH.23 .令 S=1, 2,，n+1,n 2, T x, y,z S,x z, y z試證：T 12 22n2 C n 1,2 2C n 1,3。24 .證明：任何K個(gè)相繼的正整數(shù)之積，必是r的倍數(shù)，其中r=1 , 2,，Ko25 .求證：2n122n2 2nn 12 n2n n 1 o26.使用二項(xiàng)式定理證明nn

16、n 2k,試推廣到任意實(shí)數(shù)r,求k 0nn kk r o 027 .證明 |A B C |A |B |C A B |A C B C |A B C28 .證明任何k個(gè)相繼正整數(shù)中，有一個(gè)必能被 k整除。29 .證明在小于或等于2n的任意n+1個(gè)不同的正整數(shù)中，必有兩個(gè)是互等的。用=弓30 .證任一正整數(shù)n可唯一地表成如下形式： 肉 ,0ail)個(gè)不同文字取出n個(gè)(可以重復(fù))作排列，但不允許一個(gè)文字連續(xù) 出現(xiàn)3次的排列所組成的集合為An,則所求排列數(shù)a n= | A n | o將A0中的字符串按最后一個(gè)文字可以分成兩類：一類是最后一個(gè)文字同其前一個(gè)文字不相同的那些字符串，共有（k 1） a n i

17、個(gè)（最后一位有k 1種選擇，而前n 1位是沒有一個(gè)文字連續(xù)出現(xiàn)3次的字符串），另一類是最后兩個(gè)文字相同，但與倒數(shù)第3個(gè)文字不相同 的字符串，共有（k 1 ） a 2個(gè)，所以有遞推關(guān)系n - 2(k-1)(k+ 1a n ( k 1 ) a 而 ai=k, a 2=k，遞推關(guān)系的特征方程為2,.x (k 一 ) x ( k 一 )=0其根為:a 1 = (k1 + sqrt ( (kl) (k + 3) )/2a 2 = (kl sqrt ( (kl) (k + 3) )/2于是知an = Aiain + A2a2n由于a i = k , a 2 = k 2 ,由遞推關(guān)系知a o=k/ (k l

18、),所以ao=k/(kl)=A iai + A2a2A = Ai+A2ai=k=A iai1+A2a21=Ai (k 1 + sqrt (kl) (k + 3) )/2+ A2(k-l-sqrt (kl) (k + 3) )/2解得Ai=(k/(2 (k l) A 2 = (k/ (2 (k l) 所以an= (k/ (2 (k l)+k/ (2)k/ (2)+k/ (2sqrt ( (k l)sqrt ( (k l),sqrt ( (k l)(k + 3)(k + 3)(k + 3)(k- 1 + sqrt (kl)(k + 3) )/2)+ (k/ (2 (kl) k/ (2 - sqrt

19、(kl) (k + 3)(k 一 1 一 s qD (k + 3) ) /2)53. f (n) = ( ( 1+，5 )/2)n+1- (1-V5) /2)n+1) /V5假設(shè)從A (編號(hào)為0 )到編號(hào)為 i的頂點(diǎn)有f (i )條路徑，則f ( 1 )= 1, f (2)=2 ,當(dāng) i 2 時(shí)，f (i ) =f (i-1) +f (i 2),由此知 f ( 0 ) = f(A)= 1。當(dāng)i=n 時(shí)，f (n) = f (n-1 ) +f (n 2)，即 f (n) -f (n-1 ) -f (n 2) = 0。其特 征方程為：x? x 1=0,它的兩個(gè)根分別為：a 1=(1+，5)/2,

20、a 2=(1，5)/2。于是知 f (n)=Aiain+A20C2n,根據(jù)f (0) =1= A + A2f(l)=l=A(l+，5)/2+ A2(l -V5 )/2, 解得A1= ( 1 +，5 ) / (25), A2= ( 1 -V5 ) / ( 2)所以,f (n) = ( (1 +，5) /2)- (1-，5 ) /2)J /，5 = F ( n+ 1)其中F (n)為第n個(gè)Fibonacci數(shù)。54. an= (n2+n+2) /2設(shè)n條符合條件的直線將平面分成an個(gè)區(qū)域，那么n- 1條直線可將平面分成an1個(gè)區(qū)域，而第n條直線與前n-1條直線均相交，有 n1個(gè)交點(diǎn)，因此第 n條直

21、線被分成n 段，而每一段對(duì)應(yīng)一個(gè)新增的區(qū)域，所以有an=ani+n,即anani = n。于是an 1 an 2 = n 1 , 由此得 an 2 an 1 + an- 2=1, 同牛羊an 1 2 an 2 + an 3=1, 故得an 3 an-1 + 3 an- 2 - an- 3 = 0,其特征方程為 x3 3 x?+ 3 x 1 = 0 ,解此方程 得 a = a 1 = a 2 = a 3=1,所以 an = (Ao+Ain + A2n2) a n=Ao+Ain+ A2n2 ,而a0= 1 = Aoai = 2 = Ao+ Ai + A2a2 = 4 = Ao+ 2 A + 4 A

22、2解得Ao=1A 1=1/2A 2=1/2由此知an= (n+n+2) / 255、56因?yàn)?X1+X2+X3+X4= 31,Xi0 (i = 1 , 2,3, 4 )的整數(shù)解共有C (4+31-1,31)=C (34, 3 ) = 34 33 32/6 = 5984 (個(gè))。再考慮X1+X2+X3+X4= 31,Xi 1 0 (i = 1 , 2,3, 4 )的整數(shù)解的個(gè)數(shù)。令N為全體非負(fù)整數(shù)解，則|Nl| = 5984。令A(yù)(i = 1 , 2 , 3 , 4 )為其中Xi 1 0的解集合。則| A |即為(Xd 10) + X2+X3 + X4 = 31,也就是X1 + x2+x3+x4

23、 = 21的非負(fù)整數(shù)解的個(gè)數(shù)。所以，| A | = C(4 +21- 1, 21)= C (24, 3) = 24 23 22/6 =2024。同理可知I A I = IA3 I= I A4I = IA1 I = 2024。類似地，I A n A | = C (4+11-1 ,11 ) = C (14, 3) = 14 13 12/6 = 364 ( 1 & ij 0 4), |AnAnA|=C (4+11, 1)=C (4, 1)=4(1W ijk W4),而I Ai n a2nA3nA4 1 = o。根據(jù)容斥原理，a+ b+c + d=31, 0 n）個(gè)間隔（包括頭尾處的 間隔）。在此m+

24、 1個(gè)間隔中任取n個(gè)插入1 ,則所得符號(hào)串滿足要求，所以共有 C （m+1, n）個(gè)這樣的符號(hào)串。60. （n l） ! n!, （n l） ! n!/ （nm）!先讓n個(gè)男人圍坐一圈，共有（n 1 ）!種坐法。對(duì)應(yīng)于每一種坐法，有 n個(gè)間隔，將n個(gè)女人排成一行插入這 n個(gè)間隔中，有n!種方案，所以共有（n1） !n!種不同的 坐法。若只有m （mrj）個(gè)女人，則在 n個(gè)間隔中任取 m個(gè)排列，將 m個(gè)女人插入這n個(gè)間隔 中，有P （n, m） = n!/ （n-m） !種方案，所以共有（n-1 ） !n!/ （n-m） !種不同的坐 法。61. a n = 4n-v/3 （2+，3） n+1/

25、6+，3 （ 2-，3） n+1/6設(shè)長度為n的由A B、C、D組成的允許重復(fù)的排列中AB至少出現(xiàn)一次的排列所組成的集合為S,又設(shè)a n= | Sn | o而AB 一次也不出現(xiàn)的排列所組成的集合為R,又設(shè)b=I Bn I?？蓪n中的所有排列按 AB出現(xiàn)的位置分為兩類：一類是在前 n-1位中均 未出現(xiàn)AB,它僅出現(xiàn)在最末兩位， 則這種排列共有bn-2個(gè)。另一類是在前n-1位中已出 現(xiàn)AB,而最后一位可以是 A、B、C D中的任一個(gè)，所以這類排列共有 4an-1個(gè)，于是知a n = 4an-1 +b n-2 ,而由此知于是得n = 4an-1 +4a n+bn=4n,即 an-2 + bn-2=

26、4n-2 ,也就是 bn-2=4n-2 -a-a n-2,即 a n-4a n-1 +a n -2=4 , 推知 4( a n -1 -4a n-2 +a n-3)=4a i = 4,n-8a n-1 +17a n-2-4an-3=0,其特征方程為 x3-8x2+17x-4=0,解此方程得a 2=2+，3, a 3 = 2-，3,所以可設(shè) a n = Ai a J+A2 a 2“+A3 a 3”，已知 a 1=0,a2 =1 ,由此推知ac=0,所以有ac=0= A1+A2+A3a1=0= 4Ai+ (2+，3) A2+ (2-，3) Aa2=1= 16A1+ (7+4,3) A2+ (7-4,3) A化簡得A i+A2+A