容斥原理初步

1、第三章 容斥原理与鸽巢原理1第三章 容斥原理与鸽巢原理ABAB容斥原理Inclusion and Exclusion Principle计数时重叠部分不能被重复计算若 |A| = m , |B| = n , AB = , 则 |AB| = m + n 。容斥的计数思想是:先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来；然后再把计数时重复计算的数目排斥出去；使得计算的结果既无遗漏又无重复。 23.1 容斥原理引论例 1，20中2或3的倍数的个数解 2的倍数是：2，4，6，8，10，12，14，16，18，20。 10个3的倍数是：3，6，9，12，15，18。 6个但答案不是10

2、+6=16 个，因为6，12，18在两类中重复计数，应减去。故答案是：16-3=133若A和B是集合U的子集，补集complement德摩根De Morgan定理(a)(b)3.1 容斥原理引论UBA4证：(a)的证明。设 ,则 相当于 和 同时成立，亦即 (1)反之，若故(2)由（1）和（2）得(b)的证明和(a)类似，从略.(a)53.1 容斥原理引论DeMogan定理的推广：设A1,A2, . An是U的子集,证:采用数学归纳法正确即定理对n+1也是正确的。63.2 容斥原理最简单的计数问题是求有限集合A和B的并的元素数目。(1)证若AB=，则 | AB |= |A| + |B| A |

3、 A ( BB) | | (AB)(AB)| | AB | + | AB | ( 1 )同理| B | | BA | + | BA | ( 2 )| AB |(A( BB)(B(AA)|(AB)(AB)(BA)(BA)| AB| + |AB | + | BA| ( 3 )(3)-(2)-(1) 得到| AB | A | B | AB| + |AB | + | BA| ( | AB | + | AB | )( | BA | + | BA | ) | AB | AB | A | + | B | AB |73.2 容斥原理定理：(2)83.2 容斥原理93.2 容斥原理进一步可推出：10定理设C(n

4、,k)是1,n的所有k-子集的集合, 则证: 分析C(n,k)，可根据包含不包含n划分成两部分 包含n的可看做C(n-1,k-1)中每个子集再加上元素n； 不包含n的由C(n-1,k)组成；对n用归纳法。n=2时，等式成立。 假设对n - 1，等式成立。对于n有C(2,k) = 1 2 k=1时 1 2 k=2时C(3,k) = 1 2 3 k=1时 1 21 32 3 k=2时 1 2 3 k=3时k2C(3,2) = 1 32 31 211证由于最后一项第一项123.2 容斥原理此定理也可表示为：(4)133.2 容斥原理其中N是集合U的元素个数，即不属于A的元素个数等于集合的全体减去属于

5、A的元素的个数。一般有：(5)14Inclusion-Exclusion Principle计算不在 A1 也不在 A2中的元素个数若x不属于A1 或A211-0-0+0 = 1若x 属于A1 但不属于A201-1-0+0 = 0若x 属于A2 但不属于A101-0-1+0 = 0若x 属于A2 且属于A101-1-1+1 = 0两边相等15计算不满足任意属性的元素.x不满足任何属性11-0-0+(-1)m0 = 1x只满足1个属性01-1-0 +(-1)m0 = 0 x只满足n个属性, nm0C(n,0)-C(n,1)+C(n,2)+(-1)mC(n,m)= C(n,0)-C(n,1)+C(

6、n,2)+(-1)nC(n,n) +0 +0=0两边相等，同样计算不满足任何属性的元素个数(x+y)m =C(m,0)xm+ C(m,1)xm-1y+C(m,m)ymIf x=1, y=-10 = C(m,0)- C(m,1) +(-1)mC(m,m)163.2 容斥原理容斥原理指的就是（4）和（5）式。(4) (5)17Inclusionexclusion principle This concept is attributed toAbraham de Moivre(1718) It first appears in a paper ofDaniel da Silva(1854) Late

7、r in a paper byJ. J. Sylvester(1883) One of the most useful principles of enumeration in discrete probability and combinatorial theory is the celebrated principle of inclusionexclusion. When skillfully applied, this principle has yielded the solution to many a combinatorial problem. 18193.2 容斥原理例 一个

8、学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？令：M为修数学的学生集合；P 为修物理的学生集合； C 为修化学的学生集合；即学校学生数为336人。193.3 举例 例1 求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。解：6个字母全排列： |S| = 6!设A为ace作为一个元素出现的排列集: |A|=4!， B为 df作为一个元素出现的排列集: |B|=5!， AB为同时出现ace、df的排列数:

9、 |AB |=3!。 203.3 举例 例2 求从1到500的整数中能被3或5除尽的数的个数。 解： 令A为从1到500的整数中被3除尽的数的集合， B为被5除尽的数的集合被3或5除尽的数的个数为213.3 举例 例3 求由a,b,c,d四个字母构成的n位符号串中，a,b,c都至少出现一次的符号串数目。 解：令A、B、C分别为n位符号串中不出现a，b，c符号的集合。由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是3n个，即： a，b，c至少出现一次的n位符号串集合即为223.3 举例 例5。用26个英文字母作不允许重复的全排列，要求排除dog，g

10、od，gum，depth，thing字样的出现，求满足这些条件的排列数。 解：令A1为出现dog，| A1 |=24！ 令A2为出现god，| A2 |=24！ 令A3为出现gum，| A3 |=24！ 令A4为出现depth，| A4 |=22！ 令A5为出现thing，| A5 |=22！| A1A2| = 0, A1A3, dogum: | A1A3| = 22!, A2A4, godepth: | A2A4| = 20!, A2A5, thingod: | A2A5| = 20!, A3A4, gum*depth或者gum*depth : | A3A4| = 20！A3A5, thin

11、gum: | A3A5| = 20！A4A5, depthing: | A4A5| = 19!, A1A3 A4,dogumdepth 0; A2A4 A5, godepthing 0;A3A4 A5, depthingum | A3A4 A5 | = 17！所求的排列数为 26!-(3*24!+2*22!)+(22!+4*20!+19!)-(17!)233.3 举例0 00 11 01 1f(x1,x2)f10000f20001f30010f40011f50100f60101f70110f80111f91000f101001f111010f121011f131100f141101f15111

12、0f161111例6。求完全由n个布尔变量确定的布尔函数的个数。f(x1,x2,xn)中n个布尔变量的不同的状态数为2n每个状态有0，1两种取值，故f(x1,x2,xn)的布尔函数个数为 24例6。求完全由n个布尔变量确定的布尔函数的个数。解：设 布尔函数类为： 有1个变量不出现的布尔函数个数为有2个变量不出现的布尔函数个数为 有k个变量不出现的布尔函数个数为 根据容斥原理，满足条件的函数数目为：f(x1,x2,xn)的布尔函数个数为253.3 举例0 00 11 01 1f(x1,x2)f10000f20001f30010f40011f50100f60101f70110f80111f9100

13、0f101001f111010f121011f131100f141101f151110f161111例6。求完全由n个布尔变量确定的布尔函数的个数。f(x1,x2,xn)中n个布尔变量的不同的状态数为2n每个状态有0，1两种取值，故f(x1,x2,xn)的布尔函数个数为 26273.3 举例例4。求不超过120的素数个数。因112=121，故不超过120的合数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。 设Ai为不超过120的数 i的倍数集， i=2，3，5，7。2728注意：因为27个数中排除了2，3，5，7四个素数，又包含了1这个非素数。故所求的不超过120的

14、素数个数为： 27+4-1=3028 例7。欧拉函数(n)是求小于n且与n互素的数的个数。分析的化身欧拉进行计算看起来毫不费劲儿，就像人进行呼吸，像鹰在风中盘旋一样。他是历史上最多产的数学家。彼得堡学院为了整理他的著作整整花了47年。欧拉确实常常在两次叫他吃晚饭的半小时左右的时间里赶出一篇数学论文欧拉是史上发表论文数第二多的数学家，全集共计75卷；他的纪录一直到了20世纪才被保羅埃尔德什打破 “读欧拉的著作吧，在任何意义上，他都是我们的大师” 人生波折：失明，火灾1783年9月18日，他77岁的时候，欧拉写出了他对天王星轨道的计算。他在喝着茶跟孩子玩的时候，中风发作。手中烟斗掉了，只说出一句话

15、我要死了,欧拉便停止了生命和计算。在计算机领域中广泛使用的RSA公钥密码算法也正是以欧拉函数为基础的。-拉普拉斯293.3 举例 例7。欧拉函数(n)是求小于n且与n互素的数的个数。解：若n分解为不同素数的乘积 设1到n的n个数中为pi倍数的集合为Ai(8)=48 = 23，小于8且与8互素有1 3 5 7对于pipj, AiAj既是pi的倍数也是pj的倍数。30例7续。欧拉函数(n)是求小于n且与n互素的数的个数。即比60小且与60无公因子的数有16个：7，11，13，17，19，23，29，31，37，41，43，47，49，53，59，此外还有一个1。(8)=8(1-1/2) = 4 8

16、 = 23，小于8且与8互素有1 3 5 731例 求不定方程x1+x2+x3=15,求整数解的数目。其中附加约束为0 x1 5, 0 x2 6； 0 x3 7,32例 求不定方程x1+x2+x3=15,附加约束为0 x1 5, 0 x2 6； 0 x3 7,求整数解的数目。解：对于x1+x2+xn=r的非负整数解的个数为C(n+r-1,r)没有约束情况下的不定方程x1+x2+x3=15的非负整数解的个数为C(15+3-1,15)= C(17,2)设A1为x16的解， y1+6+x2+x3=15|A1|= C(9+3-1,9)= C(11,2)设A2为x27的解， x1+y2+7+x3=15|

17、A2|= C(8+3-1,8)= C(10,2)设A3为x38的解，x1+x2+ y3+8=15|A3|= C(7+3-1,7)= C(9,2)A1A2: y1+6+y2+7+x3=15 |A1A2|= C(2+3-1,2)= C(4,2)A1A3: y1+6+x2+y3+8=15 |A1A3|= C(1+3-1,1)= C(3,1)A2A3: x1+y2+7+y3+8=15 |A2A3|= 1A1A2 A3 : y1+6+y2+7+y3+8=15; |A1A2 A3 |= 0|A1A2 A3|=C(17,2) C(11,2)-C(10,2)-C(9,2) +C(4,2)+C(3,1)+1=1

18、0333.7 容斥原理应用举例例 求不定方程x1+x2+x3=15,附加约束为0 x15, 0 x26； 0 x37,求整数解的数目。解2: 1=5-x1, 2=6-x2, 3=7-x31+ 2 + 3 =5-x1+6-x2+7-x3=18-(x1+x2+x3) = 3, 1+ 2 + 3 =3 1, 2, 30的非负整数解个数。C(3+3-1,3) = 10教材：例3-18，pp13834讨论例:求不定方程x1+x2+x3=15,附加约束为0 x1 10, 0 x2 10； 0 x3 10,求整数解的数目1=10-x1, 2=10-x2, 3=10-x31+ 2 + 3 =10-x1+10-

19、x2+10-x3=15, 1, 2, 301+ 2 + 3 =15 1, 2, 30 x1+x2+x3=15 0 x1,x2,x3 10显然不成立,所以原解法不具有通用性应加上约束条件整数解个数相等?11+2+2=15 1=11 2=2 3=2 找不到对应的x1,x2,x3 1=10-x1, 2=10-x2, 3=10-x3 0 1, 2, 3 1035讨论x1+x2+x3=S0 x1 m1, 0 x2 m2； 0 x3 m31=m1-x1, 2=m2-x2, 3=m3-x31+ 2 + 3 =m1+m2+m3-S0 1 m1, 2 m2, 3 m3若m1+m2+m3-S min(m1,m2,

20、m3)则x1+x2+x3=S 0 x1 m1, 0 x2 m2； 0 x1 m31+ 2 + 3 =m1+m2+m3-S 1, 2, 30整数解个数相等363.3 举例例8: 错排问题: n个元素依次给以标号1，2，n。n个元素的全排列中，求每个元素都不在自己原来位置上的排列数。设Ai为数i在第i位上的全体排列，i=1，2，n。因数字i不能动，因而有：|Ai|=(n-1)! |AiAj |=(n-2)!每个元素都不在原来位置的排列数为37例9 在8个字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四个字母不在原来位置上的排列数目。解：8个字母的全排列中，令AA,AC,AE,AG

21、分别表A,C,E,G在原来位置上的排列，则错排数为：38求8个字母A,B,C,D,E,F,G,H的全排列中只有4个不在原来位置的排列数。解：8个字母中只有4个不在原来位置上，其余4个字母保持不动，相当于4个元素的错排，其数目为 故8个字母的全排列中有4个不在原来位置上的排列数应为：C(8,4)9=630393.4 棋盘多项式和有限制排列有限制排列例4个x ，3个y，2个z的全排列中，求不出现xxxx，yyy，zz图象的排列。解设出现xxxx的排列的集合记为A1， |A1|= =60; 设出现yyy的排列的集合记为A2， | A2|= =105； 设出现zz的排列的集合记为A2， | A3|=

22、=280； |A1A2|= =12； |A1A3|= =20； |A2A3|= =30； |A1A2A3|=3!=6； 全排列的个数为： 9!/(4!*3!*2!) =1260；所以： |A1A2A3|=1260(60+105+280)+(12+20+30)6 =871403.4 棋盘多项式和有限制排列棋盘多项式n个不同元素的一个全排列可看做n个相同的棋子在nn的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子non-attacking rooks xxxxx 如图所示的布局对应于排列41352。1 2 3 4 5P1P2P3P4P5413.4 棋盘多项式和有限制排列 可以把棋盘的形状

23、推广到任意形状：r1( )=1，r1( )=2，r1( )=2，r2( )=0，r2( )=1。令r k（C）表示k个棋子布到棋盘C上的方案数。如：423.4 棋盘多项式和有限制排列定义 设C为一棋盘，称R(C)= rk(C) xk为C的棋盘多项式。规定 r0(C)=1，包括C=时。k=0 n性质1:设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘，则 rk(C)=rk1(Ci)rk(Ce)对任一指定的格子，要么布子，方案数为 rk-1(Ci)；要么不布子，方案数为 rk(Ce)。*CiCe433.4 棋盘多项式和有限制排列 r0(C)1 ?设C有n个格子

24、，则 r1(C)nr1(C)r0(Ci) + r1(Ce)，r1(Ce)n1 r0(Ci)1故规定 r0(C)1是合理的443.4 棋盘多项式和有限制排列该性质扩展到棋盘多项式，从而nk=0R(C)= rk(C) xknk=1 rk1(Ci)+ rk(Ce)xkn-1k=0nk=0 = x rk(Ci)xk + rk(Ce)xk xR(Ci) + R(C e) (3)453.4 棋盘多项式和有限制排列例如：R( )= xR( )+ R( )R( )=1+ x；R( )= x R( ) + R( ) =x+ (1+ x)=1+2x； = x(1 + x )+1 + x =1+ 2x +x2463

25、.4 棋盘多项式和有限制排列性质2:如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2的格子。则有： rk(C) = ri(C1) rki(C2) i=0k故R(C) = ( ri(C1) rki(C2) ) xk kni=0k=0 R(C) = R(C1) R(C2) (4)j=0nni=0 = ( ri(C1) xi) ( rj(C2) xj )473.4 棋盘多项式和有限制排列利用（）和（），可以把一个比较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。例R ( ) = xR( )+R( ) = x(1+ x)2 +(1+2x)2 =1+ 5x +6x2 + x3*R( ) = xR( ) + R( ) = 1+6x +10 x2 +4x3*483.5 棋盘多项式和有限制排列有禁区的排列例设对于排列P=P1 P2 P3 P4，规定P1，P、， P2、， P42。 1 2 3 4P1P2P3P4这样的排列对应于有禁区的布子。如图中有影线的格子表示禁区。493.5 棋盘多项式和有限制排列定理设 ri 为 i个棋子布入禁区的方案数，i =1,2,3,n。有禁区的布子方案数（即禁区内不布子的方案数）为 n! r1(n1)! r2(n2)