资源描述：
《容斥原理习题及解答.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章容斥原理习题1、某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇4次，每四人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议？参考答案[解]设Ai为甲与第i个朋友相遇的会议集，i＝1，…，6．则故甲参加的会议数为:28+5=33.第二章容斥原理习题2、求从1到500的整数中被3和5整除但不被7整除的数的个数.参考答案[解]设A3：被3整除的数的集合A5：被5整除的数的集合A7：被7整除的数的集合 所以第二章容斥原理习题3、
2、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!＝1ABCIIIIII第二章容斥原理习题4、在由a,a,a,b,b,b,c,c,c组成的排列中，求满足下列条件的排列数。(a)不存
3、在相邻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为相同字母的排列的集合123456789参考答案[解(续)]则所求即参考答案[解(续)]故为所求第二章容斥原理习题5、求从O(
4、0,0)点到(8,4)点的路径数，已知(2,1)到(4,1)的线段，(3,1)到(3,2)的线段被封锁。参考答案[解]设S为O(0,0)点到(8,4)点的所有路径的集合。则（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为的非负整
5、数解集合。参考答案[解(续)]设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册。先将书架上的图书全部取出清理。清理过程要
6、求不打乱所有的类别。试问:（1）m类书全不在各自原来层次上的方案数有多少？ （2）每层的n本书都不在原来位置上的方案数等于多少？ （3）m层书都不在原来层次，每层n本书也不在原来位置上的方案数又有多少？参考答案[解]
