1、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)定理：定理：
2、若A和B是集合U的子集，则BABABABA)2()1(4 证明证明：(1)的证明。(3-1)3.1 De Morgan3.1 De Morgan定理定理BAx,xAB设BAx则 AxBx等价于和 同时成立，AABxAB 所以有 5 反之，若(2)的证明和（1）类似，从略.3.1 De Morgan3.1 De Morgan定理定理.xAxBxAB 和亦即xABxAxB,即和xABxABxABxAB 6 3.1 De Morgan3.1 De Morgan定理定理图 3-1UBAA B7 u 德摩根德摩根(De Morgan)(De Morgan)定理的推广：定理的推广：设设A A1 1,A,A
3、2 2,A,An n是是U U的子集，则：的子集，则：3.1 De Morgan3.1 De Morgan定理定理nnAAAAAA.)1(2121nnAAAAAA.)2(21218 即定理对n+1也是正确的。证明证明：采用数学归纳法（1）n=2时定理成立。假定n时成立，即：正确212.nnAAAAA1A2111121121.(.)(.nnnnnnnnAAAAAAAAAAAAAA1则 A3.1 De Morgan3.1 De Morgan定理定理9 u容斥原理的两个基本公式容斥原理的两个基本公式若:BABABA则BA如果BABABA 有3.2 3.2 容斥定理容斥定理10 定理定理3-1CBAC
4、BCABACBACBA CBACBCABACBA图3-23.2 3.2 容斥定理容斥定理11 定理定理3.1CBACBCABACBACBA 证明：证明：CBACBA)()()()(CBCACBA)()()(CBCACBACBACBA)(CBABA根据：根据：CBACBCACBACBCABACBACBA 3.2 3.2 容斥定理容斥定理CBA)(12 例例3-23-2：一个学校只有数学，物理，化学：一个学校只有数学，物理，化学3 3门课门课 。已知修这已知修这3 3门课的学生人数分别有门课的学生人数分别有170,130,120170,130,120人；同时修数学、物理两门课的学生有人；同时修数学
5、、物理两门课的学生有4545人；同人；同时修数学、化学的有时修数学、化学的有2020人；同时修物理、化学的人；同时修物理、化学的有有2222人；同时修三门课的学生有人；同时修三门课的学生有3 3人，试计算在人，试计算在校的学生有几人。校的学生有几人。解：令解：令M M为修数学课的学生集合；为修数学课的学生集合；F F为修为修物理课的学生集合；物理课的学生集合；C C为修化学课的学生集合，为修化学课的学生集合，按照已知条件：按照已知条件：22,20,45CFCMFM120,130,170CFM3CFM3.2 3.2 容斥定理容斥定理13 假定学校的学生至少要学一门课程。假定学校的学生至少要学一门
6、课程。则在校学生数为：则在校学生数为：=170+130+120-45-20-22+3=336。CFMCFCMFMCFM CFM 3.2 3.2 容斥定理容斥定理14 例3-3：S=1,2,3,600,求其中被2，3，5除尽的数的数目。解：令A，B，C分别表示S中被2，3，5除尽的数。600600600300,200,120,235600600100,60,2*31060060040,20,1530 ABCABACBCABC440204060100120200300 CBACBCABACBACBA3.2 3.2 容斥定理容斥定理15 定理3-2 设A1,A2,An是n个有限集合，则nnniijj
7、hhjiniijjiniinAAAAAAAAAAAA.)1(.211111213.2 3.2 容斥定理容斥定理16 设设N N为全集为全集U U的元素个数，那么不属于的元素个数，那么不属于A A的元的元素数目等于集合的全体减去属于素数目等于集合的全体减去属于A A的元素个数。的元素个数。记作：记作：ANAnnA.AAA.AA2121根据德摩根定理根据德摩根定理3.2 3.2 容斥定理容斥定理17 nA.AAN21nnA.AAA.AA2121nnniijjhhjiniijjiniiAAAAAAAAAN.)1(.21111 3.2 3.2 容斥定理容斥定理18 u容斥原理的两种形式容斥原理的两种形
8、式:nnniijjhhjiniijjiniinAAAAAAAAAAAA.)1(.21111121形式一：3.2 3.2 容斥定理容斥定理19 12nAA.AnnniijjhhjiniijjiniiAAAAAAAAAN.)1(.21111 形式二：形式二：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图图像的排列，即像
9、的排列，即aceace作为一个单元参加全排列，作为一个单元参加全排列，A A是是dfdf作为一个单元参加的排列。作为一个单元参加的排列。不允许出现不允许出现aceace和和dfdf的排列数为：的排列数为：3.3 3.3 容斥原理举例容斥原理举例,!6S,!41A!52A!321AA 21AA 2121)(AAAAS582!3)!4!5(!621 例例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至少出现一次的事件的反面就是至少出现一次的事件的反面
10、就是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 nS4nAAA33213,2,1,2jijiAAnji1kjiAAA1Aa至少出现一次的集合是2Ab至少出现一次的集合是3Ac至少出现一次的集合是321,AAAcba至少出现一次的集合是3.3 3.3 容斥原理举例容斥原理举例23 321AAA3213231213
11、21 )()(4AAAAAAAAAAAAn123334nnn3.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为不超过为不
12、超过120120的数同时又是的数同时又是i i的倍数的集合，的倍数的集合，i=2,3,5,7.i=2,3,5,7.6021202A4031203A2451205A1771207A3.3 3.3 容斥原理举例容斥原理举例26 203212032AA 125212052AA 87212072AA 85312053AA 57312073AA 37512075AA4532120532AAA2732120732AAA1752120752AAA1753120753AAA075321207532AAAA3.3 3.3 容斥原理举例容斥原理举例27 注意：注意：2727包括了包括了1 1这个非素数，另外这个非
13、素数，另外2,3,5,72,3,5,7本本身是素数没有计算在内，因此满足要求的素数身是素数没有计算在内，因此满足要求的素数是是27+4-1=3027+4-1=30个。个。7532AAAA7532120AAAA757353725232AAAAAAAAAAAA753752732532AAAAAAAAAAAA7532AAAA27)1124()35881220()17244060(1203.3 3.3 容斥原理举例容斥原理举例28 n对夫妻相邻而坐，求夫妻不相邻的方案数。（1）n个人围圆桌而坐的方案数：nn2)!1(3.10 n对夫妻问题nnniijjiniinN.)1(.21112129 3.10
14、n对夫妻问题(2)2n(2)2n个人围圆桌而坐的方案数为个人围圆桌而坐的方案数为(2n-1)!(2n-1)!2)!22(nAi22)!32(nAAjiAi相当于将第相当于将第i对夫妻作为一个对象围圆桌对夫妻作为一个对象围圆桌而坐然后换位，故而坐然后换位，故nnAAAn2)!1(.2130 3.10 n对夫妻问题故夫妻不相邻的方案数为故夫妻不相邻的方案数为 )!1n)(n,n(C)1(.)!3n2)(2,n(C2)!2n2)(1,n(C2)!1n2(Nn2)!1hn2)(h,n(C2)1(hn0hh31 1 1、366366个人中必然有至少两人生日相同个人中必然有至少两人生日相同(不包括闰年不包
15、括闰年)；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
16、 例例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，任意将，
17、任意将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的因子，直至的因子，直至剩下一个奇数为止，例如，剩下一个奇数为止，例如，68=268=2*34=234=22 2*1717，去掉，去掉2 2的因子的因子2 22 2，留留下奇数
18、下奇数1717，结果得到由奇数组成的序列，结果得到由奇数组成的序列 r r1 1,r,r2 2,r,r3 3.,r.,rn+1n+1 1 1到到2n2n中只有中只有n n个奇数，故序列个奇数，故序列r r中至少有两个是相同的。设为中至少有两个是相同的。设为r=r=r ri i=r rj j故对应的有故对应的有 a ai i=2=2aiair,ar,aj=j=2 2ajajr r 若若a ai i a aj j,则则a ai i 是是a aj j的倍数的倍数 题目题目.3.12 鸽巢原理举例37 证明证明 构造一个序列构造一个序列s s1 1=a=a1 1,s,s2 2=a=a1 1+a+a2 2,s,s3 3=a=a1 1+a+a2 2+a+a3 3,s sm m=a=a1 1+a+a2 2+a+am m,则则s s1 1ss2 2s sm m 有两种可能有两种可能(1)(1)若有一个若有一个s sh h是是m m的倍数，那么上式成立。的倍数，那么上式成立。序列序列s s1 1=a=a1 1,s,s2 2=a=a1 1+a+a2 2,s,s3 3=a=a1 1+a+a2 2+a+a3 3,s sm m=a=a1 1+a+a2 2+a+am m,则则s s1 1ss2 2inh=0nhn课后习题解答课后习题解答i=1
