抽屉原理与容斥原理

I抽屉原则10个苹果放入9个抽屉中，无论怎么放，一定有一个抽屉里放了2个或更多个苹果.这个简单的事实就是抽屉原则.由德国数学家狄利克雷首先提出来的.因此，又称为狄利克雷原则.将苹果换成信、鸽子或鞋，把抽屉换成信筒、鸽笼或鞋盒，这个原则又叫做信筒原则、鸽笼原则或鞋盒原则.抽屉原则是离散数学中的一个重要原则，把它推广到一般情形就得到下面几种形式：原则一：把m个元素分成n类（m>n），不论怎么分，至少有一类中有两个元素.原则二：把m个元素分成n类（m>n）（1）当n|m时，至少有一类中含有至少个元素；（2）当n|m时，至少有一类中含有至少+1个元素.其中n m表示n是m的约数，n m表示n不是m的约数，表示不超过的最大整数.原则三：把个元素分成n类，则存在一个k，使得第k类至少有个元素.原则四：把无穷多个元素分成有限类，则至少有一类包含无穷多个元素.以上这些命题用反证法极易得到证明，这里从略.一般来说，适合应用抽屉原则解决的数学问题具有如下特征：新给的元素具有任意性.如10个苹果放入9个抽屉，可以随意地一个抽屉放几个，也可以让抽屉空着. 问题的结论是存在性命题，题目中常含有“至少有”、“一定有”、“不少于”、“存在”、“必然有”等词语，其结论只要存在，不必确定，即不需要知道第几个抽屉放多少个苹果.对一个具体的可以应用抽屉原则解决的数学问题还应搞清三个问题：（1）什么是“苹果”？（2）什么是“抽屉”？（3）苹果、抽屉各多少？用抽屉原则解题的本质是把所要讨论的问题利用抽屉原则缩小范围，使之在一个特定的小范围内考虑问题，从而使问题变得简单明确.用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律.用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律.用抽屉原则解题的关键是利用题目中的条件构造出与题设相关的“抽屉”. 容斥原则当我们试图对某些对象的数目从整体上计数碰到困难时，考虑将整体分解为部分，通过对每个部分的计数来实现对整体的计数是一种明智的选择.将整体分解为部分也就是将有限集X表示成它的一组两两互异的非空真子集A1，A2，An的并集，即叫做集合X的一个覆盖.一个特殊情况是，集族中的任意两个集合都不相交，这时我们称集族为集合X的一个（完全）划分.如为集合X的划分，则对集合X的计数可通过熟知的加法公式 进行，但是，要找到一个划分并且其中所有子集易于计数的有时并非易事. 我们可以考虑通过对任意的集族中的子集的计数来计算|X|，当集族中至少存在两个集合的交非空时，我们称这个覆盖为集合X的不完全划分. 对于集合X的不完全划分，显然有有 因为在计算|Ai|时出现了对某些元素的重复计数，为了计算|X|，就得将式右边重复计算的部分减去，如果减得超出了，还得再加上，也就是说我们要做“多退少补”的工作.完成这项工作的准则就是容斥原理. 是十九世纪英国数学家西尔维斯提出的. 容斥原理有两个公式.1容斥公式定理1 设 证明：当由加法公式有 结论成立.若n=k时结论成立，则由 知，时结论成立.由归纳原理知，对任意自然数n，公式成立.公式称为容斥公式，显然它是公式的推广.如果将看成具有性质的元素的集合，那么就是至少具有n个性质之一的元素的集合. 因此，容斥公式常用来计算至少具有某几个性质之一的元素的数目.数学是一门非常迷人的学科，久远的历史，勃勃的生机使她发展成为一棵枝叶茂盛的参天大树，人们不禁要问：这根大树到底扎根于何处？为了回答这个问题，在19世纪末，德国数学家康托系统地描绘了一个能够为全部数学提供基础的通用数学框架，他创立的这个学科一直是我们数学发展的根植地，这个学科就叫做集合论。它的概念与方法已经有效地渗透到所有的现代数学。可以认为，数学的所有内容都是在“集合”中讨论、生长的。集合是一种基本数学语言、一种基本数学工具。它不仅是高中数学的第一课，而且是整个数学的基础。对集合的理解和掌握不能仅仅停留在高中数学起始课的水平上，而要随着数学学习的进程而不断深化，自觉使用集合语言(术语与符号)来表示各种数学名词，主动使用集合工具来表示各种数量关系。如用集合表示空间的线面及其关系，表示平面轨迹及其关系、表示方程(组)或不等式(组)的解、表示充要条件，描述排列组合，用集合的性质进行组合计数等。有限集元素的个数(容斥原理)请看以下问题：开运动会时，高一某班共有28名同学参加比赛，有15人参加游泳比赛，有8人参加田径比赛，有14人参加球类比赛，同时参加游泳比赛和田径比赛的有3人，同时参加游泳比赛和球类比赛的有3人，没有人同时参加三项比赛，问同时参加田径比赛和球类比赛的有多少人？只参加游泳一项比赛的有多少人？解决这个问题需要我们研究集合元素的个数问题(请读者参阅高中教材数学第一册(上)P23P23阅读材料“集合元素的个数”。)为此我们把有限集合A的元素个数记作card(A)可以证明：(1) card(AB)card(A)card(B)card(AB)；(2) card(ABC)=card(A)+card(B)+card(C)-card(AB)-card(AC)-card(BC)+card(ABC)如下图所示：由图131，有card(AB)=+=(+)+(+)-card(A)+card(B)-card(AB)card(Cu(AB)=card(U)-card(AB)=card(U)-card(A)-card(B)+card(AB)又由图132，有card(ABC)=+(+)+(+)+(+)-(+)-(+)-(+)+card(A)+card(B)+card(C)-card(AB)-card(AC)-card(BC)+card(ABC)现在我们可以来回答刚才的问题了：设A参加游泳比赛的同学，B参加田径比赛的同学，C参加球类比赛的同学则card(A)=15，card(B)=8，card(C)=14，card(ABC)=28且card(AB)=3，card(AC)=3，card(ABC)=0由公式得281581433card(BC)+0即card(BC)=3所以同时参加田径和球类比赛的共有3人，而只参加游泳比赛的人有15339(人) 例6计算不超过120的合数的个数分析1：用“筛法”找出不超过120的质数(素数)，计算它们的个数，从120中去掉质数，再去掉“1”，剩下的即是合数。解法1：120以内： 既不是素数又不是合数的数有一个，即“1”； 素数有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97、101、103、107、109、113、共30个。所以不超过120的合数有12013089(个)(附：筛法：从小到大按顺序写出1120的所有自然数：先划掉1，保留2，然后划掉2的所有倍数4,6，120等；保留3，再划掉所有3的倍数6,9117、120等；保留5，再划掉5的所有倍数10,15，120；保留7，再划掉7的所有倍数，这样，上面数表中剩下的数就是120以内的所有素数，这种方法是最古老的寻找素数的方法，叫做“埃斯托拉筛法”)说明：当n不很大时，计算1n中的合数的个数困难不大；但当n很大时，利用筛法就很困难、很费时了，必须另觅他途。分析2受解法1的启发，如果能找出1n中质数的个数m，则n1m就是不超过n的合数的个数。由初等数论中定理：a是大于1的整数。如果所有不大于a的质数都不能整除a，那么a是质数。因为120<121112，120<11，所以不超过120的合数必是2或3或5或7的倍数，所以只要分别计算出不超过120的2、3、5、7的倍数，再利用“容斥原理”即可。解法2：设S1a13120,2a；S2b1b120,3b；S3c13120,5c；S4=d1d120,7d，则有：card(S1)120/2=60，card(S2)120/340，card(S3)120/524，card(S4)120/717；(n表示n的整数部分，例如2,42，)card(S1S2)120/2×320，card(S1S3)120/2×512，card(S1S4)120/2×78，card(S2S3)120/3×58，card(S2S4)120/3×75，card(S3S4)120/5×73，card(S1S2S3)120/2×3×54，card(S1S2S4)120/2×3×72，card(S1S3S4)120/2×5×71，card(S2S3S4)120/3×5×71，card(S1S2S3S4)120/2×3×5×70card(S1S2S3S4)card(S1)card(S2)card(S3)card(S4)card(S1S2)card(S1S3)card(S1S4)card(S2S3)card(S2S4)card(S3S4)card(S1S2S3)card(S1S2S4)card(S1S3S4)card(S2S3S4)card(S1S2S3S4)(60402417)-(20+12+8+8+5+3)+(4+2+1+1)-0141-568932，3，5，7是质数93489即不超过120的合数共有89个。四、 有限集合子集的个数问题：(1) 集合a一共有几个子集？(2) 集合a，b一共有几个子集？(3) 集合a,b,c一共有几个子集？(4) 集合a,b,c,d一共有几个子集？(5) 猜想集合a1,a2，an一共有几个子集？(6) 利用上述猜想确定符合下列条件的集合M的个数：1,2M1,2，3,4，5,6，7,8，9,10。以上诸问题都牵涉到有限集合子集的个数问题。有限集合a的子集有：，a；共两个有限集合a,b的子集有：，a，b，a,b；共422个；有限集合a,b,c的子集有：；a，b，c；a,b，a,c，b,c；a,b,c；823个；有限集合a,b,c,d的子集有：；a，b，c，d；a,b，a,c， a,d，b,c，b,d，c,d；a,b,c，a,b,d，a,c,d，b,c,d