第3章 容斥原理
第一节 引论
在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。 先考虑下面几个简单的问题。
例1 求1到600间不能被6整除的整数的个数。
例2 求{1,2,?,n}的1不在第一个位置上的全排列的个数。
例3 求不超过20的正整数中，是2的倍数或是3的倍数的数的个数。
第二节 容斥原理
定理3.2.1 设S是有限集合，P1,P2,?,Pm是同集合S有关的m个性质，设Ai是S中具有性质Pi的元素构成的集合(1?i?m),Ai是S中不具有性质Pi的元素构成的集合
(1?i?m)，则S中不具性质P1,P2,?,Pm的元素的个数为
A1?A2???Am?S??Ai?i?1m{1,2,...,m}的2组合?Ai?Aj?{1,2,...,m}的3组合?Ai?Aj?Ak
???(?1)mA1?A2???Am。
推论3.2.1 设S是有限集合，P1,P2,?,Pm是同集合S有关的m个性质，设Ai是S中具有性质Pi的元素构成的集合(1?i?m), 则S中至少具有一个性质Pi的元素的个数为
A1?A2???Am??Ai?i?1m{1,2,...,m}的2组合?Ai?Aj?{1,2,...,m}的3组合?Ai?Aj?Ak
???(?1)m?1A1?A2???Am
证明一：（数学归纳法）
当n?2 时，要证明：|A1?A2|?|A1|?|A2|?|A1?A2|
这可由A1?A2等于不相交的两个集合A1和A2\\(A1?A2)的并推出， 而A2等于不相交的两个集合A2\\(A1?A2)和A1?A2的并。 所以，|A1?A2|?|A1|?|A2\\(A1?A2)| ①
|A2|?|A2\\(A1?A2)|?|A1?A2| ②
由①、②知|A1?A2|?|A1|?|A2|?|A1?A2| 假设对n?1个集合，要证的等式成立； 对n个集合时，有
| ?|nn?1n?1n?1|?|A??A?iii?1n?1i?1i?1An?|?|Ai?|i?1n?1i?1|An?|?|(A?ii?1 n)A|?A|?|Ain|?|?(Ai?An)|
?I?{1,2,?,n?1}I???(?1)|I|?1|?Ai|?|An|?i?II?{1,2,?,n?1}I???(?1)|I|?1|?(Ai?An)|
i?I 将和式中具有相同因子数的项合并，即可得到要证明的等式。
证法二：（贡献法）
如果x??Ai，则x?Ai(i?1,2,?,n)，公式两端均为0，成立；
如果x??Ai，设x恰属于m个Ai，1?m?n。此时，公式右端中?Ai对x共
i?1i?1ni?1nn1计数Cm次，
1?i?j?n?2Ai?Aj对x共计数Cm次，
1?i?j?k?n?3Ai?Aj?Ak对x共计数Cm次，?..，
1?i1???iM?n?m|Ai1???Aim|对x共计数Cm次，并且在此后的各项中，x均未
123m被计数，故公式右端对x共计数Cm ?Cm?Cm???(?1)m?1Cm00123m?Cm?(Cm?Cm?Cm?Cm???(?1)mCm)?1?(1?1)m?1
故等式成立。
例1 1与1000之间不能被5，6，8整除的整数有多少个？
例2 展求由a,b,c,d四个字符构成的n位字符串中，a,b,c,d至少出现一次的字符串的数目。
例3 在欧拉函数?(n)表示小于n且与n互素的整数的个数。求?(n)。
解： 将n分解成素因子的乘积形式：
ii2n?p1i1p2...pqq 则有
?(n)?n(1?111)(1?)?(1?)。 p1p2pq
例4 若图G有n个顶点，且不含有完全k子图(k?2)，则它的顶点的次数d(x)满足不等式
?(k?2)n? mind(x)???x?X?k?1?
问题： 设S是一有限集合，P?{P1,P2,?,Pm}是S上的性质集合。求集合S中恰好具有P中r个性质的元素个数N(r)(1?r?m)。
S中具有性质P用N(Pi1,Pi2,?,Pik)表示i1,Pi2,?,Pik的元素个数，规定w(0)?S，令
w(k)?1?i1?i2?...?ik?m?N(Pi1,Pi2,?,Pik)。
r定理3.2.2 设集合S中具有性质集合P?{P1,P2,?,Pm}中恰好个性质的元素的个数为N(r)，则
?r?1??r?2?m?r?m?N(r)?w(r)??w(1)?w(2)???(?1)?????w(m)。
rr?????r?
例5 某学校有12位教师，已知教数学课的教师有8位，教物理课的教师有6位，教化学课的教师有5位。其中，有5位教师既教数学又教物理，有4位教师既教数学又教化学，兼教物理和化学的有3位教师，还有3位教师兼教这三门课。试问： （1）教数、理、化以外的课的教师有几位？ （2）只教数、理、化中一门课的教师有几位？ （3）正好教数、理、化中两门课的教师有几位？
第三节 容斥原理的应用
3.3.1 具有有限重复数的多重集合的r组合数
例1 求S?{3?a,4?b,5?c}的10组合数。
3.3.2 错排问题
错排问题的提法：
集合{1,2,?,n}的一个错排是该集合的一个满足条件
ij?j(1?j?n)
的全排列i1i2?in，即集合{1,2,?,n}的一个没有一个数字在它的自然顺序位置上的全排列。试求的全部错排个数Dn。
定理3.3.1 对任意正整数n，有
1111Dn?n!(1??????(?1)n)。
1!2!3!n!
证明： 记S为a1,a2,?,an 的所有排列的集合，Sk是S中所有满足ak在第k号位置上的排列的集合，k?1,2,?,n。
显然|S|?n!，|Si|?(n?1)!，Si?Sj|?(n?2)!，??，
|S1???Sn|?1
所以，|S1???Sn|?|S|?|S1???Sn|
12 ?n!?[Cn(n?1)!?Cn(n?2)!???(?1)n?1]
?n 1!2!n!
3.3.3 有禁止模式的排列问题
问题：
设某班有8位学生排成一队出去散步，第二天再列队时，同学们都不希望他前面的同学与前一天相同，问有多少种排法？
将上述例子推广并进行抽象，得问题的提法：
?n,}用Qn表示{1,2,的不出现12,23,?,(n?1)n这些模式的全排列的个数(规定
Q1?1)，求Qn。
定理3.3.2 设对任意正整数n,有
?n?1??n?1?n?1?n?1?QN?n!??(n?1)!?(n?2)!???(?1)?????1! ?1??2??n?1?
例2 多重集合M?{4?x,3?y,2?z}的全排列中不出现xxxx,yyy,zz模式的排列有多少种？
例3(menage问题) n对夫妇参加宴会围桌就座，要求男女相间并且每对夫妇两人不得相邻，问有多少种就座方式？
解 利用容斥原理，可求得就座方式总数为
n2n?2n?k?Un??(?1)k??(n?k)!。
2n?k?k?k?0
第四节 Mobius反演及可重复圆排列
Mobius函数：
对任意自然数n，若n?1，则n可唯一分解为素数幂的乘积
l1l2n?p1p2?prlr,(3.4.1)
其中，p1,p2?pr是不同的素数，li?1(1?i?r)。定义Mobius函数?(n)为
?1若n?1；??(n)??0若(3.4.1)中某li?1；
?(?1)r若(3.4.1)中l1=l2??lr?1。?
引理3.4.1 对任意正整数n，有
?1?(d)???d|n?0(若n?1)；(若n?1)。
证明: 当n=1时, 定理显然成立. 若n?1, 设
aka2n?p1a1p2?pk, n1?p1p2?pk。
??(d)???(d)
d|nd|n1??(1)?1?i?k??(p)??i?(pipj)?...??(p1?pk)
1?i?j?k