第三章容斥原理和鸽巢原理§1容斥原理引论例[1，20]中2或3的倍数的个数[解]2的倍数是：2，4，6，8，10，12，14，16，18，20。10个3的倍数是：3，6，9，12，15，18。6个但答案不是10+6=16个，因为6，12，18在两类中重复计数，应减去。故答案是：16-3=13容斥原理研究有限集合的交或并的计数。[DeMorgan定理]论域U，补集证：(a)的证明。设,则相当于和同时成立，亦即反之，若DeMogan定理的推广：设正确§2容斥原理有性质A和B的元素个数。§3.2容斥原理§3.2容斥原理定理：§3.2容斥原理A例一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？令：M为修数学的学生集合；P为修物理的学生集合；C为修化学的学生集合；即学校学生数为336人。同理可推出：§3.2容斥原理§3.2容斥原理定理：设证：用数学归纳法证明。已知n=2时有§3.2容斥原理§3.2容斥原理§3.2容斥原理§3.2容斥原理§3.2容斥原理§3.2容斥原理其中N是集合U的元素个数，即不属于A的元素个数等于集合的全体减去属于A的元素的个数。一般有：(5)§3例根据容斥原理，不出现ace和df的排列数为：例2求从1到500的整数中能被3或5除尽的数的个数。解：令A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合被3或5除尽的数的个数为解：令A、B、C分别为n位符号串中不出现a，b，c符号的集合。由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是a，b，c至少出现一次的n位符号串集合即为例4。求不超过120的素数个数。§3.3例§3.3例§3.3例§3.3例注意：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7着四个数，又包含了1这个非素数。2，3，5，7本身是素数。故所求的不超过120的素数个数为：27+4-1=30例5。用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。解：所有排列中，令：§3.3例出现dog字样的排列，相当于把dog作为一个单元参加排列，故由于gum,dog可以在dogum字样中同时出现，故有：§3.3例由于god、depth、thing不可以同时出现，故有：故满足要求的排列数为：例6。求完全由n个布尔变量确定的布而函数的个数。解：设§3.3例§3.3例例7。欧拉函数(n)是求小于n且与n互素的数的个数。解：若n分解为素数的乘积§3.3例§3.3例即比60小且与60无公因子的数有16个：7，11，13，17。19。23，29，31，37，41，43，47，49，53，59，此外尚有一个1。§4错排问题§3.4错排问题每个元素都不在原来位置的排列数为例1。数1，2，…，9的全排列中，求偶数在原来位置上，其余都不在原来位置的错排数目。解：实际上是1，3，5，7，9五个数的错排问题，总数为：例2.在8个字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四个字母不在原来上的错排数目。§3.4错排问题例3。求8个字母A,B,C,D,E,F,G,H的全排列中只有4个不在原来位置的排列数。故8个字母的全排列中有4个不在原来位置上的排列数应为：C(8,4)·9=630§5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.5棋盘多项式和有限制排列§3.6一般公式§3.6一般公式§3.6一般公式§3.6一般公式§3.6一般公式§3.6一般公式§3.6一般公式§3.6一般公式§3.6一般公式§3.6一般公式§3.6一般公式§3.6一般公式§3.6一般公式§3.6一般公式§3.6一般公式§3.6一般公式§３.11反演§３.11反演§３.11反演§３.11反演§３.11反演§３.11反演§３.11反演§３.11反演§３.11反演§３.11反演§３.11反演§３.