《容斥原理习题及解答.ppt》由会员分享，可在线阅读，更多相关《容斥原理习题及解答.ppt（23页珍藏版）》请在金锄头文库上搜索。
1、第二章容斥原理习题第二章容斥原理习题l1、 某甲参加一种会议，会上有某甲参加一种会议，会上有6位朋友，位朋友，某甲和其中每人在会上各相遇某甲和其中每人在会上各相遇12次，每次，每二人各相遇二人各相遇6次，每三人各相遇次，每三人各相遇4次，每次，每四人各相遇四人各相遇3次，每五人各相遇次，每五人各相遇2次，每次，每六人各相遇一次，六人各相遇一次，1人也没有遇见的有人也没有遇见的有5次，问某甲共参加了几次会议次，问某甲共参加了几次会议 ？参考答案参考答案l解 设设Ai为甲与第为甲与第i个朋友相遇的会议个朋友相遇的会议集，集，i1，6则则l故甲参加的会议数为故甲参加的会议数为:28+5=33.第二章
2、容斥原理习题第二章容斥原理习题l2、求从求从1到到500的整数中被的整数中被3和和5整除但不整除但不被被7整除的数的个数整除的数的个数.参考答案参考答案l解 l设设 A3：被：被3整除的数的集合整除的数的集合A5：被：被5整除的数的集合整除的数的集合A7：被：被7整除的数的集合整除的数的集合所以所以第二章容斥原理习题第二章容斥原理习题l3、A、B、C三种材料用作产品三种材料用作产品I、II、III的原料，但要求的原料，但要求I禁止用禁止用B、C作原料，作原料，II不能用不能用B作原料，作原料，III不允许用不允许用A作原料，作原料，问有多少种安排方案？（假定每种材料问有多少种安排方案？（假定每
3、种材料只做一种产品的原料）只做一种产品的原料）参考答案参考答案l解 按题意可得如下的带禁区的棋盘按题意可得如下的带禁区的棋盘,其其中有阴影的表示禁区中有阴影的表示禁区l棋盘多项式为棋盘多项式为lR()=R()R()=(1+x)(1+3x+x2)=1+4x+4x2+x3故方案数故方案数3!42!+41!10!1ABCIIIIII第二章容斥原理习题第二章容斥原理习题l4、在由在由a,a,a,b,b,b,c,c,c组成的排列中，组成的排列中，求满足下列条件的排列数。求满足下列条件的排列数。l(a)不存在相邻不存在相邻3元素相同；元素相同；l(b)相邻两元素不相同。相邻两元素不相同。参考答案参考答案l
4、解 (a)设设T为为a,a,a,b,b,b,c,c,c的排列全体，的排列全体，则则l设设 A1：出现：出现3个相邻个相邻a的排列的集合的排列的集合A2：出现：出现3个相邻个相邻b的排列的集合的排列的集合A3：出现：出现3个相邻个相邻c的排列的集合的排列的集合则所求即则所求即参考答案参考答案l解 (b)考虑考虑9个字母的一个排列个字母的一个排列l设设lA12：1和和2为相同字母的排列的集合为相同字母的排列的集合A23：2和和3为相同字母的排列的集合为相同字母的排列的集合llAkk+1：k和和k+1为相同字母的排列的集合为相同字母的排列的集合llA89：8和和9为相同字母的排列的集合为相同字母的排
5、列的集合123456789参考答案参考答案l解(续) 则所求即则所求即参考答案参考答案l解(续) l故故l为所求为所求第二章容斥原理习题第二章容斥原理习题l5、求从求从O(0,0)点到点到(8,4)点的路径数，已点的路径数，已知知(2,1)到到(4,1)的线段，的线段，(3,1)到到(3,2)的线的线段被封锁。段被封锁。参考答案参考答案l解设设S为为O(0,0)点到点到(8,4)点的所有路径的点的所有路径的集合。则集合。则（0，0）（8，4）参考答案参考答案l解(续)令令lA1表示表示S中经过线段中经过线段(2,1)-(3,1)的路径的路径lA2表示表示S中经过线段中经过线段(3,1)-(4,
6、1)的路径的路径lA3表示表示S中经过线段中经过线段(3,1)-(3,2)的路径的路径l则则参考答案参考答案l解(续)l故所求路径数为故所求路径数为第二章容斥原理习题第二章容斥原理习题l6、求满足条件求满足条件l的整数解的数目。的整数解的数目。参考答案参考答案l解作变量代换作变量代换l则方程变为则方程变为l令令P1为性质为性质，P2为性质为性质，P3为为性质性质l并设并设S为为的非负整数解集合。的非负整数解集合。参考答案参考答案l解(续)l设设Ai为为S中满足性质中满足性质Pi（i=1,2,3）的集合。）的集合。l则所求问题变成在则所求问题变成在S中计算中计算参考答案参考答案l解(续)l类似可
7、得类似可得第二章容斥原理习题第二章容斥原理习题l7、n个单位各派两名代表去出席一会议。个单位各派两名代表去出席一会议。2n位代表围一圆桌坐下。试问：位代表围一圆桌坐下。试问：（a）各单位代表并排坐着的方案是多少）各单位代表并排坐着的方案是多少？（b）各单位的两人互不相邻的方案数又）各单位的两人互不相邻的方案数又是多少？是多少？参考答案参考答案l解（a）方案数为）方案数为(n-1)!2nl（b）设第）设第i单位代表相邻的方案数为单位代表相邻的方案数为Ai（i=1,2,n）l则所求为则所求为第二章容斥原理习题第二章容斥原理习题l8、一书架有一书架有m层，分别放置层，分别放置m类不同种类的书，类不同种类的书，每层每层n册。先将书架上的图书全部取出清理。册。先将书架上的图书全部取出清理。清理过程要求不打乱所有的类别。试问清理过程要求不打乱所有的类别。试问:（1）m类书全不在各自原来层次上的方案数有类书全不在各自原来层次上的方案数有多少？多少？（2）每层的）每层的n本书都不在原来位置上的方案数本书都不在原来位置上的方案数等于多少？等于多少？（3）m层书都不在原来层次，每层层书都不在原来层次，每层n本书也不本书也不在原来位置上的方案数又有多少？在原来位置上的方案数又有多少？参考答案参考答案l解
