卢开澄组合数学组合数学第三章

1110004,56、在与之间不能被和整除的数有多少个？

21500357、求从到的整数中能被和整除，但不能被整除的数的个数。

3,3,5,710Sabcd、求多重集合=的组合数。

1234xxx、求不定方程++=14的数值不超过8的正整数解的个数。

57、在宴会后，位男士检查他们的帽子，问有多少种方法，使得（1）没有人接到自己的帽子？（2）至少有一人接到自己的帽子？（3）至少有两人接到自己的帽子？

1218,,()1,gcd(,)11()(1).kkiinpppnnkknknnnp、令为正整数，并令作为整数的所有互异的素数因子。考虑由定义的欧拉函数。利用容斥原理证明

12345123451132432542511595,,,,,,,,PPPPPCCCCCPCCPCPCCPCPCPC、 名旅客,要去5个地方,，其中，不愿意去,；不愿意去；不愿意去；不愿意去不愿意去。问去的概率有多少？

组合数学卢开澄课后习题答案

组合数学是一门研究离散结构和组合对象的数学学科，它广泛应用于计算机科学、统计学、密码学等领域。卢开澄是中国著名的组合数学家，他的教材《组合数学》是该领域的经典之作。在学习组合数学的过程中，课后习题是巩固知识、提高能力的重要途径。下面我将为大家提供一些卢开澄课后习题的答案。

第一章：集合与命题逻辑

1.1 集合及其运算

习题1：设集合A={1,2,3}，B={2,3,4}，求A∪B和A∩B的结果。

答案：A∪B={1,2,3,4}，A∩B={2,3}。

习题2：证明若A∩B=A∩C，且A∪B=A∪C，则B=C。

答案：首先，由A∩B=A∩C可得B⊆C，同理可得C⊆B，因此B=C。然后，由A∪B=A∪C可得B⊆C，同理可得C⊆B，因此B=C。综上所述，B=C。

1.2 命题逻辑

习题1：将下列命题用命题变元表示：

（1）如果今天下雨，那么我就带伞。

（2）要么他很聪明，要么他很勤奋。

答案：（1）命题变元P表示今天下雨，命题变元Q表示我带伞，命题可表示为P→Q。

（2）命题变元P表示他很聪明，命题变元Q表示他很勤奋，命题可表示为P∨Q。

习题2：判断下列命题是否为永真式、矛盾式或可满足式：

（1）(P∨Q)→(P∧Q) （2）(P→Q)∧(Q→P)

答案：（1）该命题为可满足式，因为当P为真，Q为假时，命题为真。

（2）该命题为永真式，因为无论P和Q取何值，命题都为真。

第二章：排列与组合

2.1 排列

习题1：从10个人中选取3个人，按照顺序排成一队，有多少种不同的结果？

答案：根据排列的计算公式，共有10×9×8=720种不同的结果。

习题2：从10个人中选取3个人，不考虑顺序，有多少种不同的结果？

答案：根据组合的计算公式，共有C(10,3)=120种不同的结果。

2.2 组合

习题1：证明组合恒等式C(n,k)=C(n,n-k)。

答案：根据组合的计算公式可得C(n,k)=C(n,n-k)，因此组合恒等式成立。

第一章答案 第二章答案 第三章答案 第四章答案

第一章答案

1．(a) 45 ( {1,6},{2,7},{3,8},…,{45,50} )

(b) 455+(4+3+2+1) = 235

( 126, 237, 348, …,454650, 464750, 474850,

484950, 4950 )

2．(a) 5!8!

(b) 7! P(8,5)

(c) 2 P(5,3) 8!

3. (a) n!P(n+1, m)

(b) n!(m+1)!

(c) 2!((m+n-2)+1)!

4. 2 P(24,5) 20!

5. 因首数字可分别为偶数或奇数，知结果为 25P(8,2)+34P(8,2).

6. (n+1)!-1

7. 用数学归纳法易证。

8. 两数的公共部分为240530, 故全部公因数均形如2m5n,个数为4131.

9. 设有素数因子分解 n=p1n11p2 n22…pk nkk, 则n2的除数个数为

( 2n1+1) (2n2+1) …(2nk+1).

10．1）用数学归纳法可证n能表示成题中表达式的形式；

2）如果某n可以表示成题中表达式的形式，则等式两端除以2取余数，可以确定a1；再对等式两端的商除以3取余数，又可得a2；对等式两端的商除以4取余数，又可得a3；…；这说明表达式是唯一的。 11．易用C(m,n)=m!/(n!(m-n)!)验证等式成立。

组合意义：

右：从n个不同元素中任取r+1个出来，再从这r+1个中取一个的全体组合的个数；

左：上述组合中，先从n个不同元素中任取1个出来，每一个相同的组合要生复 C(n-1,r) 次。

12．考虑,)1(,)1(1010nnkkknnnkkknxnxkCxxC求导数后有

令x=1, 即知.210nnkknnkC

【第 1 页 共 42 页】 第三章

3.12.一年级有100名学生参加中文，英语和数学的考试，其中92人通过中文考试，75人通过英语考试，65人通过数学考试；其中65人通过中，英文考试，54人通过中文和数学考试，45人通过英语和数学考试，试求通过3门学科考试的学生数。

[解].令：A1={通过中文考试的学生}

A2={通过英语考试的学生}

A3={通过数学考试的学生}

于是 |Z| =100，|A1|=92，|A2|=75，|A3|=65

|A1∩A2|=65，|A1∩A3|=54，|A2∩A3|=45

此题没有给出：

有多少人通过三门中至少一门；

有多少人一门都没通过。

但是由 max{ |A1|,|A2|,|A3| }=max{92,75,65}=92

故可以认为：

至少有92人通过三门中至少一门考试，即100≥|A1∪A2∪A3|≥92

至多有8人没通过一门考试，即0≤|1A∩2A∩3A| ≤8

于是，根据容斥原理，有

|A1∪A2∪A3|=(|A1|+|A2|+|A3|)-(|A1∩A2|+|A1∩A3|+|A2∩A3|)+|A1∩A2∩A3|

即 |A1∩A2∩A3|=|A1∪A2∪A3|-(|A1|+|A2|+|A3|)+(|A1∩A2|+|A1∩A3|+|A2∩A3|)

=|A1∪A2∪A3|-(92+75+65)+(65+54+45)

=|A1∪A2∪A3|-232+164

=|A1∪A2∪A3|-68

从而由 92-68≤|A1∪A2∪A3|-68≤100-68

即 24≤|A1∪A2∪A3|-68≤32

可得 24≤|A1∩A2∩A3| ≤32

故此，通过3门学科考试的学生数在24到32人之间。

也可用容斥原理，即

|1A∩2A∩3A|=|Z|-(|A1|+|A2|+|A3|)+(|A1∩A2|+|A1∩A3|+|A2∩A3|)-|A1∩A2∩A3|