软件2010组合数学第四章容斥原理(一).ppt

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

2、数的个数。,可以写成 或者,其中 为A相对于S的补集.,这个例子实际上用到如下原理： 如果A是集合S的子集，则在A中的元素个数等于S的元素个数减去不在A中的元素个数。,解：先求5和6相邻的七位数的个数N1. N1=26!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中具有性质P2的子集。,则S中

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

4、 |A2|= 1000/6 =166, |A3|= 1000/8 =125,|A1 A2|= 1000/ 5,6 = 1000/30 =33 |A1 A3|= 1000/ 5,8 = 1000/40 =25 |A2 A3|= 1000/ 6,8 = 1000/24 =41 | A1 A2 A3|= 1000/ 5,6,8 = 1000/120 =8 根据定理4.1.1得,上面问题的小结,四、一般情形 设S是有穷集， P1, P2,Pm是m个性质。对于性质pi (i=1,2,m),S中的任何一个元素x或具有或不具有，两者必居其一。 Ai表示S中具有性质pi的元素构成的子集。,这时容斥原理可叙述为

5、： 定理4.1.1 （容斥原理） S中不具有性质P1, P2,Pm的元素数是,证明：（贡献法，思想） 等式左边是S中不具有性质P1, P2,，Pm的元素数。我们将要证明，对S中的任何一个元素x, 如果x不具有性质P1, P2,，Pm，则对等式右边的贡献为1；如果x至少具有其中的一条性质，则对等式右边的贡献为0。 设x不具有性质P1, P2,，Pm，所以x Ai, i=1,2 ,m.令T=1,2, ,m.对T的所有的2-组合i,j都有x Ai Aj,对T的所有的3-组合i,j,k都有x Ai Aj Ak ， ，直到 x A1 A1 Am ,但x S,所以它对等式右边,的贡献是1-0+0-0+(-

6、1)m0=1. 设x具有n条性质，n=1.则x对|S|的贡献为1， 对 的贡献为n= ,对 的贡 献为 ，对 的贡献为 所以x对等式右边的总贡献是： 证明结束。,1,推论 在S中至少具有一条性质的元素数是,证明：根据De Morgan定律,2, 对称筛公式 若性质P1,P2,Pm是对称的，即具有k个性质的事物个数不依赖于这k个性质的选取，总是等于同一个数值，则这个值称为公共数，记为N(k)。,对称筛公式,这样定理4.1.1就变成下面的形式：,例.1.6 将20个学生分成不同的3个组，每组至少有1个学生，求有多少种分法？,解 显然S是这20个学生不加以限制的分成3个不同组的方法的集合，则|S|=

7、320。因为3个组是不同的，我们分别加以编号1，2，3。则性质P1, P2, P3分别表示1组，2组和3组为空。显然这三条性质是对称的，符合对称筛公式。有： N(1)=220, N(2)=1, N(3)=0, 所以共有320-3220+3=3483638676种分法。,3, 引入如下的记号： 则定理4.1.1的公式可写成：,定理4.1.2（Jordan公式） 集合 S中恰具有r(0r m)种性质的事物的个数 （广义包含排斥原理）,例.1.5 对50辆汽车做氧化氮（NOx）、碳氢化合物（HC）和一氧化碳（CO）的污染物排放量的测试。其中，1辆汽车的排放量超过所有三种污染物的环境标准，3辆汽车NO

8、x和HC超标，2辆汽车NOx和CO超标，1辆汽车HC和CO超标，6辆汽车NOx超标，4辆汽车HC超标，3辆汽车CO超标 （1）计算有多少辆汽车符合所有三种污染物的环境标准？ （2）求有多少辆汽车正好超出1种污染物的环境标准？,解 即我们要求的是N(1). 容易计算：W(1)=6+4+3=13，W(2)=3+2+1=6，W(3)=1, 则根据定理4.1.2有 =13-26+31=4.因此，有4辆汽车正好超出1种污染物的环境标准。,例4.1.4设n是正整数,n=2,欧拉函数 表示小于n且与n互质的正整数的个数。求 的表达式。 解：任何大于等于2的正整数n都有如下的分解形式： 其中p1,p2,pk为

9、质数。令 S=x|x是小于等于n的正整数， Ai=x|xS pi整除x, i=1,2, k.,则有下面的结果： |S|=n， |Ai|= n/pi =n/pi i=1,2, k |Ai Aj|= n/pi,pj =n/(pipj) 1ij k |A1 A2 Ak |= n/p1,p2,pk =n/(p1p2 pk),由定理4.1.1得：,例如：30=235，则 即与30互质的正整数有8个，分别是1,7,11,13, 17, 19,23,29.,例4.1.5 证明以下等式， 其中n,r,m为正整数，mrn,证明：令S=1,2,n, A=1,2, ,m,等式左边表示从S中选取包含着A的r-子集的方

10、法数N.设Pj表示在S的r-子集中不包含j的性质， Aj是具有性质Pj的S的r-子集的集合。那么有,由定理4.1.1得：,例4.2.1 确定多重集S=3a,4b,5c的10-组合数。, 4.2 多重集的r-组合数,求多重集S=n1a1, n2a2, ,nkak r-组合数 假定每个nir，i=1,2,n. 用容斥原理求S的r-组合数， 第五章将介绍另外一种方法-生成函数的方法,解：令T= a, b， c ,T的所有10-组合构成集合W,根据定理3.3.3得： 任取T的一个10-组合， 如果其中的a多于3个，则称它具有性质P1; 如果其中的b多于4个，则称它具有性质P2; 如果其中的c多于5个，

11、则称它具有性质P3， 因此S的10-组合数就是W中同时不具有性质P1,P2和P3的元素个数，即W中同时满足a的个数小于等于3，b的个数小于等于4， 并且c的个数小于等于5的10-组合个数。,令Ai= x|xW并且x具有性质Pi A1中的每个10-组合至少含有4个a, 把4个a 拿走就得到T的一个6-组合。反之，对T的 任意一个6-组合加上4个a就得到A1的一个 10-组合，所以|A1|就是T的6-组合数，即 同理可得：,用类似的方法可以计算 所以S的10-组合数为,列出这6个10-组合如下： 1a,4b,5c， 2a,3b,5c， 2a,4b,4c 3a,2b,5c， 3a,3b,4c， 3a,4b,3c,多重集的r组合数等于方程的非负整数解的个数。 用容斥原理来确定方程的非负整数解的个数,例4.2.2 确定方程 x1+x2+x3=12 (-1 x1 2, 1 x2 5, 2 x3 7) 的整数解的个数.,解：令y1= x1+1