鸽巢原理 容斥原理

null容斥原理容斥原理容斥原理容斥原理 容斥原理（相容排斥原理）是组合计数中常用到的一种方法。 例1 求不超过20的正整数中是2的倍数或3的倍数的数的个数。 不超过20的正整数中是2的倍数的数有10个，即2, 4, 6, 8, 10, 12, 14, 16, 18, 20。不超过20的正整数中是3的倍数的数有6个，即3, 6, 9, 12, 15, 18。 但是不超过20的正整数中是2的倍数或3的倍数的数的个数不是10+6=16个，而是13个，因为其中6, 12, 18这三个数既是2的倍数又是3的倍数。容斥原理容斥原理集合论加法法则： 若|A|=m，|B|=n，AB= ， 则|AB|=m+n。 思考：若A、B为任意的有限集合，则|AB|=？容斥原理容斥原理定理1 若A、B为任意的有限集合，则 容斥原理容斥原理例1 求不超过20的正整数中是2的倍数或3的倍数的数的个数。 解：设A、B分别表示不超过20的正整数中2的倍数的数的集合和3的倍数的数的集合，则问题转化为求|AB| 易见|A|=10，|B|=6，|AB |=3 因此|AB|=|A|+|B|- | AB |=13容斥原理容斥原理定理2 若A、B、C为任意的有限集合，则 容斥原理容斥原理利用数学归纳法可获得容斥原理的一般形式： 定理3 设是有限集合，则容斥原理容斥原理容斥原理的等价形式： 定理4 设是有限集合，则容斥原理容斥原理例2 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理、化学的22人。同时修三门的3人。问这学校共有多少学生？ 解 令M、P、C分别为修数学、物理、化学的学生集合 则该问题转化为求|MPC|容斥原理容斥原理例3 求1~1000中不能被5、6和8中任何一数整除的整数的个数 解：设1~1000之间的整数构成全集E A、B、C分别表示其中可被5，6，8整除的数的集合 则问题转化为求|~A~B~C| 由于ABC=1000/[5，6，8]=1000/120=8 AB=1000/[5，6]=33 AC=1000/[5，8]=25 BC=1000/[6，8]=41 A=1000/5=200 B=1000/6=166 C=1000/8=125容斥原理容斥原理 由ABC=8 AB=33 AC=25 BC=41 A=200 B=166 C=125 所以由容斥原理，不能被5，6和8整除的整数的个数为 |~A~B~C| =|E|-（A+B+C）+（AB+AC+BC）-ABC =600容斥原理容斥原理例4 求a,b,c,d,e,f六个字母的全排列中不出现ace和df的排列数。 解 设E为全排列集合，A为出现ace的排列的集合，B为出现df的排列的集合， 容斥原理在组合数学中的应用容斥原理在组合数学中的应用错排问题 有禁止模式的排列问题 错排问题错排问题 错排问题是指对n个元素依次给以标号1,2,…,n，求每个元素都不在自己原来位置上的排列数。 设Ai (i=1,2,…,n)为数i在第i位上的全体排列， 因数字i不能动，因而有|Ai|=(n-1)!，i=1,2,…,n 同理错排问题错排问题 定理 用Dn表示{1, 2, …, n}的全部错排个数，则错排问题错排问题 例 在8个字母ABCDEFGH的全排列中，求 （1）仅ACEG四个字母不在原来位置上的排列数 （2）只有4个字母不在原来位置的排列数 （3）ACEG四个字母不在原来上的排列数 解 （1）8个字母中仅ACEG四个字母不在原来位置上，其余4个字母保持不动，相当于4个元素的错排（2）排列数为C(8, 4)9=630错排问题错排问题 （3）8个字母的全排列中，令A1, A2, A3, A4分别表示A, C, E, G在原来位置上的排列 则满足要求的排列为 有禁止模式的排列问题有禁止模式的排列问题 有禁止模式的排列问题主要解决某些元素之间的某种相对位置不能出现的一类排列。 下面我们仅讨论有禁止模式的排列问题中最简单的一种——相邻禁位问题。相邻禁位问题相邻禁位问题 相邻禁位问题：求由集合{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 =？相邻禁位问题相邻禁位问题 设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)! 同理相邻禁位问题相邻禁位问题课后练习课后练习 （1）求1~250之间能被2、3、5和7任何一数整除的整数个数。 （2）在由a、b、c和d这4个字符构成的n位字符串中，求a、b、c至少出现一次的符号串的数目。 （3）数1，2，…，9的全排列中，求偶数在原来位置上，其余都不在原来位置的错排数目。鸽巢原理 鸽巢原理 鸽巢原理鸽巢原理 鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽屉原理。 原理描述：若有n个鸽子巢，n+1只鸽子，则至少有一个鸽子巢里住着两只鸽子。 定理（鸽巢原理） 如果把n+1个物体放入n个盒子，那么至少有一个盒子中有两个或更多的物品。举例举例 例1 367人中至少有2人的生日相同。 例2 在某班中有50名学生，其中年龄最大的20岁，最小的17岁。证明这个班中至少有两名学生是同年同月生的。 例3 在边长为2的等边三角形内任意放置5个点，则其中至少有两个点的距离小于1。 例4 某次会议有n位代表参加，每位代表至少认识其余n-1位中的一位，则这n位代表中，至少有两位认识的人数相等。举例举例 例5 设a1, a2, …,a100是由1和2组成的序列 ，已知从其中任一数开始的连续10个数的和不超过16，即ai+ai+1+…+ai+9≤16 (1≤i≤91)，则存在h和k (k>h)，使得ah+1+ah+2+…+ak=39。 证明： 思考题思考题 从1到2n的正整数中任取n+1个数，则在这n+1个数中，至少有一对数，其中一个是另一个的倍数。课后练习题课后练习题 1、在34的长方形内任意放置7个点，在其中至少有两个点的距离小于等于51/2。