组合数学-第九节：容斥原理

3.2容斥原理将3.1节讨论的原理进一步推广，总结成一般性规律，就得到定理3.2.1所描述的容斥原理。定理3.2.1设S是有限集合，12,mPPP是同集合S有关的m个性质，设iA是S中具有性质iP的元素构成的集合1im，iA是S中不具有性质iP的元素构成的集合1im，则S中不具有性质12,mPPP的元素个数为1211,2,21,2,2121mmiijimijikmmmAAASAAAAAAAAA的合的合（3.2.1）证明可以利用等式（3.1.1），通过对m作归纳进行证明。下面通过其组合意义来证明。等式（3.2.1）的左端表示的是S中不具有性质12,mPPP的元素的个数。下面我们来证明：对于S中每个元素x，若x不具有性质12,mPPP，则对等式（3.2.1）的右端贡献1；否则，若x具有某个性质1iPim，则对等式（3.2.1）的右端贡献0，从而证（3.2.1）式。任给xS，则（1）若x不具有性质12,mPPP，即12,,mxAxAxA，则x在集合S中，但不在（3.2.1）式右端的任一其他集合中。所以，x对（3.2.1）式右端的贡献为1000101m（2）若x恰具有12,mPPP中的1nn个性质12,iiinPPP，则x对S的贡献为10n因x恰具有n个性质12,iiinPPP，所以x恰属于集合12,,niiiAAA，共n个。于是，x对iA的贡献为1nn从12,iiinPPP中选出两个性质，共有2n种，所以x恰在2n个形如kliiAAkl的集合中，x对ijAA的贡献为2n；……；同理，x对12niiiAAA的贡献为nn。而当kn时，0nk。所以x对（3.2.1）式右端的贡献为1101231012310mnnxnnnnnmnnnnnnx综上所述，（3.2.1）式的右端是集合S中不具有性质12,mPPP的元素的个数。证毕。若3m，则（3.2.1）式变成123123121323123AAASAAAAAAAAAAAA上面等式的右端共有13318项。若4m，则（3.2.1）式变成1234123412131412132312310002001661253325418600AAAASAAAAAAAAAAAAAAAAAAA例2求由,,,abcd四个字符构成的n位符号串中，,,,abcd至少出现一次的符号串的数目。解设1234,,,AAAA分别为不出现,,,abcd的n位符号串的集合。由于n位符号串的每一位都可取,,,abcd四个符号中的任一个，所以共有4n个。其中，不出现a的符号串的每一位都可取,,bcd中的任一个，共有3n个。类似地，有123431,2,3,42,,1,2,3,41,,;,,1,2,3,40ninijijkAiAAijijAAAijkijkAAAA互不相等而,,,abcd至少出现一次的符号串集合即为1234AAAA，于是1234123412131423243412312413423412344443624nnnnAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA例3欧拉函数n表示小于n且与n互素的整数的个数。求n。解将n分解成素因子的乘积形式：1212qiiiqnppp设iA为不大于n且为ip的倍数的自然数的集合1iq，则：1,2,iinAiqp因ip与jp互素ij，所以ip与jp的最小公倍数为ijpp，所以;,1,2,,ijijnAAijijqpp……。小于n并与n互素的自然数是集合1,2,,An中那些不属任何一个集合1,2,,iAiq的数，由容斥原理知124111121111211qiijiijqijkijqqqqiijqijqiijijkqqnAAAnAAAAAAAAAnnnnppppppnppp上面的和式正好是下列乘积的展开式：12111111qnnppp欧拉函数常用于数论中。例如，若21223n，则11121211423小于12并与12互素的正整数为1，5，7和11例4若图G有n个顶点，且不含有完全k子图2k，则它的顶点的次数dx满足不等式2min1xXkndxk（3.2.3）其中，X为图G的顶点集。证明设2102knpkrrk若不等式（3.2.3）不成立，则对任意的xX，均有1dxp。在图G中任取一个顶点1xX，用1A和相应的集合2A，由容斥原理得到121212220AAAAAApn这是因为集合1A和2A中的每一个至少包含1p个元素，而12AA中至多只有n个元素（G中全部顶点）。再任取一个顶点312xAA，同上，由容斥原理可得1233120AAApn等等。这样，我们可由归纳法得到对于211kkjjxA，取G中与1kx相邻的顶点集1kA，有12111221111121311210kkjjkjjkkkjkjjjAAAAAAApkpknnkpknkr因此，至少有一个顶点211kkjjxA。由jA的定义知12,,kxxx之间相互相邻，所以顶点集合12,,kxxx构成的导出子图是图G的完全k子图，这与题设矛盾。故不等式（3.2.3）成立。利用定理3.2.1和推论3.2.1，我们可以算出S中不具有性质12,mPPP的元素个数和S中具有12,mPPP中某个性质的元素个数。下面我们将其推广到更一般的情形。设S是一有限集合，12,mPPPP是S上的性质集合。现在的问题是要求出集合S中恰好具有P中r个性质的元素个数1Nrrm。现用12,iiikNPPP表示S中具有性质12,,kiiiPPP的元素个数，规定0wS，令12121,,kkiiiiiimwkNPPP若S中某元素x恰好具有P中0krr个性质12,,kriiiPPP，则从12,,kriiiPPP中取出k个性质的方法数为krk，因而x在wk中计算了krk次。而对于SK具有P中少于k个性质的元素，则不计算在内。例如，在本节的例1中，有123121323123200,166,125,,33,,25,,41,,,8,NPNPNPNPPNPPNPPNPPP于是01000,1200166125491,233254199,38.在2w中，对具有3个性质123,,PPP的元素，在1213,,,NPPNPP和23,NPP中各计算了一次，共3次。例如，120能被5，6，8整除，所以，121323120,120,120AAAAAA，即120在2w中共计算了3次。定理3.2.2设集合S中具有性质集合12,mPPPP恰好r个性质的元素个数为Nr，则12121.mrrrNrwrwrwrrmwmr（3.2.4）证明设x是集合S的一个元素，则（1）若x具有少于r个性质，则x对,1,wrwrwm的贡献均为0，从而对（3.2.4）式右端的贡献为0。（2）若x恰好具有r个性质，则x对wr的贡献为1，而对1,2,wrwrwm的贡献均为0，从而对（3.2.4）式右端的贡献为1。（3）若x恰好具有kkr个性质，则它对wr的贡献为kr，对1wr的贡献为,,1kr对wk的贡献为kk；当klm时，它对wl的贡献为0。从而，它对（3.2.4）式右端的贡献为11212111110lrklrlrklrlrkllrklxkrkrkrrrrrkkrkkllrkkrllrkkrrlkxr综上所述，（3.2.4）式的右端是S中恰好具有r个性质的元素个数。在例1中，有00123600N它是S中不能被5，6，8整除的整数个数，这正是容斥原理所反映的事实。23112311317N它是S中只能被5，6，8之一整除的整数个数。3223275Nww它是S中只能被5，6，8中的两个整数的整数个数。338Nw由此可见了，定理3.2.2是定理3.2.1的推广。例5某学校有12位教师，已知教数学课的教师有8位，教物理课的教师有6位，教化学课的教师有5位。其中，有5位教师既教数学又教物理，有4位教师兼教数学和化学，兼教物理和化学的有3位教师，还有3位教师兼教这三门课。试问：（1）教数、理、化以外的课的教师有几位？（2）只教数、理、化中一门课的教师有几位？（3）正好教数、理、化中两门课的教师有几位？解令12位教师中教数学课的教师属于集合1A，教物理课的教师属于集合2A，教化学的教师属于集合3A，则有1231213231238,6,5,5,4,3,3,AAAAAAAAAAAA（1）不教数学、物理、化学课的教师数目为123123121323123121286554332AAAAAAAAAAAAAAA（2）只教数、理、化中一门课的教师数目为1231213231231238652543334.NAAAAAAAAAAAA（3）正好教数、理、化中两门课的教师数目为12132312323543333.NAAAAAAAAA3.3容斥原理的应用：3.3.1具有有限重复数的多重集合的r组合数在第2章里，我们介绍了n元集合12,nxxx的r组合数为nr，多重集合12,,,nMxxx的r组合数为1nrr。在本节中，我们将应用容斥原理来计算重复数为任意给定的正整数的多重集合的r组合数。下面通过一下例子来看看怎样用容斥原理解决上述问题，然而例子中所用的方法却适用于一般的情况。例1求3,4,5Sabc的10组合数。解令,,Sabc，则S的10组合数为：10311266102设集合A是S的10组合全体，则66A，现在要求在10组合中a的个数小于等于3，b的个数小于等于4，c的个数小于等于5的组合数。定义性质集合123,,PPPP其中：1:10P组合中的a的个数大于等于4；2:10P组合中b的个数大于等于5；3:10P组合中c的个数大于等于6。将满足性质iP的10组合体记为13iAi。那么，1A的元素可以看作是由S的1046组