1、容斥原理和鸽巢原理,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定理 :,容斥原理和鸽巢原理,DeMogan定理的推广：,设：,容斥原理和鸽巢原理,容斥原理：,最简单的计数问题是求有限集合A和B的并的元素数目。显然有,容斥原理和鸽巢原理,容斥原理和鸽巢原理,例：一个学校只有三门课程：
2、数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？,解：令，M为修数学的学生集合； P 为修物理的学生集合； C 为修化学的学生集合；所以有,容斥原理和鸽巢原理,即学校学生数为336人。,容斥原理和鸽巢原理,一般地，我们可得定理：,定理：设A1,A2, ,Am均为有限集，m2,则,容斥原理和鸽巢原理,，其中N是集合U的元素个数，即不属于A的元素个数等于集合的全体减去属于A的元素的个数。一般有：,容斥原理指的就是这两个式子。,容斥原理和鸽巢原理,例1
3、求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。,解：设A为ace作为一个元素出现的排列集， B为 df作为一个元素出现的排列集， 则AB 为同时出现ace、df的排列数。,根据容斥原理，不出现ace和df的排列数为：,=6!- (5!+4!)+3!=582,容斥原理和鸽巢原理,例2 求从1到500的整数中能被3或5除尽的数的个数。,解： 令 A为从1到500的整数中被3除尽的数的集合， B为被5除尽的数的集合,则,容斥原理和鸽巢原理,例3 求由a,b,c,d四个字母构成的n位符号串中，a,b,c至少出现一次的符号串数目。,解：令A、B、C分别为n位符号串中不出现
4、a，b，c符号的集合。 由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是：3n。,容斥原理和鸽巢原理,a，b，c至少出现一次的n位符号串集合即为,容斥原理和鸽巢原理,2 错排问题,n个元素依次给以标号1，2，n。n个元素的全排列中，求每个元素都不在自己原来位置上的排列数。,设 Ai 为数 i 在第 i 位上的全体排列，i =1，2，n。因数字 i 不能动，因而有：,容斥原理和鸽巢原理,所以每个元素都不在原来位置的排列数为,容斥原理和鸽巢原理,例1 数1，2，9的全排列中，求偶数在原来位置上，其余都不在原来位置的错排数目。,解：实际上是1，3，5，
5、7，9五个数的错排问题，总数为：,容斥原理和鸽巢原理,例2. 在8个字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四个字母不在原来上的错排数目。,解： 8个字母的全排列中，令A1,A2,A3,A4分别表A,C,E,G在原来位置上的排列，则错排数为：,容斥原理和鸽巢原理,3 棋盘多项式和有限制排列,例4个x ，3个y，2个z的全排列中，求不出现xxxx，yyy，zz的排列。 解设出现xxxx的排列的集合记为A1， |A1|= 6!/(1! 3! 2!) =60; 设出现yyy的排列的集合记为A2， | A2|= 7!/(4! 1! 2!) =105； 设出现zz的排列的集合记为
6、A3， | A3|= 8!/(4! 3! 1!) =280；,1. 有限制排列,容斥原理和鸽巢原理,同时有： |A1A2|=4!/ (1! 2! 1!) =12； |A1A3|= 5!/(1! 3! 1!) =20； |A2A3|= 6!/(4! 1! 1!) =30； |A1A2A3|=3!=6； 全排列的个数为: 9!/(4! 3! 2!) =1260；所以： |A1A2A3|=1260(60+105+280) +(12+20+30)6 =871,容斥原理和鸽巢原理,2棋子多项式,n个不同元素的一个全排列可看做n个相同的棋子在nn的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子,
7、x,x,x,x,x,如图所示的布局对应于排列41352。,容斥原理和鸽巢原理,可以把棋盘的形状推广到任意形状：,布子规定称为无对攻规则，棋子相当于象棋中的车。 令r k（C）表示k个棋子布到棋盘C上的方案数。如：,容斥原理和鸽巢原理,为了形象化起见，（ ）中的图象便是棋盘的形状。,容斥原理和鸽巢原理,规定 r0(C)=1，包括C=f 时。设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。在上面定义下，显然有rk(C)=rk1(Ci)rk(Ce)，,容斥原理和鸽巢原理,即对任一指定的格子，要么布子，所得的方案数为 rk1(Ci)；要么不布子，方案数为 rk(
8、Ce)。,设C有n个格子，则 r1(C)nr1(C)r0(Ci) + r1(Ce)，r1(Ce)n1 r0(Ci)1故规定 r0(C)1是合理的,容斥原理和鸽巢原理,对任一指定的格子，要么布子，所得的方案数为 rk1(Ci)；要么不布子，方案数为 rk(Ce)。,=xR(Ci) + R(C e) (3),容斥原理和鸽巢原理,例如：,容斥原理和鸽巢原理,如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2的格子。则有, R(C) = R(C1) R(C2) (4),容斥原理和鸽巢原理,利用前面的式子，可以把一个比较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式
9、。,容斥原理和鸽巢原理,有禁区的排列,例 设对于排列P=P1 P2 P3 P4, 规定P1,P、， P2、， P42。,这样的排列对应于有禁区的布子。如右图有影线的格子表示禁区。,容斥原理和鸽巢原理,定理设 ri 为 i个棋子布入禁区的方案数，i =1,2,3,n。有禁区的布子方案数（即禁区内不布子的方案数）为,例,四位工人，A, B, C, D四项任务。条件如下：不干B；不干B、C；不干 C、D；不干D。问有多少种可行方案？,容斥原理和鸽巢原理,解由题意，可得如下棋盘：,其中有影线的格子表示禁区。,方案数=4!6(41)!+10(42)!4(43)! +0(44)!=4,容斥原理和鸽巢原理,
10、4鸽巢原理之一,鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽屉原理。即,“若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有两个鸽子。”,例367人中至少有人的生日相同。例10双手套中任取11只，其中至少有两只是完整配对的。例参加一会议的人中至少有人认识的别的参加者的人数相等。,容斥原理和鸽巢原理,例从1到2n的正整数中任取n+1个，则这n+1个数中，至少有一对数，其中一个是另一个的倍数。,证设n+1个数是 a1 , a2 , , an+1。每个数去掉一切2的因子，直至剩下一个奇数为止。组成序列 r1 , r2, , , rn+1。这n+1个数仍在1 , 2n中，且都是奇数。而1 ,
11、 2n中只有n个奇数 . 故必有 ri = rj = r , 则 ai = 2i r, aj = 2j r .若ij ，则 ai 是 aj 的倍数。,容斥原理和鸽巢原理,例设 a1 , a2 , , am是正整数序列，则至少存在k和 l , 1k l m，使得和ak + ak+1 + + al 是m的倍数。,证设Sh = ai , Sh rh mod m 0rhm-1h = 1 , 2 , , m . 若存在 l , Sl0 mod m 则命题成立否则，1rhm-1但h = 1 , 2 , , m由鸽巢原理，故存在 rk = rh , 即Sk Sh，不妨设 h k则 ShSk = ak+1 +
12、 ak+2 + + ah 0 mod m,i=1,h,容斥原理和鸽巢原理,例设 a1 , a2 , a3为任意个整数，b1b2b3为a1 , a2 , a3的任一排列，则 a1b1 , a2b2 , a3b3中至少有一个是偶数,证由鸽巢原理， a1 , a2 , a3必有两个同奇偶设这个数被除的余数为 xxy，于是b1 , b2 , b3中被除的余数有个x，一个y这样a1b1 , a2b2 , a3b3被除的余数必有一个为,容斥原理和鸽巢原理,5鸽巢原理之二,鸽巢原理二m1 , m2 , , mn都是正整数，并有m1 + m2 + +mnn + 1个鸽子住进n个鸽巢，则至少对某个 i 有第 i
13、 个巢中至少有mi个鸽子，i = 1 , 2 , , n,上一小节的鸽巢原理一是这一原理的特殊情况，即m1 = m2 = = mn= 2， m1 + m2 + +mnn + 1 = n + 1 如若不然，则对任一 i， 都有第 i 个巢中的鸽子数mi1则鸽子总数 m1 + m2 + +mnn ，与假设相矛盾,容斥原理和鸽巢原理,推论n(m1) + 1只鸽子进n个巢，至少有一个巢内至少有m只鸽子,例证明每个长为n2+1的实数序列中，一定存在长为n+1的递增或递减子序列（不一定是严格递、减）。,推论若n个整数的平均数大于r-1，则至少有一个整数大于等于r。,证明：设,为任取的实数序列。若此序列中不
14、存在长为n+1的递增子序列,则一定存在长为n+1的递减序列.,容斥原理和鸽巢原理,令mi为以ai为首项的最长递增子序列的长度，i=1,2,n2+1。,因为n2+1=n(n+1)-1+1,由鸽笼原理的推论可知。,若有某个min+1，则结论成立。若不然，必有mi n+1，从而有mi n。,容斥原理和鸽巢原理,应用实例: 锁具装箱问题某厂生产一种弹子锁具, 每个锁具的钥匙有 5个槽, 每个槽的高度从1, 2, 3, 4, 5, 66个数(单位略)中任取一数. 由于工艺及其它原因, 制造锁具时对 5 个槽的高度还有两个限制：至少有3个不同的数；相邻两槽的高度之差不能为 5. 满足以上条件制造出来的所有
15、互不相同的锁具称为一批.,容斥原理和鸽巢原理,从顾客的利益出发，自然希望在每批锁具中“一把钥匙开一把锁”. 但是在当前工艺条件下，对于同一批中两个锁是否能够互开，有以下试验结果：若二者相对应的5个槽的高度中有 4 个相同, 另一个槽的高度差为1, 则可能互开; 在其它情形下, 不可能互开.原来，销售部门在一批锁具中随意的取60个装一箱出售. 团体顾客往往购买几箱到几十箱, 他们抱怨购得的锁具会出现互开的情形. 现聘你为顾问, 回答并解决以下的问题：,容斥原理和鸽巢原理,1） 每一批锁具有多少个，装多少箱.2） 为销售部门提出一种方案，包括如何装箱（仍是 60 个锁具一箱），如何给箱子以标志，出
16、售时如何利用这些标志，使团体顾客不再或减少抱怨. 3） 采取你提出的方案，团体顾客的购买量不超过多少箱，就可以保证一定不会出现互开的情形. 4） 按照原来的装箱办法，如何定量地衡量团体顾客抱怨互开的程度(试对购买一、二箱者给出具体结果).,容斥原理和鸽巢原理,我们主要根据生产一批锁具的三个条件，用排列组合的知识对一批锁具的总数目进行求解. 设h1, h2, h3, h4, h5分别表示相应的槽高取值, 其主要过程如下：(1) 钥匙槽高度的可能排列有65=7776种.(2) 因为至少有3个不同的数, 相邻两槽的高度之差不能为 5的约束，实际制锁时还要除去一部分钥匙槽高度的排列方式，我们称这些排列
17、方式形成的集合为除去集D.(3) 相邻两槽的高度之差不能为5等价为钥匙槽高度排列方式中不能出现1和6相邻的情况.,容斥原理和鸽巢原理,(4) 对除去集D可进行如下划分： 令D1=h1= h2= h3= h4= h5的排列 D2=hi (i = 1, 2, 3, 4, 5)中只有两个不同数的排列； D3= hi (i = 1, 2, 3, 4, 5)中有三个不同数且1和6相邻的排列 D4= hi (i = 1, 2, 3, 4, 5)中有四个不同数且1和6相邻的排列 D5= hi (i = 1, 2, 3, 4, 5)各不相同且 1和 6相邻的排列；,显然，Di (i = 1, 2, 3, 4,
18、 5)是D的一个完全划分，即D1D2D3D4D5= D, 且DiDj =f (i, j=1, 2, 3, 4, 5且ij).我们分别求出了Di (i = 1, 2, 3, 4, 5)中的元素个数如下：| D1|=6；| D2|=450；| D3|=456；| D4| =792；| D5|=192. 其中, |D|表示集合D中元素的个数.综上，一批锁具的总数为 7776一（6456792192）= 5880件.可装的箱数为588060=98箱.,容斥原理和鸽巢原理,例设A= a1a2a20是10个0和10个1 组成的进制数B=b1b2b20是任意的进制数C = b1b2b20 b1b2b20 = C1C2C40，则存在某个i ，1 i 20，使得CiCi+1Ci+19与a1a2a20至少有10位对应相等,A,B,C,第 i 格,第 i +19格,1 2 19 20 1 2 19 20,1 2 19 20 1 19 20,容斥原理和鸽巢原理,证在C = C1C2C40中，当 i 遍历1 , 2 , ,20时，每一个bj历遍 a1 , a2 , , a20因A中有10个0和10个1，每一个bj都有10位次对应相等从而当 i历遍1 , , 20时，共有10 20=200位次对应相等故对每个 i平均有200 /20 = 10位相等，因而对某个 i 至少有10位对应相等,
