5-2 容斥原理

5.5.容斥原理(TheInclusion-ExclusionPrinciple)（新）对任意有限集A、B，成立|AB|=|A|+|B|-|AB|图解说明例2(p348)有多少个不超过1000的正整数可以被7或者11整除？解：设不超过1000的正整数中可以被7整除的数组成集合A，其中可以被11整除的数组成集合B，则现在是要求|AB|。|A|=？|A|=[1000/7]=142类似地，|B|=[1000/11]=90|AB|=[1000/77]=12所以，|AB|=|A|+|B|-|AB|=220。n=3时的容斥原理|ABC|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|图解说明例4(p350)1232个学生选了西班牙语课，879个学生选了法语课，114个学生选了俄语课。103个学生选了西班牙语和法语课，23个学生选了西班牙语和俄语课，14个学生选了法语和俄语课。如果2092个学生至少在西班牙语、法语和俄语课中选一门，那么有多少学生选了所有这3门语言课？解：设选了西班牙语、法语、俄语课的学生分别组成集合A，B，C。则已知|A|,|B|,|C|,|AB|,|AC|,|BC|以及|ABC|要求|ABC|，根据容斥原理可得，7。容斥原理的一般形式(重点，新)|A1A2…An|=-++…+(-1)n+1|A1A2…An|证明：某元属于n个集合中的r个。r=1:该元在第1个式子中计了1次,后面式子与此元无关，正确。r=2:该元在第1个式子中计了2次，在第2个式子中计了1次，…。r=3:C(3,1)-C(3,2)+C(3,3)=1，…。r=r：该元在前r个式子分别计了C(r,1),C(r,2),C(r,3),…,C(r,r)次，由nk=0(-1)kC(n,k)=0：C(r,1)-C(r,2)+C(r,3)+…+(-1)r+1C(r,r)=C(r,0)=1,…。ni1i|A|nji1ji|AA|nkji1kji|AAA|应用例子1求出不超过100的素数的个数已知结果：合数n有一个不超过的素因子所以，不超过100的合数都是2或3或5或7的倍数，或者说它们都能被2或3或5或7整除。≤100的数中能被2或3或5或7整除的数有多少个？由容斥原理可解，78个。过程写在黑板上。≤100的数中，合数有多少个？能被2或3或5或7整除的数中仅4个不是合数。合数74个。不超过100的素数的个数为100-74-1=25个。（“1”既不是素数也不是合数）n应用例子2：映上函数的个数从6个元素的集合到3个元素的集合有多少个映上的函数？解：考虑从6个元素的集合到3个元素的集合有多少个普通函数、有多少个不是映上的函数？其差为所求。普通函数的个数？有多少个不是映上的函数？有多少个不是映上的函数？什么情况下，函数不是映上的？陪伴域中一个或多个元素(至少有一个元素)不在值域中。记陪伴域元素为a,b,c，分别把a、b、c不在值域中的函数全体记为A、B、C。可以用容斥原理求出不是映上的函数的个数|ABC||A|=26。类似|B|=|C|=26。|AB|=1=|AC|=|BC|以及|ABC|=0|ABC|=326–3+0=192-3=189。映上的函数的个数=36–189=729-189=540个。定理(映上函数的个数)设m和n是正整数,mn,有nm–C(n,1)(n-1)m+C(n,2)(n-2)m-…+(-1)n-1C(n,n-1)1m个从m个元素的集合到n个元素的集合映上的函数。说明：nm–{C(n,1)(n-1)m-C(n,2)(n-2)m+…-(-1)n-1C(n,n-1)1m}{}内为不是映上的函数的个数。应用例子3把5项工作分给4个雇员，如果每个雇员至少分配一项工作，有多少分配工作的方式？应用例子4例：方程x+y+z=11有多少个非负整数解，要求x3,y4,z6？分析：满足x4时方程x+y+z=11，有多少个非负整数解？容易求出。36个将原问题化为求或满足x4、或满足y5、或满足z7的非负整数解的个数问题。后者可以由容斥原理求出。72个原问题的解为：从x+y+z=11的非负整数解（78个）中扣除…。6.容斥原理的另一种形式（选学，本质与前面相同）用于求一个集合中，不具有n个性质中任何一条的元素的个数。设A为一个集合，P1,P2,…,Pn是n条性质，A中同时具有若干条性质，比如P1,P2,…,Pk，的元素的个数记为N(P1,P2,…,Pk)。举例：A中不具有性质P1,P2,…,Pn中任一条的元素的个数记为N(P‘1,P’2,…,P‘n).则N(P’1,P’2,…,P‘n)=|A|-1inN(Pi)+1ijnN(Pi,Pj)-1ijknN(Pi,Pj,Pk)+…+(-1)nN(P1,P2,…,Pn).N(P‘1,P’2,…,P‘n)=|A|-1inN(Pi)+1ijnN(Pi,Pj)-1ijknN(Pi,Pj,Pk)+…+(-1)nN(P1,P2,…,Pn)=|A|-{1inN(Pi)-1ijnN(Pi,Pj)+1ijknN(Pi,Pj,Pk)+…+(-1)nN(P1,P2,…,Pn)}。由容斥原理，{}中的数值正是A中或者具有性质P1,或者具有性质P2,…,或者具有性质Pn的元素个数。若还不明白集合A中具有性质Pi的元素的子集记为Ai，i=1,2,…,n.N(Pi)=|Ai|N(Pi,Pj)=|AiAj|N(Pi,Pj,Pk)=|AiAjAk|……N(P1,P2,…,Pn)=|A1A2…An|如此，更接近原来容斥原理的形式。其实，前面几个例子都是应用的这种形式。例：方程x+y+z=11有多少个非负整数解，要求x3,y4,z6？解：集合A：非负整数解，|A|=C(11+3-1,11)=78性质P1，P2，P3分别为：x4,y5,z7方程x+y+z=11满足P1：x4的非负整解个数为方程x+y+z=7的非负整解个数。N(P1)=C(7+3-1,7)=36类似地：N(P2)=28，N(P3)=15。类似地：N(P1,P2)=6，N(P1,P3)=1，N(P2,P3)=0N(P1,P2,P3)=0由容斥原理第二形式，所求=N(P’1,P’2,P’3)=|A|-N(P1)-N(P2)-N(P3)+N(P1,P2)+N(P1,P3)+N(P2,P3)-N(P1,P2,P3)=78-36-28-15+6+1+0-0=6。错位排列(derangement)的个数帽子寄存问题。在一个餐厅里一个新的雇员寄存n个人的帽子时忘记把寄存号放在帽子上。当顾客取回他们的帽子时，这个雇员随机地取一顶帽子发给他们，问所有顾客都没有拿到自己帽子的概率？错位排列：对于n个物体，给定它们的一个排列为初始排列，错位排列是这n个物体的一个排列，其中没有一个物体在它的初始位置。错位排列数：n个元素的错位排列数为（用容斥原理）n较大时，错位排列的概率近似为1/e=0.368][n!11)(4!13!12!11!11n!Dnn也是用容斥原理。无论哪种形式都可p358。在求错位排列数（or非错位排列数）的式子中的每项都有一个n！因子，最后一种情况下的个数为n!/n!。还有一些没讲的内容，如母函数，自学。分而治之是一个问题求解的策略。这里讲的是在分而治之算法（如递归算法）的复杂度分析中所产生的递推关系的解序列的大O估计（这类递推关系分而治之的递推关系）。练习：P359，1,3,5,9,15