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

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

2、在先求在1和和500之间可以被之间可以被5整除的个整除的个数有数有 500 5 =100个，则不能被个，则不能被5整除的整除的数有数有500100=400个。个。例例4.1.1 求在求在1,2,500中不能被中不能被5整除的数整除的数的个数。的个数。l 可以写成 或者 AASA 其中 为A相对于S的补集.ASA 这个例子实际上用到如下原理：这个例子实际上用到如下原理：如果如果A是集合是集合S的子集，则在的子集，则在A中的元素个数中的元素个数等于等于S的元素个数减去不在的元素个数减去不在A中的元素个数。中的元素个数。解：先求解：先求5和和6相邻的七位数的个数相邻的七位数的个数N1. N1=26!

3、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中既不具有性质中既不

4、具有性质P1也不具有性质也不具有性质P2的元素个数为：的元素个数为： 121212| |AASAAAA例例 在在1-n的全排列中，的全排列中，1不在第一个位置，并且不在第一个位置，并且2不在第二个位置的排列数是多少？不在第二个位置的排列数是多少？三、具有三种性质的情形三、具有三种性质的情形则则S中既不具有性质中既不具有性质P1也不具有性质也不具有性质P2也不具有性质也不具有性质P3的元素个数为：的元素个数为： 123123121323123| |AAASAAAAAAAAAAAA设设S有穷集有穷集, P1P2P3分别表示三种性质。分别表示三种性质。A1 A2 A3分别表示分别表示S中具有性质中具

5、有性质P1P2P3的子集。的子集。例例4.1.2 求在求在1-1000中不能被中不能被5,6,8整除的数的个数。整除的数的个数。解：令P1,P2和P3分别表示一个整数能被5，6和8整除的性质。 S=x|x是整数 并且1x=1.则x对|S|的贡献为1，对 的贡献为n= ,对 的贡献为 ，对 的贡献为 所以x对等式右边的总贡献是：证明结束。miiA1|1nmjijiAA1|2n|21mAAAmn)(0) 1(210) 1(210mnnnnnnmnnnnnm1,推论推论 在在S中至少具有一条性质的元素数是中至少具有一条性质的元素数是mkjikjimjijimiimAAAAAAAAA11121AAAm

6、m211) 1(|) 1(|211111212121mmmkjikjimjijimiimmmAAAAAAAAAAAASAAASAAA证明：根据证明：根据De Morgan定律定律|)0(|)(|)3(|)2(|)1(2121124213211312121SNAAANAAAmNAAAAAAAAANAAAAAANAAANmmmmmmmm2, 对称筛公式对称筛公式若性质P1,P2,Pm是对称的是对称的，即具有k个性质的事物个数不依赖于这k个性质的选取，总是等于同一个数值，则这个值称为公共数，记为N(k)。对称筛公式对称筛公式)() 1()() 1() 2 (2) 1 (1) 0 (1iNimNmNm

7、mNmNmNNmiim这样定理这样定理4.1.1就变成下面的形式：就变成下面的形式：例例.1.6 将将20个学生分成不同的个学生分成不同的3个组，每组至个组，每组至少有少有1个学生，求有多少种分法？个学生，求有多少种分法？ 解解 显然S是这20个学生不加以限制的分成3个不同组的方法的集合，则|S|=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, 引入如下的记号：引入如下

8、的记号：则定理4.1.1的公式可写成：|)(|)2(|) 1 (|)0(2111mmjijimiiAAAmWAAWAWSW)() 1() 3()2() 1 ()0(|21mWWWWWAAAmm定理定理4.1.2（Jordan公式）公式） 集合 S中恰具有r(0r m)种性质的事物的个数 （广义包含排斥原理）（广义包含排斥原理）)() 1()() 1() 2(2) 1(1)()(0irWrirmWrmrWrrrWrrrWrNrmiirm例例.1.5 对对50辆汽车做氧化氮（辆汽车做氧化氮（NOx）、碳氢）、碳氢化合物（化合物（HC）和一氧化碳（）和一氧化碳（CO）的污染物排）的污染物排放量的测试

9、。其中，放量的测试。其中，1辆汽车的排放量超过所辆汽车的排放量超过所有三种污染物的环境标准，有三种污染物的环境标准，3辆汽车辆汽车NOx和和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)

10、=3+2+1=6，W(3)=1,则根据定理4.1.2有 =13-26+31=4.因此，有4辆汽车正好超出1种污染物的环境标准。) 3(13)2(12) 1 () 1 (WWWN例例.4设设n n是正整数是正整数,n=2,n=2,欧拉函数欧拉函数 表示小于表示小于n n且与且与n n互质的正整数的个数。互质的正整数的个数。求求 的表达式。的表达式。 解：任何大于等于解：任何大于等于2 2的正整数的正整数n n都有如下的都有如下的分解形式：分解形式：其中其中p p1 1,p,p2 2, ,p pk k为质数。令为质数。令 S=x|x是小于等于是小于等于n的正整数的正整数， Ai=x

11、|xS pi整除整除x, i=1,2, k.)(n,2121kkpppn)(n则有下面的结果：|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得： )1111 (11 (1)1()11()111()1(|)(212112121211121kkkkkkkkljijikiikpppnpppnppppnpppnnpppnppnpnnAAAn（）例如：例如：30=235，则，则即与即与30互质的正整数有互质的正整数有8个，分别是个，

12、分别是1,7,11,13, 17,19,23,29.8)511 ()311 ()211 (30)30(软件组合数学第四章容斥原理一 rmnmm) 1(r1n1mrn0mmrmnm例例4.1.5 证明以下等式，证明以下等式，其中其中n,r,m为正整数，为正整数，mrnmrn软件组合数学第四章容斥原理一证明：令证明：令S=1,2,n, A=1,2, ,m,等式左边等式左边表示从表示从S中选取包含着中选取包含着A的的r-子集的方法数子集的方法数N.设设Pj表示在表示在S的的r-子集中不包含子集中不包含j的性质，的性质， Aj是具有是具有性质性质Pj的的S的的r-子集的集合。那么有子集的集合。那么有r

13、mnAAAmjirnAAmjrnAmjij|)1(2|)1(1|21软件组合数学第四章容斥原理一由定理由定理4.1.1得：得：rmnmmrnmrnmrnmrmnmmrnmrnmrnAAANmmm)1(22110)1(2211|21例例4.2.1 4.2.1 确定多重集确定多重集S=3S=3a,4a,4b,5b,5cc的的10-10-组合数。组合数。 4.2 多重集的多重集的r-组合数组合数 求多重集求多重集S=nS=n1 1a a1 1, n, n2 2a a2 2, , ,n,nk ka ak k r- r-组合数组合数 假定每个假定每个n ni irr，i=1,2,i=1,2,n.,n.

14、用容斥原理求用容斥原理求S S的的r-r-组合数，组合数， 第五章将介绍另外一种方法第五章将介绍另外一种方法- -生成函数的方法生成函数的方法解：令解：令T= a,a, b b， cc ,T的所有的所有10-组合构成组合构成集合集合W,根据定理根据定理3.3.3得：得： 任取任取T的一个的一个10-组合，组合，如果其中的如果其中的a多于多于3个，则称它具有性质个，则称它具有性质P1;如果其中的如果其中的b多于多于4个，则称它具有性质个，则称它具有性质P2;如果其中的如果其中的c多于多于5个，则称它具有性质个，则称它具有性质P3，因此因此S的的10-组合数就是组合数就是W中同时不具有性质中同时不

15、具有性质P1,P2和和P3的元素个数，即的元素个数，即W中同时满足中同时满足a的个数小于等于的个数小于等于3，b的个数小于等于的个数小于等于4， 并且并且c的个数小于等于的个数小于等于5的的10-组合个数。组合个数。662121012101103|W令令Ai= x|x W并且并且x具有性质具有性质PiA1中的每个中的每个10-组合至少含有组合至少含有4个个a, 把把4个个a拿走就得到拿走就得到T的一个的一个6-组合。反之，对组合。反之，对T的的任意一个任意一个6-组合加上组合加上4个个a就得到就得到A1的一个的一个10-组合，所以组合，所以|A1|就是就是T的的6-组合数，即组合数，即 同理可得：同理可得：2828686163|1A2127575153|2A1526464143|3A用类似的方法可以计算用类似的方法可以计算所以所以S的的10-组合数为组合数为. 6001315212866|. 0| , 0|, 30103|,