软件2010组合数学第四章容斥原理一

《软件2010组合数学第四章容斥原理一》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章容斥原理InclusionandExclusionPrinciple(包含排斥原理)主要内容§4.1容斥原理§4.2多重集的r-组合数§4.3错位排列§4.4有限制条件的排列问题§4.5有禁区的排列问题§4.6Möbius反演应用§4.1容斥原理是求解组合计数问题常用的工具之一是加法法则的推广它给出了用满足某些性质的元素个数来表示不满足这些性质的元素个数的计数公式。一、具有一种性质的情形解先求在1和500之间可以被5整除的个数有500÷5=100个，则不能被5整除的数有500－100=400个。例4.1.1求在1,2,…,500中不能被5

2、整除的数的个数。可以写成或者其中为A相对于S的补集.这个例子实际上用到如下原理：如果A是集合S的子集，则在A中的元素个数等于S的元素个数减去不在A中的元素个数。解：先求5和6相邻的七位数的个数N1.N1=2×6!×C(7,5)=30240不同数字的七位数有P(9,7)个，根据定理5.1,所求的七位数个数N=P(9,7)-N1=151200例4.1.3从{1,2,…,9}中取7个不同的数字构成七位数，如果不允许5和6相邻，问有多少种方法？二、具有两种性质的情形设S为有穷集,P1和P2分别表示两种性质。A1表示S中具有性质P1的子集。A2表示S中具

3、有性质P2的子集。则S中既不具有性质P1也不具有性质P2的元素个数为：例在1-n的全排列中，1不在第一个位置，并且2不在第二个位置的排列数是多少？三、具有三种性质的情形则S中既不具有性质P1也不具有性质P2也不具有性质P3的元素个数为：设S有穷集,P1P2P3分别表示三种性质。A1A2A3分别表示S中具有性质P1P2P3的子集。例4.1.2求在1-1000中不能被5,6,8整除的数的个数。解：令P1,P2和P3分别表示一个整数能被5，6和8整除的性质。S={x

4、x是整数并且1

5、x∈S⋀x具有性质Pi},i=1,2,3

6、.则有下面结果：

7、A1

8、=⌊1000/5⌋=200,

9、A2

10、=⌊1000/6⌋=166,

11、A3

12、=⌊1000/8⌋=125,

13、A1A2

14、=⌊1000/[5,6]⌋=⌊1000/30⌋=33

15、A1A3

16、=⌊1000/[5,8]⌋=⌊1000/40⌋=25

17、A2A3

18、=⌊1000/[6,8]⌋=⌊1000/24⌋=41

19、A1A2A3

20、=⌊1000/[5,6,8]⌋=⌊1000/120⌋=8根据定理4.1.1得上面问题的小结四、一般情形设S是有穷集，P1,P2,…,Pm是m个性质。对于性质pi(i=1,2,…,m),S中的任何一个元素x或具有或不具有

21、，两者必居其一。Ai表示S中具有性质pi的元素构成的子集。这时容斥原理可叙述为：定理4.1.1（容斥原理）S中不具有性质P1,P2,…,Pm的元素数是证明：（贡献法，思想）等式左边是S中不具有性质P1,P2,…，Pm的元素数。我们将要证明，对S中的任何一个元素x,如果x不具有性质P1,P2,…，Pm，则对等式右边的贡献为1；如果x至少具有其中的一条性质，则对等式右边的贡献为0。设x不具有性质P1,P2,…，Pm，所以xAi,i=1,2…,m.令T={1,2,…,m}.对T的所有的2-组合{i,j}都有xAiAj,对T的所有的3-组合{i,j,k

22、}都有xAiAjAk，…，直到xA1A1…Am,但xS,所以它对等式右边的贡献是1-0+0-0+…+(-1)m0=1.设x具有n条性质，n>=1.则x对

23、S

24、的贡献为1，对的贡献为n=,对的贡献为，对的贡献为所以x对等式右边的总贡献是：证明结束。1,推论在S中至少具有一条性质的元素数是证明：根据DeMorgan定律2,对称筛公式若性质P1,P2,…,Pm是对称的，即具有k个性质的事物个数不依赖于这k个性质的选取，总是等于同一个数值，则这个值称为公共数，记为N(k)。对称筛公式这样定理4.1.1就变成下面的形式：例４.1.6将20个学生分成不同的

25、3个组，每组至少有1个学生，求有多少种分法？解显然S是这20个学生不加以限制的分成3个不同组的方法的集合，则

26、S

27、=320。因为3个组是不同的，我们分别加以编号1，2，3。则性质P1,P2,P3分别表示1组，2组和3组为空。显然这三条性质是对称的，符合对称筛公式。有：N(1)=220,N(2)=1,N(3)=0,所以共有320-3×220+3=3483638676种分法。3,引入如下的记号：则定理4.1.1的公式可写成：定理4.1.2（Jordan公式）集合S中恰具有r(0≤r≤m)种性质的事物的个数（广义包含排斥原理）例４.1.5对50辆汽车

28、做氧化氮（NOx）、碳氢化合物（HC）和一氧化碳（CO）的污染物排放量的测试。其中，1辆汽车的排放量超过所有三种污染物的环境标准，3辆汽车NOx和HC