鸽巢原理 容斥原理

鸽巢原理 容斥原理2容斥原理 集合论加法法则： 若|A|=m，|B|=n，AB= ， 则|AB|=m+n。 思考：若A、B为任意的有限集合，则|AB|=？第1页/共27页3容斥原理| |ABABAB&定理定理1 1 若A、B为任意的有限集合，则 第2页/共27页4容斥原理 例1 求不超过20的正整数中是2的倍数或3的倍数的数的个数。 解：设A、B分别表示不超过20的正整数中2的倍数的数的集合和3的倍数的数的集合，则问题转化为求|AB| 易见|A|=10，|B|=6，|AB |=3 因此|AB|=|A|+|B|- | AB |=13第3页/共27页5容斥原理&定理定理2 2 若A、B、C为任意的有限集合，则 | | | |ABCABCABACBCABC | ?ABC第4页/共27页6容斥原理 利用数学归纳法可获得容斥原理的一般形式： 定理定理3 3 设12,.,nA AA是有限集合，则12111112|.|. ( 1)|.|nnnniijijkiij iij i kjnnAAAAAAAAAAAA 第5页/共27页7容斥原理 容斥原理的等价形式： 定理定理4 4 设12,.,nA AA是有限集合，则1211121|.| | . ( 1) |.|nnniijiij innijknij i kjAAAEAAAAAAAAA 第6页/共27页8容斥原理 例2 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理、化学的22人。同时修三门的3人。问这学校共有多少学生？ 解 令M、P、C分别为修数学、物理、化学的学生集合 则该问题转化为求|MPC| |MPCMPCMPMCPCMPC170 130 1204520223336第7页/共27页9容斥原理 例3 求11000中不能被5、6和8中任何一数整除的整数的个数 解：设11000之间的整数构成全集E A、B、C分别表示其中可被5，6，8整除的数的集合 则问题转化为求|ABC| 由于ABC=1000/5，6，8=1000/120=8 AB=1000/5，6=33 AC=1000/5，8=25 BC=1000/6，8=41 A=1000/5=200 B=1000/6=166 C=1000/8=125第8页/共27页10容斥原理 由ABC=8 AB=33 AC=25 BC=41 A=200 B=166 C=125 所以由容斥原理，不能被5，6和8整除的整数的个数为 |ABC| =|E|-（A+B+C）+（AB+AC+BC）-ABC =600第9页/共27页11容斥原理 例4 求a,b,c,d,e,f六个字母的全排列中不出现ace和df的排列数。 解 设E为全排列集合，A为出现ace的排列的集合，B为出现df的排列的集合， | 6!,| 4!,| 5!,| 3!EABAB则根据容斥原理，不出现ace和df的排列数为| 6! (5! 4!)3!582AB第10页/共27页12容斥原理在组合数学中的应用 错排问题 有禁止模式的排列问题 第11页/共27页13错排问题 错排问题是指对n个元素依次给以标号1,2,n，求每个元素都不在自己原来位置上的排列数。 设Ai (i=1,2,n)为数i在第i位上的全体排列， 因数字i不能动，因而有|Ai|=(n-1)!，i=1,2,n 同理1212| (2)!, ,1,2,.,|.| ()!|.| 0!kijiiinAAni jnijAAAnkAAA 第12页/共27页14错排问题 定理 用Dn表示1, 2, , n的全部错排个数，则12|.|!(1)!(2)! .( 1)0!12111!(1.( 1)1!2!nnnnDAAAnnnnnnnnn 第13页/共27页15错排问题 例 在8个字母ABCDEFGH的全排列中，求 （1）仅ACEG四个字母不在原来位置上的排列数 （2）只有4个字母不在原来位置的排列数 （3）ACEG四个字母不在原来上的排列数 解 （1）8个字母中仅ACEG四个字母不在原来位置上，其余4个字母保持不动，相当于4个元素的错排11114! (1)91!2!3!4!排列数为（2）排列数为C(8, 4)9=630第14页/共27页16错排问题 （3）8个字母的全排列中，令A1, A2, A3, A4分别表示A, C, E, G在原来位置上的排列 则满足要求的排列为 1234|44448!7!6!5!4!123424024AAAA 第15页/共27页17有禁止模式的排列问题 有禁止模式的排列问题主要解决某些元素之间的某种相对位置不能出现的一类排列。 下面我们仅讨论有禁止模式的排列问题中最简单的一种相邻禁位问题。第16页/共27页18相邻禁位问题 相邻禁位问题：求由集合1, 2, , n产生的不出现12, 34, , n(n-1)的全排列数 设Qn表示1, 2, , n的不出现12, 34, , n(n-1)的全排列数 则Q1 =1，满足要求的排列为1； Q2 =1，满足要求的排列为21； Q3 =3，满足要求的排列为213, 321, 132； Q4 =11，满足要求的排列为：4132, 3142, 2143，1324, 4213, 3214, 2413, 1432, 4321, 3241, 2431Qn =？第17页/共27页19相邻禁位问题 设S为1, 2, n的所有全排列，则|S|=n!， 设Ai （i=1,2,n-1）表示全排列中出现i(i+1)模式的排列的集合 则Ai中的每一个排列都可看作n-1元集合1, 2, i(i+1), n的一个全排列，所以|Ai|=(n-1)! 同理12121| (2)!|.| ()!|.| 1!kijiiinAAnAAAnkAAA第18页/共27页20相邻禁位问题121111211111|.| | .( 1)|.|111 !(1)!(2)! .( 1)1!121nnnniijniij nnQAAASAAAAAAnnnnnnn 第19页/共27页21课后练习 （1）求1250之间能被2、3、5和7任何一数整除的整数个数。 （2）在由a、b、c和d这4个字符构成的n位字符串中，求a、b、c至少出现一次的符号串的数目。 （3）数1，2，9的全排列中，求偶数在原来位置上，其余都不在原来位置的错排数目。第20页/共27页22鸽巢原理 第21页/共27页23鸽巢原理 鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽屉原理。 原理描述：若有n个鸽子巢，n+1只鸽子，则至少有一个鸽子巢里住着两只鸽子。 定理（鸽巢原理） 如果把n+1个物体放入n个盒子，那么至少有一个盒子中有两个或更多的物品。第22页/共27页24举例 例1 367人中至少有2人的生日相同。 例2 在某班中有50名学生，其中年龄最大的20岁，最小的17岁。证明这个班中至少有两名学生是同年同月生的。 例3 在边长为2的等边三角形内任意放置5个点，则其中至少有两个点的距离小于1。 例4 某次会议有n位代表参加，每位代表至少认识其余n-1位中的一位，则这n位代表中，至少有两位认识的人数相等。第23页/共27页25举例 例5 设a1, a2, ,a100是由1和2组成的序列 ，已知从其中任一数开始的连续10个数的和不超过16，即ai+ai+1+ai+916 (1i91)，则存在h和k (kh)，使得ah+1+ah+2+ak=39。 证明： 11,2,.,100jjiiSaj，设12100.SSS显然100110112091100(.)(.).(.)Saaaaaa根据题义有10010 16160S 作序列121001100,.,39,.,39S SSSS，共200项。 设39,39khkhSSkh SS即1.39hkaa第24页/共27页26思考题 从1到2n的正整数中任取n+1个数，则在这n+1个数中，至少有一对数，其中一个是另一个的倍数。证明:假设这n+1个数121,.,na aa令 2,1,2,.,1iiiar in,其中ri为奇数1,2 irn而,并且1,2n中只有n个奇数pqrrr因此必然存在 若 22pqpqarar 则 2ppar2qqar是 的倍数 第25页/共27页27课后练习题 1、在34的长方形内任意放置7个点，在其中至少有两个点的距离小于等于51/2。 第26页/共27页