第四专题 容斥原理

《第四专题 容斥原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四专题容斥原理教学时数：4学时教学目标：（1）理解组合数学三大原理之一的容斥原理；（2）了解运用容斥原理处理的常见问题；（3）灵活使用容斥原理解决问题。教学重点与难点：如何将问题转化成可利用容斥原理解决的问题。一、基础知识（一）容斥原理及逐步淘汰原理容斥原理：（1）（简单形式）对任何有限集合，有；（2）（一般形式）对任何个有限集合，有简记：逐步淘汰原理：（1）（简单形式）（2）（一般形式）（二）容斥原理的两种证明方法证法一：（数学归纳法）当时，要证明：这可由等于不相交的两个集合和的并推出，而等于不相交的两个集合和的并。所以，①②由①、②知假设对个集

2、合，要证的等式成立；对个集合时，有第四专题容斥原理（第12页共12页）将和式中具有相同因子数的项合并，即可得到要证明的等式。证法二：（贡献法）如果，则，公式两端均为0，成立；如果，设恰属于个。此时，公式右端中对共计数次，对共计数次，对共计数次，…..，对共计数次，并且在此后的各项中，均未被计数，故公式右端对共计数故等式成立。（三）逐步淘汰原理的另一种描述设有个元素，其中个元素具有特性，个元素具有特性，…，个元素既具有和特性，…，个元素既具有、和特性，…，则完全不具有中任何一种特性的元素个数为。为了便于记忆，逐步淘汰原理可采用符号形式：约定：，，，，则

3、第四专题容斥原理（第12页共12页）（四）几点说明1、容斥原理是19世纪英国数学家西尔维斯特（J.J.Sylvester）首先建立。2、逐步淘汰原理也叫筛公式，它和数论中的筛法有密切联系。3、容斥原理的更为一般的形式：令为一有限集，为从到实数的一个函数。对每一个子集，令其中。若，则。若为常值函数，即对所有的，。便为通常情况下的容斥原理。二、典型例题选讲例1、在1~600中，能被6整除，但不能被8整除的数有多少个？【思路】画个示意图，理清关系。【评注】解决问题的基本方法是画个示意图。思考1：求1~100这100个正整数数中有多少个质数？【思路】（逆向思

4、维，先求1~100中合数的个数）因为，从而1~100中的合数必然是1~10中的质数2，3，5，7之一的倍数。设，，则所以，全体质数的个数为：。【评注】质数个数求解方法常见的是“筛子法”；当不大时，这是求解质数个数的一个方法。思考2：分母是1001的最简真分数，共多少个？（提示：）第四专题容斥原理（第12页共12页）例2、在一个代表团里，懂英语、法语的有10人，懂英语、法语、俄语的有5人，懂英语、法语、汉语的有3人，懂四种语言的有2人，问只懂英语、法语而不懂俄语、汉语的有几人？【思路】关系较复杂，借助逐步淘汰的另一描述进行处理。设分别为懂英语、法语、俄

5、语、汉语的性质，问题即求【评注】当关系较复杂时，利用逐步淘汰的另一描述处理可能要简单些。思考：在面积为6的正方形里有三个面积为3的多边形。证明：在它们中间可以找到两个多边形使之公共部分的面积不小于1。【思路】记这三个多边形的指标为1，2，3，并用表示指标的多边形面积，表示指标的多边形相交部分的面积，表示三者相交部分的面积，其中分别是某个指标1，2，3。由容斥原理，有。因为，而，因此。于是由抽屉原理知，在中必有某个。【评注】问题求解最后用到了面积重叠原理，即抽屉原理。例3、7个人站一排，求甲不站最左边，乙不站中间，丙不站最右边的站法有多少种？【思路】利

6、用容斥原理处理。【评注】对排列计数问题，用容斥原理比直接分类讨论简单。思考1：有3个，4个，2个，用这9个字母组成一个排列，若限定排列中同样的字母不能全部相邻，问这样的排列有多少？【思路】设：9个字母的各种排列组成的集合；：字母全相邻的排列集合；：字母全相邻的排列集合；：字母全相邻的排列集合；则，，，，，，所以【评注】这个问题涉及到可重复排列问题。第四专题容斥原理（第12页共12页）例4、从自然数1、2、3、4、5、……中依次划去3和4的倍数但保留其中是5的倍数，划完后将剩下的数依次构成一个新的数列：，求。【思路】画示意图，先弄清楚1~60中，剩下多

7、少个数。【评注】这个问题涉及到周期段问题。定理：称不大于正整数且与互质的正整数的个数为的欧拉函数，记作。设是的全部质因数，则是1到中，不能被中任何一个整除的整数的个数。易知：。【思路】记，令]则，，……，所以，例5、将与105互质的所有正整数从小到大排成一排组成一个数列}，比如，求这个数列的第1000项。【思路】先求出1~105中有多少项数。因为，故因为，故由于，，所以，。【评注】该问题是一种常见的问题，处理手段为分段处理。思考：已知，求满足条件，且的整数的个数.【思路】因为，所以不能被2，5，199整除，第四专题容斥原理（第12页共12页）即模2不

8、为1；模5不为1，4；模199不为1，198。令，规定的如下子集：，，则，，故，，，，，，，所以，【评注】该