第三章容斥原理与鸽巢

1、第三章 容斥原理与鸽巢原理马昱春myc1第三章 容斥原理与鸽巢原理InclusionandExclusionPrinciple计数时重叠部分不能被重复计算容斥的计数思想是: 先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来； 然后再把计数时重复计算的数目排斥出去； 使得计算的结果既无遗漏又无重复。2 容斥原理ABAB§3.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+6=16 个，因为6，12，18但 在两类中重复计数，应减去。 故是：16-

2、3=133§3.1容斥原理引论若A和B是集合U的子集，补集complementA = x | x ÎU 且x Ï A德摩根De Morgan定理(a)A U B = A I B(b)A I B = A U BUAB4(a)A U B =A I B证：(a)的证明。x Ï B同时设x Î A U B ,则 x Ï A U B相当于 x Ï A和成立，亦即xÎ AU B Þ xÎ AI B(1)反之，若 x Î A I B, 即x Î A和x Î B故 x Ï

3、 A, x Ï B即x Ï A U B x Î A I B Þ x Î A U B(2)由（1）和（2）得 x Î A I B Û x Î A U B(b)的证明和(a)类似，从略.5§3.1容斥原理引论DeMogan定理的推广：设A1,A2, . An是U的子集,(a)A1 U A2 U . U An = A1 I A2 I . I An则证:采用数学归纳法A1 U A2 U . U An= A1 I A2 I. I An正确则= ( A1 U. U An ) U An+1A1 U A2 U. U An

4、U An+1= ( A1 U A2 U. U AnI An+1= A1 I A2 I. I AnI An+1即定理对n+1也是正确的。6§3.2容斥原理最简单的计数问题是求有限集合A和B的并的元素数目。证若AB=，则 | AB |= |A| + |B| A | A ( BB) | (AB)(AB)| AB | + | AB |( 1 )同理| B | | BA | + | BA | AB |(A( BB)(B(AA)|( 2 )|(AB)(AB)(BA)(BA)| AB| + |AB | + | BA|( 3 )(3)-(2)-(1) 得到| AB | A | B | AB| + |

5、AB | + | BA| ( | AB | + | AB | )( | BA | + | BA | )7| AB | A | + | B | AB | | AB |A U B=A+B-A I B(1)§3.2容斥原理定理：(2)-+B I CA I B I C-A I C8A U B U C=A+B+C-A I B§3.2容斥原理证明：=A U B U C( A U B) U C=+ C- ( A U B) I CA U B( A U B) I C = ( A I C) U (B I C)根据=A + C-A U B U CBA I B- ( A I C) U (B I C

6、) = A + B + C - A I B - A I C - B I C9+A I B I C§3.2容斥原理进一步可推出：=A +B + C+ D -A U B U C U DA I B- A I C - B I C-A I D +A I B I C+A I B I D + B I C I D -A I B I C I D10§3.2容斥原理例 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？令：M为修

7、数学的学生集合；P 为修物理的学生集合；C 为修化学的学生集合；= 170,= 130, C= 120, M I P= 45PM= 20, P I C= 22, M I P I C= 3M I CM- 20 - 22 + 311即学校学生数为336人。= 336-M I C-P I C+M I P I CM U P U C=M+P+C-M I PC(3,k) = 1 2 31 21 32 31 2 3k=1时k=2时k=3时C(2,k) = 1 21 2k=1时k=2时C(3,2) = 1 32 31 2定理设C(n,k)是1,n的所有k-子集的集合, 则nnååIA |i

8、ii =1k =1I ÎC ( n ,k )iÎ I证: 分析C(n,k)，可根据包含不包含n划分成两部分包含n的可看做C(n-1,k-1)中每个子集再加上元素n；不包含n的由C(n-1,k)组成；å IååA |=IIA |+I|A|A |k2iiniIÎC(n,k) iÎIIÎC(n-1,k-1) iÎIIÎC(n-1,k) iÎI对n用归纳法。n=2时，等式成立。 假设对n - 1，等式成立。对于n有12nnåk = 1å=( - 1) k -1U| IAA|

9、iii = 1I Î C ( n , k )iÎ In-1n-1n-1n-1n-1n=+ | A | -=+ | A | -UUUUUUUAAAAA I AnA(A I An )iininiini证i=1i=1i=1i=1i=1i=1n-1n-1n-1åiåånåå I i=| A | +(-|A |+| A | -(-k1I ik11)1)|(A IA )|ni=1k=2IÎC(n-1,k) iÎIk=1IÎC(n-1,k)iÎIn-1n-1n-1nååå

10、;|A |+ | A | +å(-1)k-1åk -n-=| A | +(-1II+ (-1I1)|( AI A ) |1)|A |iininii=1k =2IÎC ( n-1,k ) iÎIk =2IÎC ( n-1,k -1) iÎIi=1i =1k =2IÎC ( n,k ) iÎIi =1n= å(-1)k-1k =1å | I Ai |IÎC ( n,k )iÎI13nn-1= å| A | +å(-1)k-1iå | I Ai |n+

11、 (-1)n-1 | I A |i由于å |IAi |=å |IAi IAn |+å |IAi |IÎC(n,k) iÎIIÎC(n-1,k-1) iÎIIÎC(n-1,k) iÎIn-1n-1= å(-1)k-1k=1å |IAi |IÎC(n-1,k) iÎI+| A | -å(-1)k-1nk=1å |I(Ai IAn |IÎC(n-1,k) iÎI§3.2容斥原理k - 1此定理也可表示为：A1 U A2U

12、. U Annni =1i =1j >in+ååå- .I AjI AkAii=1 j>i k>j(4)+(-1)n-1A I AI . I A12n14= åAi- ååAiI AjnnU A ii = 1= å ( - 1)k = 1å| I A i|I Î C ( n , k )iÎ I§3.2容斥原理= N -A ,又A其中N是集合U的元素个数，即不属于A的元素个数等于集合的全体减去属于A的元素的个数。一般有：= N -A1 I A2 I . I AnA1 U

13、 A2U . U An-1 U Annn= N - å+ ååAiAiI Aji=1i=1j >in(5)-ååå Ai+ .I AjI Aki=1 j>i k>j+ (-1)nA I A I . I A1512nInclusion-Exclusion Principle| A1 I A2 |=| S | - | A1 | - | A2| + | A1 I A2|计算不在 A1 也不在 A2中的元素个数若x 不属于A1 或A211-0-0+0 = 1若x 属于A1 但不属于A201-1-0+0 = 0若x 属于A2

14、但不属于A101-0-1+0 = 0若x 属于A2 且属于A101-1-1+1 = 0 两边相等16(x+y)m =C(m,0)xm+ C(m,1)xm-1y+C(m,m)ym If x=1, y=-10 = C(m,0)- C(m,1) +(-1)mC(m,m)= S -å Ai+å Ai Ç Aj-å Ai Ç Aj Ç AkA1 Ç A2 ÇLÇ Am计算不满足任意属性的元素.å+L+(-A Ç A ÇÇ Am1)L12mX不满足任何属性11-0-0+(-1)

15、m0 = 1X只满足1个属性01-1-0 +(-1)m0 = 0X只满足n个属性, n£mC(n,0)-C(n,1)+C(n,2)+(-1)mC(n,m)0= C(n,0)-C(n,1)+C(n,2)+(-1)n) +0 +0=0两边相等，同样计算不满足任何属性的元素个数17§3.2容斥原理容斥原理指的就是（4）和（5）式。nn= å Ai- åå AiA1 U A2 U . U AnI Aji=1i=1j >in+ååå Ai- .I Aj I Aki=1 j>i k>j(4)+(-1)n-1A

16、 I AI. I A12n= N -A1 I A2 I. I AnA1 U A2U . U An-1 U Annnn= N - å Ai+ åå Ai-ååå Ai+ .I AjI Aj I Aki=1+ (-1)ni=1j >ii=1 j>i k>j(5)A I A I. I A12n18§3.2容斥原理Inclusionexclusion principle This concept is attributed to Abraham deMoivre (1718) it first appears in

17、 a paper of Daniel da Silva (1854) later in a paper by J. J. Sylvester (1883)"One of the most useful principles of enumeration in discrete probability andcombinatorial theory is the celebrated principle of inclusionexclusion. When skillfully applied, this principle has yielded the solution to m

18、any a combinatorial problem."§3.3 举例求a,b,c,d,e,f六个字母的全排列中不例1出现ace和df图象的排列数。解：6个字母全排列： |S| = 6!设A为ace作为一个元素出现的排列集: |A|=4!，B为 df作为一个元素出现的排列集: |B|=5!，AB为同时出现ace、df的排列数: |AB |=3!。| AIB|=| AUB|=S-| A|-| B|+| AIB|= 6!-4!-5!+3!= 58220§3.3 举例求从1到500的整数中能被3或5除尽的数的个数。例2解： 令A为从1到500的整数中被3除尽的数的集合

19、，B为被5除尽的数的集合= ê 500 ú = 166, B= ê 500 ú = 100;Aêëúûêëúû35= ê 500 ú = 33A I Bêë 15úû被3或5除尽的数的个数为=A +-A U BBA I B=21§3.3 举例 例3 求由a,b,c,d四个字母的n位符号串中，a,b,c都 至少出现一次的符号串数目。 解：令A、B、C分别为n位符号串中不出现a，b，c符号的集 合。由于n位符号

20、串中每一位都可取a，b，c，d四种符号中的一出现a的n位符号串的个数应是3n个，即：个，故不= 3n= 1BCAA I B I C= 2nA I BA I CC I Ba，b，c至少出现一次的n位符号串集合即为= 4n - ( A+C ) + ( A I BA I B I CB+C I B ) -A I CA I B I C= 4n- 3 · 3n + 3 · 2n -122§3.3 举例 例4。求不超过120的素数个数。 因112=121，故不超过120的合数必然是2、3、5、7的 倍数，而且不超过120的合数的因子不可能都超过11。设Ai为不超过120的数 i

21、的倍数集， i=2，3，5，7。= ê120 ú = 60，A= ê120 ú = 40，Aêëúûêëúû2323ê120 úê120 ú= êëúû = 24，A7= êëúû = 17,A557120ê120ê=ú = 20，A=ú = 12,AI AI A2325ë 2 ´ 3 û

22、ë 10û= ê120 ú = 8，A I A= ê120 ú = 8，AI Aêë 14ûúëê 15ûú273523= ê120 ú = 5，A= ê120 ú = 3，AAI AIêëúûêëúû37572135= ê120ú =AAI A4，Iêë 2 ´ 3´ 5 &#

23、250;û235= ê120ú =AAI A2，Iêë 2 ´ 3 ´ 7 úû237= ê120ú = 1，AAI AIêë 2 ´ 5 ´ 7 ûú257= 120 -+-A2 I A3I A5 I A7A2A3A2A5-+A7A3A2 I A3A2 I A5I A7注意：因为27个数中排除+I A5A3 I A7A5 I A7了2，3，5，7四个素数，-A2I A3I A5A2 I A3 I A7又包含了1这个非素数。故

24、所求的不超过120的素数个+AI AI A I A2357数为：= 120 - (60 + 40 + 24 +17) + (20 +12 + 8+ 8 + 5 + 3) - (4 + 2 +1+1)27+4-1=3024= 27.-A2 I A5 I A7-A3 I A5 I A7§3.3 举例例5。用26个英文字母作不重复的全排列，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。解：令A1为出现dog，| A1 |=24！ 令A2为出现god，| A2 |=24！令A3为出现gum，| A3 |=24！令A4为出现depth，| A4 |=

25、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, thingum: | A3A5| = 20！A4A5, depthing:| A4A5| = 19!,A1A3 A4,dogumdepth0;A2A4 A5, godepthing0; A3A4 A5, depthingum | A3A4 A5 | = 17！2

26、5所求的排列数为 26!-(3*24!+2*22!)+(22!+4*20!+19!)-(17!)§3.3 举例例6。求完全由n个布尔变量确定的布尔函数的个数。260 00 11 01 1f(x1,x2)f(x1,x2,xn)中n个f100000布尔变量的不同的f20001x1 Ù x 2f30010x1 Ù x 2状态数为2n 每个状态有0，1两f40011x1f50100x1 Ù x 2种取值，f60101x2f70110x1 Ù x 2 故f(x1,x2,xn)的布n尔函数个数为 22f80111(x1Ú2)f91000x1 &#

27、218; x 2f101001x1 Ù x 2f111010(x1Ú2)f121011x 2f131100x1 Ú x 2f141101x1f151110x1 Ú x 2f1611111n22f(x1,x2,xn)的布尔函数个数为 例6。求完全由n个布尔变量确定的布尔函数的个数。n )中xi不出现的布尔函数类为：Ai ， i = 1, 2,., n.解：设 f (n-1C (n,1) 22n-2C (n,2) 22有1个变量不出现的布尔函数个数为有2个变量不出现的布尔函数个数为n-kC (n, k ) 22有k个变量不出现的布尔函数个数为根据容斥原理，满

28、足条件的函数数目为：n-1n= 22- C(n,1)22A I AI . I A12nn-2n-k+ C(n, 2)22- . + (-1)k C(n, k )22+ . + (-1)n)2n = 2时，得2= 22- C (2,1)22 + C (2, 2)2A I A1227 = 16 - 8 + 2 = 10§3.3 举例例6。求完全由n个布尔变量确定的布尔函数的个数。280 00 11 01 1f(x1,x2)f(x1,x2,xn)中n个f100000布尔变量的不同的f20001x1 Ù x 2f30010x1 Ù x 2状态数为2n 每个状态有0，1两f

29、40011x1f50100x1 Ù x 2种取值，f60101x2f70110x1 Ù x 2 故f(x1,x2,xn)的布n尔函数个数为 22f80111(x1Ú2)f91000x1 Ú x 2f101001x1 Ù x 2f111010(x1Ú2)f121011x 2f131100x1 Ú x 2f141101x1f151110x1 Ú x 2f1611111在计算机领域中广泛使用的RSA公钥算法也正是以欧拉函数为基础的。例7。欧拉函数F(n)是求小于n且与n互素的数的个数。 分析的化身欧拉进行计算看起来毫不费

30、劲儿，就像人进行呼吸，像鹰在风中盘旋一样。 他是历史上最多产的数学家。 彼得堡学院为了整理他的著作整整花了47年。 欧拉确实常常在两次叫他吃晚饭的一篇数学左右的时间里赶出 人生波折：失明，火灾 科学环境：普鲁士腓特烈大帝和叶卡捷琳娜女皇慷慨地给了数学以无法报偿的资助。1783年9月18日，他77岁的时候，欧拉写出了他对星轨道的计算。他在喝着茶跟孩子玩的时候，中风发作。手中烟斗掉了， 只说出一句话"我要死了","欧拉便停止了生命和计算。"29F(8)=48 = 23，小于8且与8互素有§3.3 举例 例7。欧拉函数F(n)是求小于n且与n互素的数

31、的个数。 ap a2 . pakn = pn分解为不同素数的乘积解：若112k| A |= n , i =1,2.k设1到n的n个数中为p 倍数的集合为Aiiipi对于pipj, AiAj既是pi的倍数也是pj的倍数。n| A IA |=,i, j =1,2.,k,i ¹ jijp pijy(n)=I . I Aknnnn= n - (+ . +) + (pknnn+ . +) - × ×× ±p p××× ppp p31n12k111= n(1 -)(1 -) ××× (1 -)p1

32、p2pk30111y(n)=n(1 -)(1 -) ××× (1 -)p1p2pk 例7续。欧拉函数F(n)是求小于n且与n互素 的数的个数。F(8)=8(1-1/2) = 48 = 23，小于8且与8互素有1 3 5 7例如n = 60 = 22 ´ 3´ 5，则y (60) = 60(1 - 1 )(1 - 1)(1 - 1 ) = 16235即比60小且与60无公因子的数有16个：7，11，13，17，19，23，29，31，37，41，43，47，49，53，59，此外还有一个1。31例 求不定方程x1+x2+x3=15,求整数解的数目

33、。其中附加约束为0x1 5, 0x2 6； 0x3 7,例 求不定方程x1+x2+x3=15,附加约束为0x1 5, 0x2 6； 0x3 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|A2|= C(8+3-1,8)= C(10,2)设A3为x38的解，x1+x2+ y3+8=15|A3|= C(7+

34、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)33+C(4,2)+C(3,1)+1=10§3.7 容斥原理应用举例例 求不定方程x1+x2+x3=15,附加约束为0x15, 0x26； 0x37

35、,求整数解的数目。解2: x1=5-x1, x2=6-x2, x3=7-x3x1+ x2 + x3 =5-x1+6-x2+7-x3=18-(x1+x2+x3) = 3,x1+ x2 + x3 =3C(3+3-1,3) = 10x1, x2, x30的非负整数解个数。：例3-18，pp13834讨论例:求不定方程x1+x2+x3=15,附加约束为0x1 10,0x2 10； 0x3 10,求整数解的数目x1=10-x1, x2=10-x2, x3=10-x3x1+ x2 + x3 =10-x1+10-x2+10-x3=15, x1, x2, x30x1+ x2 + x3 =15x1, x2, x

36、30整数解个数相等?x1+x2+x3=150x1,x2,x3 10显然不成立,所以原解法不具有通用性 应加上约束条件11+2+2=15x1=11x2=2x3=2找不到对应的x1,x2,x3 0 x1, x2, x3 10x1=10-x1, x2=10-x2, x3=10-x335讨论x1+x2+x3=S0x1 m1, 0x2 m2； 0x3 m3x1=m1-x1, x2=m2-x2, x3=m3-x3x1+ x2 + x3 =m1+m2+m3-S0 x1 m1, x2 m2, x3 m3解个36 若m1+m2+m3-S min(m1,m2,m3)则 x1+x2+x3=S0x1 m1, 0x2

37、m2； 0x1 m3 x1+ x2 + x3 =m1+m2+m3-S x1, x2, x30整数数相等§3.3 举例 例8: 错排问题: n个元素依次给以标号1，2，n。n个元素的全排列中，求每个元素都不在原来位置上的排列数。设Ai为数i在第i位上的全体排列，i=1，2，n。因数字i不能动，因而有：|Ai|=(n-1)!|AiAj |=(n-2)!每个元素都不在原来位置的排列数为= n!n -1)!A1 I A2 I . I An+- 2)!- ××× -,)1!111 )= n!(1 -+- ××× ±(n -

38、i)!i!i!1!2!n!37C(n, i)(n - i)!=n!(n - i)!= n! 例9 在8个字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四个字母不在原来上的错排数目。解：8个字母的全排列中，令AA,AC,AE,AG分别表A,C,E,G在原来位置上的排列，则错排数为：- C(4, 3)5!+ C(4, 4)4! = 2402438A1 I A2 I A3 I A4= 8!- C(4,1)7!+ C(4, 2)6! 求8个字母A,B,C,D,E,F,G,H的全排列中只 有4个不在原来位置的排列数。解：8个字母中只有4个不在原来位置上，其余4个字母保持不动，相当于4个

39、元素的错排，其数目为4!(1 - 1 +111 )-+1!2!3!4!= 24(1 -1 + 1 - 1 +1) = 92624 故8个字母的全排列中有4个不在原来位置上的排列数 39应为：C(8,4)·9=630§3.4棋盘多项式和有限制排列1.有限制排列4个x ，3个y，2个z的全排列中，求不出现x，yyy，zz图象的排列。例x的排列的集合记为A1，解设出现|A1|=6 !=60;3 ! 2 !设出现yyy的排列的集合记为A2， 7 ! | A2|=105；4 !2 !设出现zz的排列的集合记为A2， 8 ! | A3|=280；4 !3!4 !5 !|A1A2|=12

40、； |A1A3|=20；2 !3!6 !|A2A3|=30； |A1A2A3|=3!=6；4 !9!/(4!*3!*2!) =1260；全排列的个数为： 所以： |A1A2A3|=1260(60+105+280)+(12+20+30)6=87140§3.4棋盘多项式和有限制排列 棋盘多项式 n个不同元素的一个全排列可看做n个相同的棋子在n×n的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子non-attacking rooks12345xP1的布局对应 xP2于排列41352。xP3xP4xP541§3.4棋盘多项式和有限制排列可以把棋盘的形状推广到任意

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

42、，则 r1(C)nr1(C)r0(Ci) + r1(Ce)，r1(Ce)n1 r0(Ci)1故规定 r0(C)1是合理的44§3.4棋盘多项式和有限制排列该性质扩展到棋盘多项式，从而nR(C)= r (C) xkkk=0nrk1(Ci)+ rk(Ce)xkk=1n-1n= x rk(Ci)xk + rk(Ce)xkk=0k=0xR(Ci) + R(C e)(3)45§3.4棋盘多项式和有限制排列 例如：R()=1+ x；R()= xR()+ R() =x+ (1+ x)=1+2x；R()= x R() + R()= x(1 + x )+1 + x=1+ 2x +x246§3.4棋盘多项式和有限制排列性质2:如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2的格子。则有：krk(C) = ri(C1) rki(C2)i=0nkR(C) = ( ri(C1) rki(C2) ) xk故k=0i=0nn=( ri(C1) xi) ( rj(C2) xj )j=0i=0R(C) = R(C1) R(C2)(4)47§3.4棋盘多项式和有限制排列 利用（）和（），可以把一个比较复 杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。例R () = xR()+R()*= x(