组合数学题库答案

1、填空题1. .将5封信投入3个邮筒，有 243 种不同的投法.2. 5个男孩和4个女孩站成一排。如果没有两个女孩相邻，有43200 方法.3. 22件产品中有2件次品，任取3件，恰有一件次品方式数为 380 .4. (xy)6所有项的系数和是_64.答案：645.不定方程XiX2X32的非负整数解的个数为 6 .6 .由初始条件 f (0) 1, f(1) 1及递推关系f(n 2) f(n 1) f(n)确定的数列 f (n) (n 0)叫做 Fibonacci 数列7 . (3x-2y) 20的展开式中x10y10的系数是c0310( 2尸.8 .求6的4拆分数P4(6) 2.9 .已知在

2、Fibonacci 数列中，已知 f (3)3, f (4) 5, f (5)8 ,试求 Fibonacci 数f (20)1094610 .计算 P4(12)4P4(12)Pk(12)R(8) P2(8) P3(8) PM8)k 134P1(8)P2(8)PkPk(4)14 5 5k 1k 111 . P4(9)( D) A. 5 B. 8 C. 1012 .选择题1.集合A &,a2,L冏。的非空真子集的个数为(15D. 6A )C.10242 .把某英语兴趣班分为两个小组，甲组有2名男同学，5名女同学；乙组有 3名男同学，6名女同学，从甲乙两组均选出3名同学来比赛，则选出的6人中

3、恰有1名男同学的方式数是(D )A. 800 B. 780 C. 900 D. 8503.设(x, y)满足条件x y10,则有序正整数对(x,y)的个数为(D )A. 100 C. 504,求(x0 3x1 2x2 x3)6 中 乂2乂12项的系数是( C )B. 604 » 一 22 一一一5 .多项式(2x0 x1 4x2 x3)中项x0 x x2的系数是( C )A. 78 B. 104 C. 96 D. 486 .有4个相同的红球，5个相同的白球，那么这 9个球有( B )种不同的排列方式A. 63 B. 126 C. 2527,递推关系f(n) 4f(n 1) 4f(n

4、2)的特种方程有重根2,则(B )是它的一般解A. 012n 1 c22nB. (c1 c2n)2nC. c(1 n)2n D. c12n c22n8 .用数字1,2,3,4 (数字可重复使用)可组成多少个含奇数个1、偶数个2且至少含有一个3的n (n 1)位数()运用指数生产定理n cnn c nn onnA.4n 3n ( 1)n B. 431421. 43( 1)9.不定方程XiX2xnn正整数的解的个数为多少（A/ C )不确定r A.rB.r10. Xi X2X3n C.n D.r14的非负整数解个数为（D. 5011.从1至1000的整数中，有多少个整数能被5整除但不能被6整除（1

5、2.期末考试有六科要复习，若每天至少复习完一科（复习完的科目不再复习）把全部科目复习完，则有多少种不同的安排（A. 9B. 1613.某年级的课外学科小组分为数学、语文二个小组，参加数学小组的有23人,参加语文小组的有27人；同时参加数学、语文两个小组的有7人。这个年级参加课外学科小组人数(CA. 5014.将A、1B. 57C. 43D. 1111封信放入8个信箱中，则必有一个信箱中至少有（B ）封信。15.组合式B、120D、4120A、6016.在1：A、 250B、与下列哪个式子相等11950119 +4912512011949D、493, 4,5,6全排列中，使得只有偶数在原来位置的

6、排列方式数为（A )。B、 4C、17.若存在一递推关系n nA.3 2318 .递推关系anA.an2n B. a2n19 .错位排列数 n 1A.nDn ( 1)4anB.23an 2%5an3n94,a16an2nD、9242(n则an2)n 1C.3 22n （n 2）的特解形式是（A ).n 1 n 1D.3 23（a为待定系数）C. anDn (3 n2 n2 D. an 2B. (n 1)Dn20.有100只小鸟飞进6个笼子,A. 15 B. 16 C. 17 D. 1821. 10个节目中有6个演唱，4）答案：Cn（1） C. nDn 1则必有一个笼子至少有(1)n_n 1D.

7、 (n 1)Dn ( 1)C )只小鸟个舞蹈，今编写节目单，要求任意两个舞蹈之间至少有个演唱，问可编写出多少种不同的演出节目单A6CX； P(6,6)?P(7,4)22.数列 n n 0的生成函数是（D )。A、B、D、23.6个男孩和4个女孩站成一圈,A、P(6, 4)B、6!P(6,4)如果没有两个女孩相邻,6!C P（6,4）6D、）种排法。6! P(7,4)24.排 A, B,A、1225.求多重集A. 700G D, EB、72F六个字母，使A, B之间恰有2个字母的方式数（D ）。C、36D、144S3 a,2 b,4 c的 8-排列数是( C )B. 140 C. 1260 D.

8、120026. 多, A.一糕点店生产8种糕点，如果一盒内装有 12块各种糕点，并且可以认为每种糕点无限那么你能买到多少种不同的盒装糕点(假设装盒与顺序无关)50000 B. 50388 C. 55000 D. 5278827.在一次聚会上有 15位男士和20位女士,则形成15对男女一共有多少种方式数(A )A.20!5!20!在20B. - C. 15D.152028.A.an1的生成函数是(1 x)2B.2x(1 x)2C.(1x)2D.x(1 x)2计算题1.试确定多重集S=1 ai,a2,a3,L ,ak的 r组合数。解：把包含S的r一组合分成两类：”的r组合：这种组合数等于即NiC(

9、k 1) (r不包含a的r组合:1即 N2 C(k 1) r由加法法则，所求的r1) 1,r 1) C(k这种组合数等于a2,a3r 3, rak的(r-1)1)a2，a3,ak的r组合数1,r) C(k组合数为Nr 2,r)N1N2 C(k3,r 1) C(kr 2,r)2.求S 5a,3b的6-排列数解:根据题意有：MNi1 16!4!2!5a,b, M15,电3.求(12x3x24x3)6展开式中4.求(12x的展开式中解：(12x)n = (1 x)2)n所以x5的系数为2n5. (1)求 ann55的生成成函数。解：设A(t)antn ,则 A(t)(2)解递归关系:H (n) 4H

10、 (n2 4a,2b, M33a,3b6 20则的全排列数N3!3!x5的系数NiN2 N 3 412nn 3。5(n 3)又因为(12nx)2n 2n k xk 0 k(1 x)2n。5x5的系数淇中3)0)(nn 05)tn(n01)tn 4ntn2(1 t)1) 4H (n4(1t)11 4 4t 54t(1 t)2(1 t)22)H (0) 1,H (1) 3。答案：解特征方程 x2-4x-4=0 xi=x2=2.得 H(n)=2n1+n/26.求重集 S 20ga,14gb,20gs的 10-组合数。答案:C(10+3-1 ,10)7. (a b c d)100的展开式在合并同类项后

11、一共有多少项 答案:C(100+4-1 , 100).8.解递推关系 an 5an 1 6an 2 n 2, a0，a14解：递推关系 an 5an 1 6an 2 n 2(1)的特征方程为x2 5x 6 0,特征根为x1 2,x2 nnan c1 2C2 3 .因为(1)式无等于1的特征根，所以递推关系49. (n42)3.故其通解为an 5an 1 6an 2 n 2 n 2(2)有特征根an AnB,其中a和B是待定常数，代入2)式得2A 12B 7A 2An B 5A(n 1) B 化简得2An 2B 7A n 2,所以6A(n 2)B n 2.、111解之得A -, B 一.于是an

12、24C1 2nn 11.c2 3n -n ,其中Ci,C2是待定常数。24由初始条件得C1C211272Ci 3c2114494111解之得 G3,c21.所以 an3 2n 3n -n (n 2).24解：递推关系an的特征方程为9 .解递推关系 an5an 1 6an 2 2n 3, a。 5,a1 10. (n 2)5an 1 6an 2 n 2(1)3.故其通解为2x 5x 6 0 ,特征根为x12,X2nnc1 2C23 .因为(1)式无等于1的特征根，所以递推关系an 5an 1 6an 2 2n 3 n 2(2)有特征根anAn B,其中a和B是待定常数，代入(2)式得An B

13、5 A(n 1) B 6A(n 2) B 2n 3化简得2An 2B 7A 2n 3,所2A 2 以解之得 A 1,B 2.于是2B 7A3 anc1 2nC23n n 2,其中G,C2是待定常数。由初始条件得G c2 2 52Ci 3C2 2 2 10解之得 G 2,c21.所以 an 2n 1 3n 3n n 2(n 2).答案：a。2n 13n n 210 .求1到1000之间不能被5 , 6 ,或8整除的自然数的个数。解：设A为1至1000的整数中能被5整除的数的个数；B为1至1000的整数中能被6整除的数的个数；C为1至1000的整数中能被8整除的数的个数1000200, B5100

14、061000166, C 125, A B81000.33,30A C 100025, B C40100041,A B C100024120所以 1A B C11ABicA B 1A Cl IB200 166 125 33 25 41 8 400 即所求为：1000 400 600.11.在所有的n位数中，包含数字3、8、9但不包含数字0、4的数有多少解：除去 0、4,则在 1、2、3、5、6、7、8、9这8个数组成的n位数中：令S表示由这8个数字组成的所有n位数的集合，则 S 8n；令P1表示具有性质：一个 n位数不包含3 ；令P2表示具有性质：一个 n位数不包含8；令P3表示具有性质：一个

15、 n位数不包含9；令A表示S中具有性质P的元素构成的集合(i 1,2,3)则有容斥原理，3|A1 IA2IA3I|S| Ai| (|A1IA2 |A21A3|A1IA3|)|A1IA2I A3 |i 1而 |Ai |7n,i1,2,3; |Ai IA211A21A3| A1IA316n,|AiIA21A3|5n所以 A1 I A2I A38n 3 7n 3 6n 5n4 5312.求(1 2x 3x )的展开式中x3的系数。解：原式=(1 2x 3x4)5 =54.554.4524.353 4.2544.(3x )(1 2x)(3x )(1 2x) (3x )(1 2x) (3x )(1 2x

16、) (3x )012345(1 2x)所以x3的系数523=80213.请确定在(Xix2 2x3 2xn8的展开式中xfxfxax2项的系数。2312 12 ( 1)3 (2)1 ( 2)28!2!3!2!(8)8!3组合数。试确定多重集 S=b1,3 b2,5 b3,7 b4的10解：构造多重集S' =8*b1, 8*b2, 8*b3, 8*b4,令S'的所有10组合构成的集合为 S, 有|S|二C(4+10-1,10)。令B为至少出现4个b2的组合构成的集合，C为至少出现6个b3的组合构成的集合，D为至少出现8个b4的组合构成的集合。由于B中的每一个10组合至少含有 4个

17、b2,故这样的一个组合相当于S'的一个6组合，反之，S'的一个6组合加上4个b2就得到了 B的一个10组合。这两种选法是一一对应的。故 |B|=C(4+6-1,6),同理有 |C|=C(4+4-1,4) , |D|=C(4+2-1,2)。类似的分析可得|B n c|=c(4+o-i,o), |B n d|=o, |C n d|=o , |B nCn d|二o。根据容斥原理， S的10组合数为286-(84+35+10)+(1+0+0)-0=15814.解递推关系：an 5an 1 6 an 2 2n 3(n 2)a。 5,a1102解：特征万程为x 5x 6 0 ,特征根为X1

18、 1,X22,X32所以对应的齐次递推关系式有anG 2n C2 3n的通解原递推式有特解为an An 6an2,代入原递推式得A=1, D=2,因此原递推式有通解anCi2nc23nn 2 ,再将 a。5,a110 代入通解得 g2,c21 ,所以n 1 nan 23 n 214.有红球4个，黄球3个,解：由定理得：白球3个，把它们排成一条直线，有多少种排法(4 3 3)!4!3!3!420015.求M 4 a,3 b的5-可重排列数。t解法 1： A=(1+t+ 2!一，5 . 一所以t的系数为:t一 )(1 t 3!114! 2!3!t2 t! 42! 3! 4!13!2!t5则L的系数

19、为:5!5!1一) 3!2!二25M 4 a,3 b的 5-排列数有 M1 4 a,1 b , M23 a,2 b , M32 a,3 b三种情况。n1 0,N2 W-,N3 B- 14!, 2 3! 2!, 32! 3!N N1 N2 N3 5 10 10 2515.求x1 2x2 4x328的正整数解的个数解：22448A(x) (x x2L )(x2x4L )(x4x8L )72244x7(1x x2L )(1 x2x4L )(1 x4L )7x2(1 x)(1 x )(1 x )772 2x (1 x) x (1 x)(1 x )2-44(1 x ) (1 x )(1 x )证明题1

20、.证明：边长为4的正三角形内任意 5个点必有两点其距离不超过 2。答案：取个边中点将三角形等分为四个边长为2的三角形。则5个点中必然有两个落在同一个三角形内。2 .设x”x2,L ,xn是n个正整数，证明其中存在着连续的若干数，其和为n的倍数。答案：令si x1 x2 x,i 1,2, ,n把si除以n的余数记作ri50 n n 1如果存在i,使得n 0，则x x2x可以被n整除，如果对于所有的i，i 1,2, ,n都有n0那么n个q，只能有1,2， ，n 1种可能的取值，由割巢 原理必存在j和k满足口 rk，k 因此：Sj sk xk 1 xk 2xj可以被n整除j k k I k 2j3

21、.设S是n元集，则S的子集数是2n C(n,0) C(n,1) L C(n,n)。答案：对于r 0,1, ,n,s的每个r元子集就是s的一个r组合，因此C(n,r)就是s的r 元子集数根据加法法则，s的子集数是C(n,0) C(n,1)C(n,n),另一方面，构成s的某子集时可以对每个 元素有两种选择属于该 子集或不属于该子集，于是由乘法 法则得不同的子集总数是2n4 .某学生在37天里共做了 60道数学题。已知他每天至少做1道题，求证：必存在连续的若干天，在这些天里该学生恰做了13道数学题。证明：设该同学从第1天至第ii 1,2,L ,37 天共做了 ai道数学题，则1 ai a2a37 6

22、0.令 biai 13 i1,2,37 ,则 14nb2L b3773.令A1,2,L ,73, Aa,a2,Lg7 ,A hML% ,则AA A如果A1A2，则AA1A2 A|A37 3774,这与A 73矛盾，所以A A ，从而存在akA1,bi A2,使彳#akbi,即akai 13, ak ai 13,这表明该学生从第l 1天到第k天共做了 13道数学题。25 .证明：C(2n,2) 2c(n,2) n。这里，C(m,n)表示从m个对象中取n个的方法数。 答案：等式左边表示从 2n个不同的球中取两个球的方法数。我们把2n个球平均分成A, B两组，选球的方法有以下两类：去自同一组的选法数

23、为N1 2c(n,2);取自不同组的球的22万法数为N2 C(n,1) n6 .如 n, rCN 且 n7>2 则 P(n,r)= r x P(n-1,r-1)+P(n-1,r)证明：当r>2时，把集合A的r排列分为两大类：一类包含A中的某个固定元素，不妨设为a1，另一类不包含 a1。第一类排列相当于先从A-a1中取r-1个元素进行排列，有 P(n-1,r-1)种取法，再将 a1放入每一个上述排列中，对任一排列，a1都有r种放法。由乘法法则，第一类排列共有r x P(n-1,r-1打。第二类排列实质上是 A-a1的r排列，共有P(n-1,r)个。再由加 法法则有 P(n,r)= r

24、 x P(n-1,r-1)+P(n-1,ir)i毕。7 .用非降路径法证明：C(m n, n) C(m n 1, n 1) C(m n 1, n)这里，C(m,n)表示从m个对象中n取个元素的方法数。答案：(0,0)到(m,n)的路径数为 C(m+n , n);又，(0,0)到(m,n)的任一路径必过(m-1,n)或。 故，等式成立；mnmnmnmn8 .证明：L。0 r 1 r 1r 0 r解：证明：法1,设A=am,B=bn,且A C B=，则AU B=C有m+n个元素。C的r组合个数 为C(m+n,r),而C的每个r组合无非是先从 A中取k个元素，再从B中取出r-k个元素组成 (k=0,

25、1，,r)。由乘法法则共有 C(m,k)C(n,r-k)种取法，再由加法法则即可得证。应用题1 . 一次宴会，5位来宾寄存他们的帽子，在取帽子的时候有多少种可能使得没有一位来宾取回的是他自己的帽子44种可能使得没有一位来宾取回的是他自己的帽子。11111解：属于重排问题，所求为 D5o D55!(1-)44 (6分)551!2!3!4!52 .n对夫妻围圆桌就座，要求每对夫妻不相邻，问有多少种入座方式解：将n个丈夫记为Xi,X2, ,Xn他们的妻子分别记为Vl，V2, ,yn, 设pi表示xi与yi相邻，其中i 1,2, ,n令s为2n个人的全体环排列 构成的集合，s的满足性质R的子集为A,i

26、 1,2, ,n那么有s (2n(1)! A 2(2n(2)!,i 1,2, ,nA Aj2(2n(2)!,1 i j nA1A2A 2n(n 1)!由包含排斥原理得 N (2n 1)! 1n 2(2n 2)! 2 22(2n 3)!n 23(2n 4)!( 1)n n 2n(n 1)!2 .用17张100元钱买3支股票，不要求每支股票都买，但要求买A股钱数必须是200的倍数，买B股钱数是400的倍数，求有多少种买法25种买法。解：此题等同于求方程X12X2 4X3 17的非负整数解的个数。方程通过换元可变为：y1 y2 y3 17 ,其中y1为非负整数，丫2为非负偶数，y为非负的4的倍数的整

27、数。由此构造常生函数：(1 t t2)(1 t2 t3)(1 t4 t8)所求为常生成函数的t17的系数，化简生成函数为：1(1 t)(1 t2)(1 t4)2,可求得公式得t18的系数为25。1 t 1 t2 1 t43 .方程xx2x3x430有多少满足x12 ,x20 ,x35 ,x48的整数解解进行变量代换：丫1 牛 2 , y2 x2, y3 X3 5 , ydX4 8则方程变为y1 y2 y3 y425原方程满足条件的解的个数等于新方程的非负整数解的个数。新方程的非负整数解的个数为25 4 125282528328 27 263!32764 .用四种颜色(红、蓝、绿、黄)涂染四台仪器A,B,C和D。规定每台仪器只能用一种颜色并任意两台仪器都不能