容斥原理习题及解答.ppt

第二章容斥原理习题,1、某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇4次，每四人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议？,参考答案,解设Ai为甲与第i个朋友相遇的会议集，i1，6则故甲参加的会议数为:28+5=33.,第二章容斥原理习题,2、求从1到500的整数中被3和5整除但不被7整除的数的个数.,参考答案,解设A3：被3整除的数的集合A5：被5整除的数的集合A7：被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!42!+41!10!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)考虑9个字母的一个排列设A12：1和2为相同字母的排列的集合A23：2和3为相同字母的排列的集合Akk+1：k和k+1为相同字母的排列的集合A89：8和9为相同字母的排列的集合,参考答案,解(续)则所求即,参考答案,解(续)故为所求,第二章容斥原理习题,5、求从O(0,0)点到(8,4)点的路径数，已知(2,1)到(4,1)的线段，(3,1)到(3,2)的线段被封锁。,参考答案,解设S为O(0,0)点到(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-1)!2n（b）设第i单位代表相邻的方案数为Ai（i=1,2,n）则所求为,第二章容斥原理习题,8、一书架有m层，分别放置m类不同种类的书，每层n册。先将书架上的图书全部取出清理。清理过程要求不打乱所有的类别。试问:（1）m类书全不在各自原来层次上的方案数有多少？（