研究生精品课程研究生精品课程研究生精品课程研究生精品课程 组合数学组合数学组合数学组合数学第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 3.1 De Morgan 3.1 De Morgan 3.1 De Morgan 3.1 De Morgan 定理定理定理定理3.2 3.2 3.2 3.2 容斥定理容斥定理容斥定理容斥定理3.3 3.3 3.3 3.3 容斥原理举例容斥原理举例容斥原理举例容斥原理举例3.10 n3.10 n3.10 n3.10 n对夫妻问题对夫妻问题对夫妻问题对夫妻问题3.12 3.12 3.12 3.12 鸽巢原理鸽巢原理鸽巢原理鸽巢原理3.13 3.13 3.13 3.13 鸽巢原理举例鸽巢原理举例鸽巢原理举例鸽巢原理举例课后习题解答课后习题解答课后习题解答课后习题解答2第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 例例3-13-1 求不超过20的正整数中为2或3的倍数的数3.1 De Morgan3.1 De Morgan定理定理解： 不超过20的数中2的倍数有10个： 2，4，6，8，10，12，14，16，18，20 不超过20的数中3的倍数有6个：3，6，9，12，15，18,但其中为2或3的倍数的数只有13个，而不是10+6=16 个。
即 2，3,4,6,8,9,10,12,14,15,16,18,20其中6，12，18同时为2和3的倍数若计算10+6=16，则重复计算了一次6,12,18.3第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 3.1 De Morgan定理德摩根德摩根(De Morgan)(De Morgan)定理：定理：若A和B是集合U的子集，则4第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 证明证明：(1)的证明 (3-1)3.1 De Morgan3.1 De Morgan定理定理设则 等价于和 同时成立，所以有 5第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 反之，若(2)的证明和（1）类似，从略.3.1 De Morgan3.1 De Morgan定理定理6第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 3.1 De Morgan3.1 De Morgan定理定理图 3-1UBA7第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 u 德摩根德摩根(De Morgan)(De Morgan)定理的推广：定理的推广：设设A A1 1,A,A2 2, ,A,An n是是U U的子集，则：的子集，则：3.1 De Morgan3.1 De Morgan定理定理8第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 即定理对n+1也是正确的。
证明证明：采用数学归纳法（1） n=2时定理成立假定n时成立，即：正确3.1 De Morgan3.1 De Morgan定理定理9第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 u容斥原理的两个基本公式容斥原理的两个基本公式若:则有3.2 3.2 容斥定理容斥定理10第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 定理定理3-1图3-23.2 3.2 容斥定理容斥定理11第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 定理定理3.1证明：证明：根据：根据：3.2 3.2 容斥定理容斥定理12第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 例例3-23-2：一个学校只有数学，物理，化学：一个学校只有数学，物理，化学3 3门课门课 已知修这已知修这3 3门课的学生人数分别有门课的学生人数分别有170,130,120170,130,120人；同时修数学、物理两门课的学生有人；同时修数学、物理两门课的学生有4545人；同人；同时修数学、化学的有时修数学、化学的有2020人；同时修物理、化学的人；同时修物理、化学的有有2222人；同时修三门课的学生有人；同时修三门课的学生有3 3人，试计算在人，试计算在校的学生有几人。
校的学生有几人 解：令解：令M M为修数学课的学生集合；为修数学课的学生集合；F F为修为修物理课的学生集合；物理课的学生集合；C C为修化学课的学生集合，按为修化学课的学生集合，按照已知条件：照已知条件：3.2 3.2 容斥定理容斥定理13第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 假定学校的学生至少要学一门课程假定学校的学生至少要学一门课程则在校学生数为：则在校学生数为：=170+130+120-45-20-22+3=3363.2 3.2 容斥定理容斥定理14第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 例3-3：S=1,2,3,600,求其中被2，3，5除尽的数的数目解：令A，B，C分别表示S中被2，3，5除尽的数3.2 3.2 容斥定理容斥定理15第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 定理3-2 设A1,A2,An是n个有限集合，则3.2 3.2 容斥定理容斥定理16第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 设设N N为全集为全集U U的元素个数，那么不属于的元素个数，那么不属于A A的元的元素数目等于集合的全体减去属于素数目等于集合的全体减去属于A A的元素个数。
的元素个数记作：记作：根据德摩根定理根据德摩根定理3.2 3.2 容斥定理容斥定理17第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 3.2 3.2 容斥定理容斥定理18第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 u容斥原理的两种形式容斥原理的两种形式: :形式一：3.2 3.2 容斥定理容斥定理19第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 形式二：形式二：3.2 3.2 容斥定理容斥定理20第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 例例3-4 3-4 求求a,b,c,d,e,fa,b,c,d,e,f这这6 6个字母的全排列个字母的全排列中不允许出现中不允许出现aceace和和dfdf图像的排列数图像的排列数解：解：S S是由这是由这6 6个字符组成的全排列，个字符组成的全排列，A A1 1是出现是出现aceace图图像的排列，即像的排列，即aceace作为一个单元参加全排列，作为一个单元参加全排列，A A是是dfdf作为一个单元参加的排列作为一个单元参加的排列不允许出现不允许出现aceace和和dfdf的排列数为：的排列数为：3.3 3.3 容斥原理举例容斥原理举例21第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 例例3-5 3-5 求由求由a,b,c,da,b,c,d这这4 4个字符构成个字符构成n n位位符号串，其中符号串，其中a,b,ca,b,c至少出现一次的数目。
至少出现一次的数目a,b,ca,b,c至少出现一次的事件的反面就是至少出现一次的事件的反面就是a,b,ca,b,c都不出现令都不出现令A A1 1，A A2 2，A A3 3分别为分别为n n位符号串中位符号串中不出现不出现a,b,ca,b,c的事件S S是是a,b,c,da,b,c,d组成的组成的n n位位符号串的全体符号串的全体解解( (用容斥原理用容斥原理) )3.3 3.3 容斥原理举例容斥原理举例22第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 3.3 3.3 容斥原理举例容斥原理举例23第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 3.3 3.3 容斥原理举例容斥原理举例24第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 例例3-6 3-6 求不超过求不超过120120的素数的个数的素数的个数 因为因为11112 2=121,=121,不超过不超过120120的合数必然是的合数必然是2,3,5,72,3,5,7的倍数，而且不超过的倍数，而且不超过120120的合数的因的合数的因数只能是数只能是2,3,5,72,3,5,7也就是被也就是被2,3,52,3,5或或7 7除尽。
因除尽因为它们是小于为它们是小于1111的素数解解：3.3 3.3 容斥原理举例容斥原理举例25第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 设设A Ai i为不超过为不超过120120的数同时又是的数同时又是i i的倍数的集合，的倍数的集合，i=2,3,5,7.i=2,3,5,7.3.3 3.3 容斥原理举例容斥原理举例26第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 3.3 3.3 容斥原理举例容斥原理举例27第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 注意：注意：2727包括了包括了1 1这个非素数，另外这个非素数，另外2,3,5,72,3,5,7本本身是素数没有计算在内，因此满足要求的素数身是素数没有计算在内，因此满足要求的素数是是27+4-1=3027+4-1=30个3.3 3.3 容斥原理举例容斥原理举例28第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 n对夫妻相邻而坐，求夫妻不相邻的方案数1）n个人围圆桌而坐的方案数： 3.10 n对夫妻问题29第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 3.10 n对夫妻问题(2) 2n(2) 2n个人围圆桌而坐的方案数为个人围圆桌而坐的方案数为(2n-1)!(2n-1)! Ai相当于将第相当于将第i对夫妻作为一个对象围圆桌对夫妻作为一个对象围圆桌而坐然后换位，故而坐然后换位，故30第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 3.10 n对夫妻问题故夫妻不相邻的方案数为故夫妻不相邻的方案数为 31第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 1 1、366366个人中必然有至少两人生日相同个人中必然有至少两人生日相同( (不包括闰年不包括闰年) )；2 2、抽屉里散放着、抽屉里散放着1010双手套，从中任意抽取双手套，从中任意抽取1111只，其中至少只，其中至少 有两只是成双的；有两只是成双的；3 3、某次会议有、某次会议有n n位代表参加，则至少有两个人认识的人数是位代表参加，则至少有两个人认识的人数是 一样的；一样的；4 4、任给、任给5 5个整数，其中至少有个整数，其中至少有3 3个数的和被个数的和被3 3除尽；除尽；3.12 鸽巢原理32第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 鸽巢原理：鸽巢原理： n n个鸽子巢，若有个鸽子巢，若有n+1n+1只鸽子在里面，则只鸽子在里面，则至少有一个巢里的鸽子数不少于至少有一个巢里的鸽子数不少于2 2。
3.12 鸽巢原理33第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 例例3-26 3-26 从从1 1到到2n2n的的2n2n个正整数中任取个正整数中任取n+1n+1个数，则这个数，则这n+1n+1个个数中至少有一对数，其中一个数是另一个数的倍数数中至少有一对数，其中一个数是另一个数的倍数解解.3.12 鸽巢原理举例鸽巢原理举例34第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 例例3-27 3-27 设设a a1,1,a a2 2,.a,.am m 是正整数序列，则至少存在整数是正整数序列，则至少存在整数k k和和L L，1 k1 kLmLm, ,使得和是使得和是m m的倍数解解.3.12 鸽巢原理举例35第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 例例3-28 3-28 已知已知X=1X=1，2 2，3 3，4 4，.9.9，任意将，任意将X X剖分成两个剖分成两个部分部分P P和和Q Q其中至少有一个集合含有其中至少有一个集合含有3 3个等差的数个等差的数解解.3.12 鸽巢原理举例36第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理 证明证明 设所取的设所取的n+1n+1个是个是 a a1 1,a,a2 2,a,a3 3,.a,.an n,a,an+1n+1 对对a a1 1,a,a2 2,a,a3 3,.a,.an n,a,an+1n+1序列的每一个数去掉一切序列的每一个数去掉一切2 2的因子，。