抽屉原理与容斥原理

1、I抽屉原则10个苹果放入9个抽屉中，无论怎么放，一定有一个抽屉里放了2个或更多个苹果.这个简单的事实就是抽屉原则.由德国数学家狄利克雷首先提出来的.因此，又称为狄利克雷原则.将苹果换成信、鸽子或鞋，把抽屉换成信筒、鸽笼或鞋盒，这个原则又叫做信筒原则、鸽笼原则或鞋盒原则.抽屉原则是离散数学中的一个重要原则，把它推广到一般情形就得到下面几种形式：原则一：把m个元素分成n类（mn），不论怎么分，至少有一类中有两个元素.原则二：把m个元素分成n类（mn）（1）当n|m时，至少有一类中含有至少个元素；（2）当n|m时，至少有一类中含有至少+1个元素.其中n m表示n是m的约数，n m表示n不是m的约数，表示不超过的最大整数.原则三：把个元素分成n类，则存在一个k，使得第k类至少有个元素.原则四：把无穷多个元素分成有限类，则至少有一类包含无穷多个元素.以上这些命题用反证法极易得到证明，这里从略.一般来说，适合应用抽屉原则解决的数学问题具有如下特征：新给的元素具有任意性.如10个苹果放入9个抽屉，可以随意地一个抽屉放几个，也可以让抽屉空着. 问题的结论是存在性命题，题目中常含有“至少有”、“一定有”

2、、“不少于”、“存在”、“必然有”等词语，其结论只要存在，不必确定，即不需要知道第几个抽屉放多少个苹果.对一个具体的可以应用抽屉原则解决的数学问题还应搞清三个问题：（1）什么是“苹果”？（2）什么是“抽屉”？（3）苹果、抽屉各多少？用抽屉原则解题的本质是把所要讨论的问题利用抽屉原则缩小范围，使之在一个特定的小范围内考虑问题，从而使问题变得简单明确.用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律.用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律.用抽屉原则解题的关键是利用题目中的条件构造出与题设相关的“抽屉”. 容斥原则当我们试图对某些对象的数目从整体上计数碰到困难时，考虑将整体分解为部分，通过对每个部分的计数来实现对整体的计数是一种明智的选择.将整体分解为部分也就是将有限集X表示成它的一组两两互异的非空真子集A1，A2，An的并集，即叫做集合X的一个覆盖.一个特殊情况是，集族中的任意两个集合都不相交，这时我们称集族为集合X的一个（完全）划分.如为集合X的划分，则对集合X的计数可通过熟知的加法公式 进行

3、，但是，要找到一个划分并且其中所有子集易于计数的有时并非易事. 我们可以考虑通过对任意的集族中的子集的计数来计算|X|，当集族中至少存在两个集合的交非空时，我们称这个覆盖为集合X的不完全划分. 对于集合X的不完全划分，显然有有 因为在计算|Ai|时出现了对某些元素的重复计数，为了计算|X|，就得将式右边重复计算的部分减去，如果减得超出了，还得再加上，也就是说我们要做“多退少补”的工作.完成这项工作的准则就是容斥原理. 是十九世纪英国数学家西尔维斯提出的. 容斥原理有两个公式.1容斥公式定理1 设 证明：当由加法公式有 结论成立.若n=k时结论成立，则由 知，时结论成立.由归纳原理知，对任意自然数n，公式成立.公式称为容斥公式，显然它是公式的推广.如果将看成具有性质的元素的集合，那么就是至少具有n个性质之一的元素的集合. 因此，容斥公式常用来计算至少具有某几个性质之一的元素的数目.数学是一门非常迷人的学科，久远的历史，勃勃的生机使她发展成为一棵枝叶茂盛的参天大树，人们不禁要问：这根大树到底扎根于何处？为了回答这个问题，在19世纪末，德国数学家康托系统地描绘了一个能够为全部数学提供基础的通

4、用数学框架，他创立的这个学科一直是我们数学发展的根植地，这个学科就叫做集合论。它的概念与方法已经有效地渗透到所有的现代数学。可以认为，数学的所有内容都是在“集合”中讨论、生长的。集合是一种基本数学语言、一种基本数学工具。它不仅是高中数学的第一课，而且是整个数学的基础。对集合的理解和掌握不能仅仅停留在高中数学起始课的水平上，而要随着数学学习的进程而不断深化，自觉使用集合语言(术语与符号)来表示各种数学名词，主动使用集合工具来表示各种数量关系。如用集合表示空间的线面及其关系，表示平面轨迹及其关系、表示方程(组)或不等式(组)的解、表示充要条件，描述排列组合，用集合的性质进行组合计数等。有限集元素的个数(容斥原理)请看以下问题：开运动会时，高一某班共有28名同学参加比赛，有15人参加游泳比赛，有8人参加田径比赛，有14人参加球类比赛，同时参加游泳比赛和田径比赛的有3人，同时参加游泳比赛和球类比赛的有3人，没有人同时参加三项比赛，问同时参加田径比赛和球类比赛的有多少人？只参加游泳一项比赛的有多少人？解决这个问题需要我们研究集合元素的个数问题(请读者参阅高中教材数学第一册(上)P23P23阅读材

5、料“集合元素的个数”。)为此我们把有限集合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由公

6、式得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很大

7、时，利用筛法就很困难、很费时了，必须另觅他途。分析2受解法1的启发，如果能找出1n中质数的个数m，则n1m就是不超过n的合数的个数。由初等数论中定理：a是大于1的整数。如果所有不大于a的质数都不能整除a，那么a是质数。因为120121112，12011，所以不超过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/2320，card(S1S3)120/2512，card(S1S4)120/278，card(S2S3)120/358，card(S2S4)120/375，card(S3S4)120/573，card(S1S2S3)120/2354，card(S1S2S4)120/2372，card(S1S3S4)120/2

8、571，card(S2S3S4)120/3571，card(S1S2S3S4)120/23570card(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

《抽屉原理与容斥原理》由会员cn****1分享，可在线阅读，更多相关《抽屉原理与容斥原理》请在金锄头文库上搜索。