论文容斥原理的应用 (1)

《论文容斥原理的应用 (1)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、由《集合中元素的个数》到“莎士比亚巧合”-------容斥原理的应用举例莎士比亚是英国著名戏剧家，其不仅才华横溢，更有一个有趣的巧合流传甚广。他生于1564年4月23日，卒于1616年4月23日，生卒日期相同．下面，我们就从这个巧合说起，谈谈组合数学中最重要原理之一的容斥原理．例1若按每年365天计算，且一个人生卒日期均是随机的，则他生卒日期相同的概率是多少？显然是.试问，两个人都生卒日期相同呢？两个人中至少一个人生卒日期相同的概率呢？如果是N个人呢？为解决这个问题，可参考普通高中数学课程标准(实验)中，必修课程(数学1)13页阅读与思考《集合中元素的个数》一节的内容。对求多个集合的元素总个数

2、，这样解释：(card（A）表示有限集合A中元素的个数），这实质就是两个集合的容斥关系的体现.如果被计数的事物有A、B两类，那么，A类B类元素个数总和=属于A类元素个数+属于B类元素个数—既是A类又是B类的元素个数.如果被计数的事物有A、B、C三类，那么，A类和B类和C类元素个数总和=A类元素个数+B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数.三个集合的容斥关系公式记作：现详细推理如下：Venn图分块标记如右图：1245构成A，2356构成B，4567构成C上式简记为：A∪B∪C={[（A+

3、B-A∩B）+C-B∩C]-C∩A}+A∩B∩C（1）等式左边指的是右图中的1+2+3+4+5+6+7七部分；（2）等式右边（）指的是右图中的1+2+3+4+5+6六部分；（3）等式右边[]相当于A∪B∪C多加了4；（4）等式右边{}相当于A∪B∪C多减了5；（5）而A∩B∩C就是5.则加上A∩B∩C，刚好是A∪B∪C.对于个集合不难推理类似定理，即19世纪英国数学家西尔维斯特（J.J.Sylverster)首先创立的组合计数的一个重要工具.——容斥原理：下我们思考例1所提问题，每一个人生卒日期相同的情况都可以看作一个集合，每两个人生卒日期都分别相同的情况可以看作两个集合的交集，其中对于每个集

4、合对应的元素数，在这里就成了概率，那么这N个集合的概率和就是，这N个集合中每两个集合交集的概率和则为，依次类推，在n 个人中，至少一人生卒日期相同的概率公式为：有了容斥原理，我们还可解决很多类似求集合元素数的问题，不妨看下题：例2学校举办运动会时，高一（1）班共有28名同学参加比赛，有15人参加游泳比赛，有8人参加田径比赛，有14人参加球类比赛，同时参加游泳比赛和田径比赛的有3人，同时参加游泳比赛和球类比赛的有3人，没有人同时参加三项比赛，问同时参加田径和球类比赛的有多少人?只参加游泳一项比赛的有多少人？解：设参加游泳比赛的学生的人数为集合A，参加田径比赛的学生的人数为集合B，参加球类比赛的学

5、生的人数为集合C根据题意，需求根据容斥原理）-=28（参加比赛的人数）=15+8+14=37（参加游泳比赛的人数+参加田径比赛的人数+参加球类比赛的人数）=3（既参加游泳又参加田径的人数）=9（既参加又参游泳加球类的人数）=0（同时参加三项比赛的人数）故28=37-(3-9-)=3.有些题目看似与集合无关，其实也可用容斥原理解答，如下题：例3在1—120的整数中，合数与质数各有多少个？解：即在不超过120的正整数中或是2的倍数，或是3的倍数，或是5的倍数，或是7的倍数共有93个，其中含有2,3,5,7本身，故合数的个数为93-4=89个，而质数的个数等于120个数中除去合数与1的个数，即120

6、-（89+1）=30个.在自主招生考试中，用到容斥原理的问题也屡见不鲜，如2008年复旦大学的自招题：例4四十个学生参加数学奥林匹克竞赛。他们必须解决一个代数学问题、一个几何学问题以及一个三角学问题。具体情况如下表所述：问题代数学问题几何学问题三角学问题代数学问题和几何学问题代数学问题和三角学问题几何学问题和三角学问题解决问题的学生数201818789其中有三位学生一个问题都没有解决。问三个问题都解决的学生数是___________。分析：设解决代数学问题人数为集合A解决几何学问题人数为集合B解决三角学问题人数为集合C根据题意，即，要求A∩B∩C根据容斥原理即A∪B∪C即40-3=37（解决问

7、题的人数）A+B+C即20+18+18=56（解决代数学问题人数+解决几何学问题人数+解决三角学问题人数）A∩B=7（即解决代数学问题有解决几何学问题）B∩C=8（即解决几何学问题又解决三角学问题）C∩A=9（即解决三角学问题又解决代数学问题）所以三个问题都解决的学生人数=5（人）综上，我们不难看出，容斥原理在解决集合问题等数学问题中的重要地位，其更加深入的应用还希望同学们在以后的学习中进一步探讨