第二章容斥原习题及解答.ppt

第二章容斥原理习题 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、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 A B C I II III 第二章容斥原理习题 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为相同字母的排列的集合 … Ak k+1：k 和k+1为相同字母的排列的集合 … A89：8和9为相同字母的排列的集合 123456789 参考答案 [解(续)] ?则所求即 参考答案 [解(续)] ? 故 为所求 第二章容斥原理习题 5、求从O(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为 的非负整数解集合。 参考答案 [解(续)] 设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类书全不在各自原来层次上的方案数有多少？（2）每层的n本书都不在原来位置上的方案数等于多少？（3）m层书都不在原来层次，每层n本书也不在原来位置上的方案数又有多少？ 参考答案 [解]