组合数学题库答案

?1000??1000??1000??1000?A???200,B??166,C??125,A?B???6??8??30??33,5????????则

?1000??1000??1000?A?C???25,B?C??41,A?B?C???24??120??8?40?????所以

A?B?C?A?B?C?A?B?A?C?B?C?A?B?C?200?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表示具有性质：一个n位数不包含9；

令Ai表示S中具有性质Pi的元素构成的集合(i?1,2,3) 则有容斥原理， A1A2A3?S??|Ai|?(|A1i?13A2|?|A2A3|?|A1A3|)?|A1A2A3|

而|Ai|?7,i?1,2,3;|A1所以A1nA2|?|A23A3|?|A1A3|?6n，|A1A2A3|?5n

A2A3?8n?3?7n?3?6n?5n

454512．求(1?2x?3x)的展开式中x的系数。 解：原式=(1?2x?3x)=

?5?45?5??5??5??5?4424334244??(3x)???(1?2x)(3x)???(1?2x)(3x)???(1?2x)(3x)???(1?2x)(3x) ?0??1??2??3??4??5????(1?2x)5?5?所以x的系数???2=80

3213．请确定在(x1?x2?2x3?2x4)8的展开式中x12x2项的系数。 x3x43?5??2?3???1?(?1)8231223?(2)1?(?2)2

8!8!??(?8)?2!3!2!3试确定多重集S={??b1,3?b2,5?b3,7?b4}的10?组合数。

解：构造多重集S’={∞*b1, ∞*b2, ∞*b3, ∞*b4}，令S’ 的所有10?组合构成的集合为S，有|S|=C(4+10-1,10)。令B为至少出现4个b2的组合构成的集合， C为至少出现6个b3的组合构成的集合，D为至少出现8个b4的组合构成的集合。

由于B中的每一个10?组合至少含有4个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∩C|=C(4+0-1,0)，|B∩D|=0，|C∩D|=0，|B∩C∩D|=0。

根据容斥原理，S的10?组合数为286-(84+35+10)+(1+0+0)-0=158 14．解递推关系：

?an?5an?1?6an?2?2n?3(n?2) ??a0?5,a1?10解：特征方程为

x2?5x?6?0，特征根为x1?1,x2?2,x3?2

所以对应的齐次递推关系式有an?c1?2n?c2?3n的通解

原递推式有特解为an?An?6an?2，代入原递推式得A=1，D=2，因此原递推式有通解

an?c1?2n?c2?3n?n?2，再将a0?5,a1?10代入通解得c1?2,c2?1，所以an?2n?1?3n?n?2

14.有红球4个，黄球3个，白球3个，把它们排成一条直线，有多少种排法？ 解：由定理得： N?(4?3?3)!?4200

4!3!3!15．求M?{4?a,3?b}的5-可重排列数。

t2t3t2t3t4解法1：A(t)=(1+t+?)(1?t???)

2!3!2!3!4!1115? 所以 t的系数为：?

4!2!3!3!2!111t5? 则的系数为：5!（?）=25

4!2!3!3!2!5!M?{4?a,3?b}的5-排列数有M1?{4?a,1?b}, M2?{3?a,2?b}, M3?{2?a,3?b}三

5!5!5!,N3?种情况。N1?,N2?

4!3!?2!2!?3!N?N1?N2?N3?5?10?10?25

15．求x1?2x2?4x3?28的正整数解的个数 解：

A(x)?(x?x2?)(x2?x4?)(x4?x8?) ?x7(1?x?x2?)(1?x2?x4?)(1?x4?)

x7(1?x)(1?x2)(1?x4)7722

x(1?x)x(1?x)(1?x)?(1?x2)2(1?x4)(1?x4)3证明题

1．证明：边长为4的正三角形内任意5个点必有两点其距离不超过2。 答案：取个边中点将三角形等分为四个边长为2的三角形。则5个点中必然有两个落在同一个三角形内。

2．设x1,x2,,xn是n个正整数，证明其中存在着连续的若干数，其和为n的倍数。 ?答案：令si?x1?x2???xi,i?1,2,?,n把si除以n的余数记作ri，0?ri?n?1如果存在i,使得ri?0，则x1?x2???xi可以被n整除，如果对于所有的i，i?1,2,?,n都有ri?0那么n个ri，只能有1,2，?，n?1种可能的取值，由割巢原理必存在j和k满足rj?rk，k?j因此：sj?sk?xk?1?xk?2???xj可以被n整除

3.设S是n元集，则S的子集数是2n?C(n,0)?C(n,1)?

?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的某子集时可以对每个元素有两种选择属于该子集或不属于该子集，于是由乘法法则得不同的子集总数是2n

4．某学生在37天里共做了60道数学题。已知他每天至少做1道题，求证：必存在连续的若干天，在这些天里该学生恰做了13道数学题。 证明：设该同学从第1天至第i?i?1,2,,37?天共做了ai道数学题，则

1?ai?a2???a37?60.

b37?73.

令A??12，，，73?，A1??a1,a2,,a37?,A2??b1,b2,,b37?,则A1?A2?A.

如果A1?A2??，则

令bi?ai?13?i?1,2,?,37?， 则 14?b1?b2?A?A1?A2?A1?A2?37?37?74,这与A?73矛盾，所以A1?A2??，从而存在ak?A1,bl?A2,使得ak?bl,即ak?al?13,ak?al?13,这表明该学生从第l?1天到第k天共做了13道数学题。

5．证明 ：C(2n,2)?2C(n,2)?n2。这里，C(m,n)表示从m个对象中取n个的方法数。 答案：等式左边表示从2n个不同的球中取两个球的方法数。我们把2n个球平均分成A，B两组，选球的方法有以下两类：去自同一组的选法数为N1?2C(n,2); 取自不同组的球的方法数为N2?[C(n,1)]2?n2

6．如n, r∈N且n≥r≥2，则P(n,r)= r×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×P(n-1,r-1)个。第二类排列实质上是A-{a1}的r?排列，共有P(n-1,r)个。再由加法法则有P(n,r)= r×P(n-1,r-1)+P(n-1,r) 证毕。 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)或 (m.n-1)。故，等式成立；

?m??n??m??n??m??n??m?n?8．证明：??????????????????。

0r1r?1r0r??????????????解：证明：法1, 设A={am},B={bn},且A∩B=Φ，则A∪B=C有m+n个元素。C的r?组合

个数为C(m+n,r)，而C的每个r?组合无非是先从A中取k个元素，再从B中取出r-k个元素组成(k=0,1,…,r)。由乘法法则共有C(m,k)C(n,r-k)种取法，再由加法法则即可得证。

应用题

1．一次宴会，5位来宾寄存他们的帽子，在取帽子的时候有多少种可能使得没有 一位来宾取回的是他自己的帽子？

44种可能使得没有一位来宾取回的是他自己的帽子。

（!1?解：属于重排问题，所求为D5。D5?511111????）?44………（6分） 1！2！3！4！5！

2.n对夫妻围圆桌就座，要求每对夫妻不相邻，问有多少种入座方式？

解：将n个丈夫记为x1,x2,?,xn他们的妻子分别记为y1,y2,?,yn,设pi表示xi与yi相邻，其中i?1,2,?,n.令s为2n个人的全体环排列构成的集合，s的满足性质pi的子集为Ai,i?1,2,?,n那么有s?(2n(1)!Ai?2(2n(2)!,i?1,2,?,n

Ai?Aj?2(2n(2)!,1?i?j?n?A1?A2???An?2n(n?1)!由包含排斥原理得N?(2n?1)!??n33nnnn??2(2n?4)!???(?1)??2(n?1)!??2(2n?2)!???2(2n?3)!n1n222．用17张100元钱买3支股票，不要求每支股票都买，但要求买A股钱数必须 是200的倍数，买B股钱数是400的倍数，求有多少种买法？ 25种买法。

解：此题等同于求方程x1?2x2?4x3?17的非负整数解的个数。

方程通过换元可变为：y1?y2?y3?17，其中y1为非负整数，y2为非负偶数，y3为非负的4的倍数的整数。

由此构造常生函数： (1?t?t??)(1?t?t??)(1?t?t??)所求为常生成函数的t的系数，化简生成函数为：

172234811124?218t???(1?t)(1?t)(1?t)，可求得公式得的系数为25。 241?t1?t1?t3．方程x1?x2?x3?x4?30有多少满足x1?2，x2?0，x3??5，x4?8的整数解？

解 进行变量代换：

y1?x1?2，y2?x2，y3?x3?5，y4?x4?8

则方程变为

y1?y2?y3?y4?25

原方程满足条件的解的个数等于新方程的非负整数解的个数。新方程的非负整数解的个数为

?25?4?1??28??28?28?27?26??3276 ?25?????25?????3???3!??????3．用四种颜色（红、蓝、绿、黄）涂染四台仪器A,B,C和D。规定每台仪器只能用一种颜色并任意两台仪器都不能相同。如果B不允许用蓝色和红色，C不允许用蓝色和绿色，D不允许用绿色和黄色，问有多上种染色方案？

答案：M?1?6x?10x2?4x3从而得到r1?6,r2?10,r3?4根据定理5.4所求的方案数是N?4！-6?3！?10?2！-4?1！?4

5．一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。

证明 设从第一天到第i天她共学习了ai小时。因为她每天至少学习1小时，所以

a1,a2,?,a37和a1?13,a2?13,?,a37?13都是严格单调递增序列。因为总的学习时间

不超过

60

小时，所以a37?60，a37?13?73。a1,a2,?,a37,

a1?13,a2?13,?,a37?13是1和73之间的74个整数，由鸽巢原理知道，它们中存在相

同的整数，有ai和aj?13使得ai?aj?13，ai?aj?13，从第j?1天到第i天她恰好学习了13小时。

6．8个女孩围坐在旋转木马上。她们可以有多少种方法改变座位，使得每个女孩前面的女孩都与原先的不同？

解 令S为{1,2,3,4,5,6,7,8}的全部7!个循环排列的集合，Ai为出现模式i(i?1)的循环排列的集合（1?i?7），A8为出现模式81的循环排列的集合。若1?k?7且i1,?,ik是集合{1,2,3,4,5,6,7,8}中的不同整数，则|Ai???Ai|?(7?k)!。|1ki?1 ?Ai|?1。因此，

8?8??8??8??8??8??8??8?????????????|A1???A8|?7!??6!?5!?4!?3!?2!?1!??1??2??3??4??5??6??7??0!?1?1625 ??????????????她们可以有1625种方法改变座位。

7．把2n?1个苹果送给3个孩子，若使得任意两个孩子得到的苹果总数大于另一个孩子的苹果树，问有多少种分法？

根据题意写出生成函数如下(1?yn?1)3A(y)?(1?y?y???y)?(1?y)32n3?(1?3yn?1?3y2n?12n?2?y3n?3)?n?0???n?22上述展开式中yN?项的系数为1)n??3???(n?2n?22

?2n?1?22