第三章容斥原理与鸽巢原理3.1容斥原理1.容斥原理对于求两个有限集合A和B的并集的元素数目：定理2例2一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理的学生45人；同时修数学、化学的20人；同时修物理、化学的22人；同时修三门的3人。假设每个学生至少修一门课，问这学校共有多少学生？类似的，对于四个集合有：对于一般的n个有限集合：例3求从1到500的整数中能被3或5除尽的数的个数。例4求由abcdef这六个字符组成的全排列中不允许出现ace和df图象的排列数。例5求4个x，3个y，2个z组成的全排列中不允许出现xxxx，yyy和zz图象的排列数。例6求由abcd这4个字符构成的n位符号串中，a、b、c都至少出现一次的数目。例7用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。类似有：|A2∩A3|=0，|A2∩A4|=20!，|A2∩A5|=20!，例8欧拉函数y(n)，是指小于n且与n互素的正整数的个数。因此小于n且与n互素的正整数的个数为：例9错排问题，是指1到n每个元素都不在自己原来位置上的排列的数目。例10第二类Stirling数，是指m个不同的球放到n个相同的盒子里，且无一空盒的方案数。例11求方程x1+x2+x3=15的非负整数解的数目。A1∩A2相当于求线性方程例12n对夫妻问题围圆桌而坐，所有夫妻都相邻的方案数为：(n-1)!2n。2.有禁区的排列为了求解有禁区的排列问题，除了容斥原理外，还需要另一个工具：棋盘多项式。设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。注意到rk(C)=rk-1(Ci)+rk(Ce)，因此有利用定义和这两个公式可以计算出棋盘多项式。下面回到有禁区的排列问题，有如下的定理：例14再解错排问题。3.广义容斥原理单修一门数学的用同样的方法还可以得到：一般的我们有如下的结论：例15某校有12个教师，已知教数学的有8位，教物理的有6位，教化学的5位；数理5位，数化4位，理、化3位；数理化3位。问教其他课的有几位？只教一门的有几位？只教两门的有几位？例16错排问题的推广：从1到n这n个整数中取r个进行排列，得到a1a2…ar。要求其中刚好有k个数满足ai=i。因此有：