- 1、本文档共5页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
从考试成绩到容斥原理
从考试成绩到容斥原理——容斥原理探究及其拓展应用
合肥市第六中学高一(1)班 徐刘辰亮
在生活中,我们经常遇到诸如此类的问题:某校高一某班50名学生,在第一次测验中26人满分,在第二次测验中21人满分,如果两次测验中都没得到满分的学生有17人,那么两次测验中都获得满分的人数是多少?认真想想不难发现两次测验中都获得满分的人数是14.而这个看似简单的问题其实包含着容斥原理的有关知识.
我们知道,在计数时,必须注意无一重复,无一遗漏.为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理.是一个有限集,是的一些两两不相交(无交集)的子集合,使得 ,那么 .是指集合中的元素个数(也就是)叫做集合的一个分划.也就是说, 我们平时的计数,实际上都使用了加法原理.而加法原理的基础是集合的分划.但是有时要做出一个集合的分划,是不很容易的.这就要求人们推广加法原理,容斥原理就应运而生.由此看来,容斥原理是加法原理的一个推广.
一.探究容斥原理及其几个基本形式的证明
基本形式Ⅰ:,,(注意这里可没有限定,所以这两个集合是较为任意的,这里不须使用集合分划的概念),于是有如下一个重要结论:
这就是二元(二集合)形式的容斥原理.
对于它的证明,用Venn图看起来是十分简单的(因为看这个Venn图,这个结论似乎是理所当然的).但我们仍要设法证明之.
首先说明,图中 .
为了证明这个问题,可以采用一种方法——贡献法.这个“贡献”,就是指每个元素在计数过程中的贡献程度有多大.比如说,对一个集合S的子集A计数,要算|A|.对于S中的一个元素,若,我们称元素对|A|的贡献是1.反之,即,那么它的贡献为0.由此,S中所有元素对A的贡献,即是|A|.如此,我们要证的结论,就变成了“等式两边贡献相同”.我们来探究这个证明.
探究如下:记,由于没有限定,所以对于中的任意一个元素,它对等式左端的贡献一定为1而对右端的贡献有三种情况:
①,,此时对|A|贡献为1,对|B|贡献为0,对贡献为0.那么,易知对式子右端贡献为1+0+0=1;
②,,同①的想法,对|A|、|B|和的贡献分别为0,1,0.那么它对式子右端的贡献为0+1+0=1;
③,可得对|A|、|B|和的贡献分别为1,1,1,那么它对式子右端的贡献为1+1-1=1(对于的贡献,不能重复,是要减去的).
综上,不论如何,对式子左边和右边的贡献都相等(都是1).这就说明了等式成立.
至此,命题得证.
基本形式Ⅱ:设A、B分别是集合S的两个子集, 表示集合A与B对S的补集,则
如果直接证明,看起来是不大容易的.对于它的证明,我们为什么不借助已知结论呢? 如果用上前面证过的基本形式Ⅰ,就只需证明了.如果再尝试着用贡献法,就要借助Venn图看看:
对于集合S中的一个任意元素,讨论它与的关系:若 ,那么它对式子左右两端的贡献都是0;若, 则有,那么它对式子左右两端的贡献都是1.因此无论何
种情况,集合S中每个元素对等式两端的贡献都是相同的.这就证明了这个基本形式.
可以看到,我们适时地定义一个“贡献”来计数,就把证明做了简化.
由这两个简单的形式,事实上可以引出一般形式的容斥原理:假如集合S可以分解成m个子集 使 ,则
这个式子也可以用贡献法或数学归纳法来证明.
m=1时,即为基本形式Ⅰ;m=2时,原式化为
.
这个式子当然也可用贡献法.我们在这里证明一下m=2时的情况即(i)式:
设有任一元素则对式子左端的贡献恒为1.对于式子右端,由于所以分类讨论:
假如x属于三个子集中的一个,而不属于其余两个,如 ,则它对式子右端的各项 的贡献依次是1,0,0.所以对式子右端的贡献为1-0+0=1;
假如x属于三个子集中的两个,而不属于其余一个,如,则易得它对式子右边的贡献是2,1,0.所以x对式子右端贡献为2-1+0=1;
如果x是三个集合共有的元素,则得它对式子右边的贡献是3,3,1.所以x对式子右端贡献为3-3+1=1;
所以x对式子右端贡献恒为1.证毕.
这就是你我所熟知的三元形式的容斥原理.
二.容斥原理的拓展应用
容斥原理在计数等问题中有着很广泛的应用.下面探究几个例子.
(一)在集合与数字计数方面的应用
先看一个简单的、与生活息息相关的例子:
例1. :某校高一某班50名学生,在第一次测验中26人满分,在第二次测验中21人满分,如果两次测验中都没得到满分的学生有17人,那么两次测验中都获得满分的人数是多少?
解 这其实是开头我们提到的题目.
如果采用算术解法,可以这样思考:依题意,被计数的事物有两类:第一次测验得满分和第二次测验得满
文档评论(0)