第二章课后习题答案

第二章容斥原理课后习题答案。

1、某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇4次，每四人各相遇3次，每五人各相遇2次，每六人各相遇1次，一人也没有遇见的有5次，问某甲共参加了几次会议？

解：设ai为甲与i个朋友相遇的会议集合，i＝1, 2, …6，根据题意，|a1|=12c(6, 1)，|a2|=6c(6, 2)，|a3|=4c(6, 3)，|a4|=3c(6, 4)，|a5|=2c(6, 5)，|a6|=1c(6, 6)，根据容斥原理，甲在会上至少遇见一位朋友的会议次数为。

甲在会上一人也没有遇见的有5次，根据加法法则，甲共参加会议次数为28+5=33。

2、求从1到500的整数中被3和5整除但不被7整除的数的个数。

解：令a3为1到500的整数中被3整除的数的集合，a5为1到500的整数中被5整除的数的集合，a7为1到500的整数中被7整除的数的集合。根据题意，所求的整数个数为。

3、a、b、c三种材料用作产品i、ii、iii的原料，但要求i禁止用b、c作原料，ii不能用b作原料，iii不允许用a作原料，问有多少种安排方案？（假定每种材料只做一种产品的原料）

解：按题意可得如下的带禁区的棋盘，其中有阴影的表示禁区。

棋盘多项式为。

r( )r( )r( )

(1+x)(1+3x+x2)=1+4x+4x2+x3

故方案数=3!－4×2!+4×1!－1×0!＝1

4、在由a, a, a, b, b, b, c, c, c组成的排列中，求满足下列条件的排列数。

a) 不存在相邻3元素相同；

b) 相邻两元素不相同。

解：(a) 设t为a, a, a, b, b, b, c, c, c的排列全体集合，则。

设a1：出现3个相邻a的排列的集合。

a2：出现3个相邻b的排列的集合。

a3：出现3个相邻c的排列的集合。

根据容斥原理，所求的排列数为。

b) 设t为重集b=的排列全体集合，则。

设a1为重集b1=的排列全体集合，a2为重集b2=的排列全体集合，a3为重集b3=的排列全体集合，其中x='aa'，y='bb'，z='cc'，则。

设a4为重集b4=的排列全体集合，a5为重集b5=的排列全体集合，a6为重集b6=的排列全体集合，其中x='aa'，y='bb'，z='cc'，则。

设a7为重集b7=的排列全体集合，其中x='aa'，y='bb'，z='cc'，则。

根据容斥原理，所求的排列数为。

5、求从o(0, 0)点到p(8, 4)点的路径数，已知(2, 1)到(4, 1)的线段，(3, 1)到(3, 2)的线段被封锁。

解：设s为o(0, 0)点到p(8, 4)点的所有路径的集合。则。

令a1表示s中经过线段(2, 1)→(3, 1)的路径。

a2表示s中经过线段(3, 1)→(4, 1)的路径。

a3表示s中经过线段(3, 1)→(3, 2)的路径，则。

根据容斥原理，有。

6、求满足条件的整数解的数目。

解：作变量代换。

则方程变为。

令p1为性质，p2为性质，p3为性质。

并设s为的非负整数解集合，ai为s中满足性质pi（i=1, 2, 3）的集合，则所求问题变成在s中计算。

7、n个单位各派两名代表去出席一会议。2n位代表围一圆桌坐下。试问：

a) 各单位代表并排坐着的方案是多少？

b) 各单位的两人互不相邻的方案数又是多少？

解：(a) 首先把n个单位的两名代表分别看作一个整体，进行圆排列，然后各单位的两名代表可分别进行换位，根据乘法法则，方案是方案数为(n-1)!2n。

b) 设第i单位代表相邻的方案集合为ai（i=1, 2, …n），根据容斥原理，所求方案数为。

8、一书架有m层，分别放置m类不同种类的书，每层n册。先将书架上的图书全部取出清理。清理过程要求不打乱所有的类别。试问：

1) m类书全不在各自原来层次上的方案数有多少？

2) 每层的n本书都不在原来位置上的方案数等于多少？

3) m层书都不在原来层次，每层n本书也不在原来位置上的方案数又有多少？

解：令错排数。

1) 方案数为。

2) 方案数为。

3) 方案数为。

第二章课后习题答案

第二章课后习题答案

第二章课后习题答案

微观第二章课后习题答案

其他用户还读了