容斥原理组合数学

容斥原理组合数学[解]2得倍数就是:2,4,6,8,10,12,14,16,18,20。共10个;3.1容斥原理例1,求[1,20]中2或3得倍数得数得个数、否！因为6,12,18在两类中重复计数,应减去。3得倍数就是:3,6,9,12,15,18。共6个;答案就是10+6=16个吗？故答案就是:16-3=13

容斥原理研究有限集合得交或并得计数。则有3.1容斥原理(b)[DeMorgan定理]论域U,A得补集(a)(1)3.1容斥原理证:(a)得证明相当于和同时成立，亦即若则反之，若故(2)由(1)与(2)得(b)得证明与(a)类似,从略、3.1容斥原理DeMogan定理得推广:证明:只证(a)、n=2时,定理已证。设定理对n就是正确得,即假定:3.1容斥原理设正确即定理对n+1也就是正确得。3.1容斥原理

最简单得计数问题就是求有限集合A与B得并得元素数目。显然有即具有性质A或B得元素得个数等于具有性质A得元素个数与具有性质B得元素个数减去同时具有性质A与B得元素个数。(1)定理13.1容斥原理UBA3.1容斥原理3.1容斥原理证若A∩B=φ,则

|A∪B|=|A|+|B|,否则同理|B|＝|B∩A|+|B∩A|(2)|A|＝|A∩(B∪B)|

＝|(A∩B)∪(A∩B)|

＝|A∩B|+|A∩B|(1)3.1容斥原理|A∪B|－|A|－|B|＝|A∩B|+|A∩B|+|B∩A|

－(|A∩B|+|A∩B|)

－(|B∩A|+|B∩A|)＝－|A∩B|(3)－(1)－(2)得∴|A∪B|＝|A|+|B|－|A∩B|大家有疑问的，可以询问和交流可以互相讨论下，但要小声点3.1容斥原理证明定理23.1容斥原理3.1容斥原理ABC例2,一个学校只有三门课程:数学、物理、化学。已知修这三门课得学生分别有170、130、120人;同时修数学、物理两门课得学生45人;同时修数学、化学得20人;同时修物理化学得22人。同时修三门得3人。问这学校共有多少学生？3.1容斥原理解:令M为修数学得学生集合;

P

为修物理得学生集合;

C为修化学得学生集合;则即学校学生数为336人。3.1容斥原理同理可推出:利用数学归纳法可得一般得定理:3、1容斥原理3、1容斥原理证对n用归纳法。n=2时,等式成立。

假设对n-1,等式成立。对于n有定理3设

(n,k)就是［1,n］得所有k-子集得集合,则3、1容斥原理3.1容斥原理(4)定理3’设是有限集合，则此定理也可表示为:其中N就是集合U得元素个数、即不属于A得元素个数等于集合得全体减去属于A得元素得个数、一般有:3.1容斥原理(5)容斥原理指得就就是(4)与(5)式。解:设A为ace作为一个元素出现得排列集,B为df作为一个元素出现得排列集,A

B为同时出现ace、df得排列数。3.1容斥原理例3求a,b,c,d,e,f六个字母得全排列中不允许出现ace与df图象得排列数。根据容斥原理,不出现ace与df得排列数为:=6!-(5!+4!)+3!=582例4求从1到500得整数中能被3或5除尽得数得个数、3.1容斥原理解:令A为从1到500得整数中被3除尽得数得集合,B为被5除尽得数得集合被3或5除尽得数得个数为解:令A、B、C分别为n位符号串中不出现a,b,c符号得集合。由于n位符号串中每一位都可取a,b,c,d四种符号中得一个,故不允许出现a得n位符号串得个数应就是3^n即有3.1容斥原理例5求由a,b,c,d四个字母构成得位符号串中,a,b,

c,d至少出现一次得符号串数目。a,b,c至少出现一次得n位符号串集合即为3.1容斥原理例6,求不超过120得素数个数。

因11×11=121,故不超过120得合数必然就是2、3、5、7得倍数,而且不超过120得合数得因子不可能都超过11。设

Ai为不超过120得数i得倍数集,i=2,3,5,7。3.1容斥原理3.1容斥原理3.1容斥原理3、1容斥原理3.1容斥原理

注意:27并非就就是不超过120得素数个数,因为这里排除了2,3,5,7着四个数,又包含了1这个非素数。2,3,5,7本身就是素数、故所求得不超过120得素数个数为:27+4-1=30

例7,用26个英文字母作不允许重复得全排列,要求排除dog,god,gum,depth,thing字样得出现,求满足这些条件得排列数。3.1容斥原理解:所有排列中,令出现dog字样得排列,相当于把dog作为一个单元参加排列,故类似有:由于god,dog不可能在一个排列中同时出,故:类似:3.1容斥原理

由于gum,dog可以在dogum字样中同时出现，故有：

类似有god和depth可以在godepth字样中同时出现，故

god和thing可以在thingod字样中同时出现，从而

3.1容斥原理3.1容斥原理

由于god、depth、thing不可以同时出现,

故有:其余多于3个集合得交集都为空集。3.1容斥原理

故满足要求得排列数为:

例8，求完全由n个布尔变量确定的布尔函数的个数。

由于n个布尔变量x1,x2,…xn

的不同的真值表数目与位2进制数数目相同，故为个。根据容斥原理，满足条件的函数数目为：3.1容斥原理解:设f(x1,x2,…xn)中xi不出现得布尔函数类为3.1容斥原理3.1容斥原理这10个布尔函数为：x1∧x2，x1∧x2，x1∧x2，x1∧x2，x1∨x2，x1∨x2，x1∨x2，x1∨x2，(x1∨x2)∧(x1∨x2)，(x1∨x2)∧(x1∨x2)

例9。欧拉函数

(n)就是小于n且与n互素得数得个数。

设1到n得n个数中为pi倍数得集合为则有3.1容斥原理解:若n分解为素数得乘积3.1容斥原理3.1容斥原理即比60小且与60无公因子得数有16个:7,11,13,17。19。23,29,31,37,41,43,47,49,53,59,此外尚有一个1。3.1容斥原理1,再解错排问题

n个元素依次给以标号1,2,…,n。n个元素得全排列中,求每个元素都不在自己原来位置上得排列数。设Ai

为数i在第i位上得全体排列,i=1,2,…,n。因数字i不能动,因而有:3.2容斥原理—应用同理每个元素都不在原来位置得排列数为3、2容斥原理—应用

例1。数1,2,…,9得全排列中,求偶数在原来位置上,其余都不在原来位置得错排数目。3、2容斥原理—应用解:实际上就是1,3,5,7,9五个数得错排问题,总数为:例2,在8个字母A,B,C,D,E,F,G,H得全排列中,求使A,C,E,G四个字母不在原来上得错排数目。解:8个字母得全排列中,令

A1

A2

A3

A4分别表A,C,E,G在原来位置上得排列,则错排数为:3.2容斥原理—应用例3。求8个字母A,B,C,D,E,F,G,H得全排列中只有4个不在原来位置得排列数。解:8个字母中只有4个不在原来位置上,其余4个字母保持不动,相当于4个元素得错排,其数目为:3.2容斥原理—应用故8个字母得全排列中有4个不在原来位置上得排列数应为:C(8,4)·9=6302、有限制排列3、2、容斥原理—应用解设出现xxxx得排列得集合记为A1,则设出现yyy得排列得集合记为A2,则4!2!7!=105；|A2|=6!1!·3!·2!=60;|A1|=例4

4个x,3个y,2个z得全排列中,求不出现xxxx,yyy,zz图象得排列。3.2.容斥原理—应用设出现zz得排列得集合记为A3,4!·3!8!|A3|=

=280；4!2!|A1∩A2|==125!3!|A1∩A3|==20；6!4!|A2∩A3|==309!2!·3!·4!全排列的个数为：

=1260；|A1∩A2∩A3|=3!=6所以|A1∩A2∩A3|=1260－(60+105+280)+(12+20+30)－6=8713.2.容斥原理—应用3、棋子多项式

n个不同元素得一个全排列可瞧做n个相同得棋子在n×n得棋盘上得一个布局。布局满足同一行(列)中有且仅有一个棋子xxxxx

如图所示得布局对应于排列41352。3.2.容斥原理—应用

可以把棋盘得形状推广到任意形状:

布子规定称为无对攻规则,棋子相当于象棋中得车。

令r

k(C)表示k个棋子布到棋盘C上得方案数。如:3.2.容斥原理—应用r1()=1，r1()=2，r1()=2，r2()=0，r2()=1。为了形象化起见,()中得图象便就是棋盘得形状。3.2.容斥原理—应用定义1设C为一棋盘，称R(C)=∑rk(C)xk为C的棋盘多项式。k=0∞规定r0(C)=1,包括C=Ф时。设Ci就是棋盘C得某一指定格子所在得行与列都去掉后所得得棋盘;Ce就是仅去掉该格子后得棋盘。在上面定义下,显然有rk(C)=rk－1(Ci)＋rk(Ce),3.2.容斥原理—应用即对任一指定得格子,要么布子,所得得方案数为

rk－1(Ci);要么不布子,方案数为

rk(Ce)。

设C有n个格子,则

r1(C)＝n、r1(C)＝r0(Ci)+r1(Ce),∵r1(Ce)＝n－1∴r0(Ci)＝1、故规定

r0(C)＝1就是合理得、3.2.容斥原理—应用

从而

R(C)=∑rk(C)xk

＝１＋∑[rk－1(Ci)+

rk(Ce)]xk=x∑rk(Ci)xk+∑rk(Ce)xk

＝xR(Ci)+R(C

e)(3)∞k=0∞k=1∞k=0∞k=03.2.容斥原理—应用例如:R()=1+x；R()=xR()+R()=x+(1+x)=1+2x；R()=xR()+R()=x(1+x)+1+x=1+2x+x23.2.容斥原理—应用

如果C由相互分离得C1,C2组成,即C1得任一格子所在得行与列中都没有C2得格子。则有:

R(C)=∑(∑ri(C1)rk-i(C2))xk

=(∑ri(C1)xi)(∑rj(C2)xj)j=0nnkni=0i=0k=0∴R(C)=R(C1)R(C2)(4)i=0krk(C)=∑ri(C1)rk－i(C2)故3.2.容斥原理—应用利用(３)与(４),可以把一个比较复杂得棋盘逐步分解成相对比较简单得棋盘,从而得到其棋盘多项式。例

R()=xR()+R()=x(1+x)2+(1+2x)2=1+5x+6x2+x3*R()=xR()+R()=1+6x+10x2+4