《第二章课后习题答案.doc》由会员分享，可在线阅读，更多相关《第二章课后习题答案.doc（3页珍藏版）》请在金锄头文库上搜索。
1、第二章 容斥原理课后习题答案1、某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇4次，每四人各相遇3次，每五人各相遇2次，每六人各相遇1次，一人也没有遇见的有5次，问某甲共参加了几次会议？解：设Ai为甲与i个朋友相遇的会议集合，i1, 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
2、+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作原料，问有多少种安排方案？（假定每种材料只做一种产品的原料）ABCIIIIII解：按题意可得如下的带禁区的棋盘，其中有阴影的表示禁区。棋盘多项式为R( )=R( )R( )=(1+x)(1+3x+x2)=1+4x+4x2+x3故方案数=3!4
3、2!+41!10!14、在由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=3*a, 3*b, 3*c的排列全体集合，则。设A1为重集B1=a, X, 3*b, 3*c的排列全体集合，A2为重集B2=3*a, b, Y, 3*c的排列全体集合，A3为重集B3=3*a,
4、 3*b, c, Z的排列全体集合，其中X=aa，Y=bb，Z=cc，则设A4为重集B4=a, X, b, Y, 3*c的排列全体集合，A5为重集B5=3*a, b, Y, c, Z的排列全体集合，A6为重集B6=a, X, 3*b, c, Z的排列全体集合，其中X=aa，Y=bb，Z=cc，则设A7为重集B7=a, X, b, Y, c, Z的排列全体集合，其中X=aa，Y=bb，Z=cc，则根据容斥原理，所求的排列数为1680-3980+3620-426=1745、求从O(0, 0)点到P(8, 4)点的路径数，已知(2, 1)到(4, 1)的线段，(3, 1)到(3, 2)的线段被封锁。
5、解：设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) 方案数为
