容斥问题知识点及实例解析

2024-04-21

容斥问题知识点及实例解析（共3篇）

篇1：容斥问题知识点及实例解析

一、知识点 ?

1、集合与元素：把一类事物的全体放在一起就形成一个集合。每个集合总是由一些成员组成的，集合的这些成员，叫做这个集合的元素。

如：集合A={0，1，2，3，„„，9}，其中0，1，2，„9为A的元素。

2、并集：由所有属于集合A或集合B的元素所组成的集合，叫做A，B的并集，记作A∪B，记号“∪”读作“并”。A∪B读作“A并B”，用图表示为图中阴影部分表示集合A，B的并集A∪B。

? 例：已知6的约数集合为A={1，2，3，6}，10的约数集合为B={1，2，5，10}，则A∪B={1，2，3，5，6，10}

3、交集：A、B两个集合公共的元素，也就是那些既属于A，又属于B的元素，它们组成的集合叫做A和B的交集，记作“A∩B”，读作“A交B”，如图阴影表示：

? 例：已知6的约数集合A={1，2，3，6}，10的约数集合B={1，2，5，10}，则A∩B={1，2}。

4、容斥原理（包含与排除原理）：

（用|A|表示集合A中元素的个数，如A={1，2，3}，则|A|=3）

原理一：给定两个集合A和B，要计算A∪B中元素的个数，可以分成两步进行：

第一步：先求出?A?+?B?（或者说把A，B的一切元素都“包含”进来，加在一起）；

第二步：减去?A∩B?（即“排除”加了两次的元素）

总结为公式：|A∪B|=?A?+?B?-?A∩B? 原理二：给定三个集合A，B，C。要计算A∪B∪C中元素的个数，可以分三步进行：

第一步：先求?A?+?B?+?C?；

第二步：减去?A∩B?，?B∩C?，?C∩A?；

第三步：再加上?A∩B∩C?。

即有以下公式：

?A∪B∪C?=?A?+?B?+?C?-?A∩B?-?B∩C?-|C∩A|+|A∩B∩C?

二、例题分析：

例1 求不超过20的正整数中是2的倍数或3的倍数的数共有多少个。

分析：设A={20以内2的倍数}，B={20以内3的倍数}，显然，要求计算2或3的倍数个数，即求?A∪B?。

解1：A={2，4，6，„20}，共有10个元素，即|A|=10 B={3，6，9，„18}，共有6个元素，即|B|=6 A∩B={既是2的倍数又是3的倍数}={6，12，18}，共有3个元素，即|A∩B|=3 所以?A∪B?=?A?+?B?-?A∩B?=10+6-3=13，即A∪B中共有13个元素。

解2：本题可直观地用图示法解答

? 如图,其中,圆A中放的是不超过20的正整数中2的倍数的全体;圆B中放的是不超过20的正整数中3的倍数的全体,其中阴影部分的数6,12,18是既是2的倍数又是3的倍数的数(即A∩B中的数)只要数一数集合A∪B中的数的个数即可。例2 某班统计考试成绩，数学得90分上的有25人；语文得90分以上的有21人；两科中至少有一科在90分以上的有38人。问两科都在90分以上的有多少人？

解：设A={数学成绩90分以上的学生} B={语文成绩90分以上的学生} 那么，集合A∪B表示两科中至少有一科在90分以上的学生，由题意知，?A?=25，?B?=21，?A∪B?=38 现要求两科均在90分以上的学生人数，即求?A∩B?，由容斥原理得 ?A∩B?=?A?+?B?-?A∪B?=25+21-38=8 点评：解决本题首先要根据题意，设出集合A，B，并且会表示A∪B，A∩B，再利用容斥原理求解。

例3 某班同学中有39人打篮球，37人跑步，25人既打篮球又跑步，问全班参加篮球、跑步这两项体育活动的总人数是多少？

解：设A={打篮球的同学}；B={跑步的同学} 则 A∩B={既打篮球又跑步的同学} A∪B={参加打篮球或跑步的同学} 应用容斥原理?A∪B?=?A?+?B?-?A∩B?=39+37-25=51（人）

例4 求在不超过100的自然数中，不是5的倍数，也不是7的倍数有多少个？

分析：这个问题与前几个例题看似不相同，不能直接运用容斥原理，要计算的是“既不是5的倍数，也不是7的倍数的数的个数。”但是，只要同学们仔细分析题意，这只需先算出“100以内的5的倍数或7的倍数的数的个数。”再从100中减去就行了。

解：设A={100以内的5的倍数} B={100以内的7的倍数} A∩B={100以内的35的倍数} A∪B={100以内的5的倍数或7的倍数} 则有?A?=20，?B?=14，?A∩B?=2 由容斥原理一有：?A∪B?=?A?+?B?-?A∩B?=20+14-2=32 因此，不是5的倍数，也不是7的倍数的数的个数是：100-32=68（个）

点评：从以上的解答可体会出一种重要的解题思想：有些问题表面上看好象很不一样，但经过细心的推敲就会发现它们之间有着紧密的联系，应当善于将一个问题转化为另一个问题。

例5 某年级的课外学科小组分为数学、语文、外语三个小组，参加数学小组的有23人，参加语文小组的有27人，参加外语小组的有18人；同时参加数学、语文两个小组的有4人，同时参加数学、外语小组的有7人，同时参加语文、外语小组的有5人；三个小组都参加的有2人。问：这个年级参加课外学科小组共有多少人？

解1：设A={数学小组的同学}，B={语文小组的同学}，C={外语小组的同学}，A∩B={数学、语文小组的同学}，A∩C={参加数学、外语小组的同学}，B∩C={参加语文、外语小组的同学}，A∩B∩C={三个小组都参加的同学} 由题意知：?A?=23，?B?=27，?C?=18 ?A∩B?=4，?A∩C?=7，?B∩C?=5，?A∩B∩C?=2 根据容斥原理二得：

?A∪B∪C?=?A?+?B?+?C?-?A∩B?-?A∩C|-?B∩C|+|A∩B∩C? =23+27+18-（4+5+7）+2 =54（人）

解2：利用图示法逐个填写各区域所表示的集合的元素的个数，然后求出最后结果。? ? ? 设A、B、C分别表示参加数学、语文、外语小组的同学的集合，其图分割成七个互不相交的区域，区域Ⅶ（即A∩B∩C）表示三个小组都参加的同学的集合，由题意，应填2。区域Ⅳ表示仅参加数学与语文小组的同学的集合，其人数为4-2=2（人）。区域Ⅵ表示仅参加数学与外语小组的同学的集合，其人数为7-2=5（人）。区域Ⅴ表示仅参加语文、外语小组的同学的集合，其人数为5-2=3（人）。区域Ⅰ表示只参加数学小组的同学的集合，其人数为23-2-2-5=14（人）。同理可把区域Ⅱ、Ⅲ所表示的集合的人数逐个算出，分别填入相应的区域内，则参加课外小组的人数为：

14+20+8+2+5+3+2=54（人）

点评：解法2简单直观，不易出错。由于各个区域所表示的集合的元素个数都计算出来了，因此提供了较多的信息，易于回答各种方式的提问。

例6 学校教导处对100名同学进行调查，结果有58人喜欢看球赛，有38人喜欢看戏剧，有52人喜欢看电影。另外还知道，既喜欢看球赛又喜欢看戏剧（但不喜欢看电影）的有6人，既喜欢看电影又喜欢看戏剧（但不喜欢看球赛）的有4人，三种都喜欢的有12人。问有多少同学只喜欢看电影？有多少同学既喜欢看球赛又喜欢看电影（但不喜欢看戏剧）？（假定每人至少喜欢一项）

解法1：画三个圆圈使它们两两相交，彼此分成7部分（如图）这三个圆圈分别表示三种不同爱好的同学的集合，由于三种都喜欢的有12人，把12填在三个圆圈的公共部分内（图中阴影部分），其它6部分填上题目中所给出的不同爱好的同学的人数（注意，有的部分的人数要经过简单的计算）其中设既喜欢看电影又喜欢看球赛的人数为χ，这样，全班同学人数就是这7部分人数的和，即

16+4+6+（40-χ）+（36-χ）+12=100 解得 χ=14 只喜欢看电影的人数为 36-14=22 ? 解法2：设A={喜欢看球赛的人}，B={喜欢看戏剧的人}，C={喜欢看电影的人}，依题目的条件有|A∪B∪C|=100，|A∩B|=6+12=18（这里加12是因为三种都喜欢的人当然喜欢其中的两种），|B∩C|=4+12=16，|A∩B∩C|=12，再设|A∩C|=12+χ由容斥原理二：|A∪B∪C |=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C| 得：100=58+38+52-（18+16+х+12）+12 解得：х=14 ∴36-14=22 所以既喜欢看电影又喜欢看球赛的人数为14，只喜欢看电影的人数为22。

点评：解法1没有用容斥原理公式，而是先分别计算出（未知部分设为х）各个部分（本题是7部分）的数目，然后把它们加起来等于总数，这种计算方法也叫“分块计数法”，它是利用图示的方法来解决有关问题，希望同学们能逐步掌握此类方法，它比直接用容斥原理公式更直观，更具体。

例

7、某车间有工人100人，其中有5个人只能干电工工作，有77人能干车工工作，86人能干焊工工作，既能干车工工作又能干焊工工作的有多少人？

解：工人总数100，只能干电工工作的人数是5人，除去只能干电工工作的人，这个车间还有95人。利用容斥原理，先多加既能干车工工作又能干焊工工作的这一部分，其总数为163，然后找出这一公共部分，即163-95=68 例

8、某次语文竞赛共有五道题（满分不是100分），丁一只做对了（1）、（2）、（3）三题得了16分；于山只做对了（2）、（3）、（4）三题，得了25分；王水只做对了（3）、（4）、（5）三题，得了28分，张灿只做对了（1）、（2）、（5）三题，得了21分，李明五个题都对了他得了多少分？

解：由题意得：前五名同学合在一起，将五个试题每个题目做对了三遍，他们的总分恰好是试题总分的三倍。五人得分总和是16+25+28+21=90。因此，五道题满分总和是90÷3=30。所以李明得30分。

例9，某大学有外语教师120名，其中教英语的有50名，教日语的有45名，教法语的有40名，有15名既教英语又教日语，有10名既教英语又教法语，有8名既教日语又教法语，有4名教英语、日语和法语三门课，则不教三门课的外语教师有多少名？

解：本题只有求出至少教英、日、法三门课中一种的教师人数，才能求出不教这三门课的外语教师的人数。至少教英、日、法三门课中一种教师人数可根据容斥原理求出。根据容斥原理,至少教英、日、法三门课中一种的教师人数为50+45+40-15-10-8+4=106（人）不教这三门课的外语教师的人数为120-106=14（人）。

篇2：容斥原理在更列问题中的应用实例

在计数时, 必须注意无一重复, 无一遗漏.为了使重叠部分不被重复计算, 人们在计数时, 必须注意研究出一种新的计算方法, 这种方法的基本思想是:先不考虑重叠的情况, 把包含于某内容中的所有对象的数目先计算出来, 然后再把计算时重复计算的数目排斥出去, 使得计算的结果既无遗漏又无重复, 这种计数的方法称之为容斥原理

二、容斥原理的性质

假定|A|表示集合A的元素个数, 根据加法原则, 若A∪B=Ø, 则|A∪B|=|A|+|B|.若A∩B=Ø时, 这时将|A∪B|多计算一次, 可以直观有|A∪B|=|A|+|B|-|A∩B|.对于n个有限集合A1, A2, A3, …, An, 同样有定理:

(-1) n-2|A1∩An|∪ (A2∩An) ∪…∪ (An-1∩An) |+

undefined|Ai∩Aj∩Ak|+…+ (-1) n-1|A1∩A2∩…∩An|.

三、更列问题的概念

什么叫作更列问题?我们先来看一个题目, 现有五件球衣分属五个运动员, 现问五个运动员都不穿自己的球衣, 而穿其他球员的球衣, 这样的穿法有几种?这就是5个元素的更列问题.

就一般而言, 有几个不同的元素, 它们一一对应于几个位置, 如果这n个元素都不排在自身对应的位置上, 这种排列的方法称为几个元素的一个更列.现要计算这种更列的个数.大数学家欧拉曾用容斥原理求出了n个元素的更列个数为:undefined

四、容斥原理与更列问题的关系

这是运用组合数学的方法解决问题的一个运用.下面我们就证明一下这个公式.现在, 我们来考虑整数1, 2, …, n的排列.如果1不出现在第1个位置, 2不出现在第2个位置, …, n不出现在第n个位置, 这时, 这些整数的一个排列说成是它们的一个更列.也就是说, 没有一个整数出现在它的自然位置上.用Mn记1, 2, …, n这n个数的更列的个数.如何来求这个Mn, 这既是一个排列问题, 同时又是一个数列的通项问题.

我们不妨先考虑这个数列的前几项.整数更列的个数可由解递归关系而得到.考虑整数1, 2, …, n的更列, 对其进行合理分布, 恰当分类.

由分步计数原理和分类计数原理, 我们便得到了数列{Mn}的递推关系式:Mn= (n-1) (Mn-1+Mn-2) . (*)

显然, M1=0, M2=1, M3=2. (*) 式可进一步变形, Mn-nMn-1=-[Mn-1- (n-1) Mn-2]=…= (-1) n-3· (M3-3M2) = (-1) n-2= (-1) n.Mn-nMn-1= (-1) n式两边同乘undefined, 则有

undefined

由累加法, 得undefined

五、容斥原理在更列问题中的应用

例1 4只小鸟飞入四个不同的笼子里, 每只小鸟都有自己的一个笼子 (不同的鸟, 笼子也不同) , 每个笼子只能飞进一只鸟, 若都不飞进自己的笼子, 应有多少种不同的飞法?

解为了准确地计算出有多少种不同的飞法, 先求出4只小鸟随意飞有多少种不同的飞法, 然后减去不符合条件的飞法.

记A1={甲飞入自己的笼子而另3只鸟随意飞的飞法}, A2={乙飞入自己的笼子而另3只鸟随意飞的飞法}, A3={丙飞入自己的笼子而另3只鸟随意飞的飞法}, A4={丁飞入自己的笼子而另3只鸟随意飞的飞法}.

根据上面提到的公式:

undefined

若是5只小鸟按题意飞入鸟笼, 则有undefined (种) 不同的飞法.

例2 某市有8个县, 每县派出一个巡视组到本市别的县去检查工作 (每县去一组) , 问巡视组有多少种不同的分派方法?

解设这8个县的编号为1, 2, …, 8, 而ai为第i号县 (i=1, 2, …, 8) 派出的巡视组.I表示这8个巡视组分派到这8个县 (每县一组) 的所有可能的方法组成的集合, Ai表示I中ai分到i号县的分配方法组成的集合 (i=1, 2, …, 8) .依题意, 根据公式Mn=n!-Cundefined (n-1) !+Cundefined (n-2) !-…+ (-1) n·Cnn (n-n) !=8!-Cundefined (8-1) !+Cundefined (7-2) !-…+ (-1) 8·Cundefined (8-8) !=14833 (种) 分配方法, 即为所求.

参考文献

[1]李超英.排列和数列的汇合点——有趣的更列问题.中学数学参考, 2003 (9) :35.

[2]周小华.由“小鸟飞错鸟笼”谈容斥原理的应用.绍兴文理学院院报, 2001 (2) .

[3]吴国柱, 郝端绪.容斥原理在组合数学中的若干应用.冀东学刊, 1994 (6) :23.

篇3：容斥问题知识点及实例解析

关键词倾斜角开槽长度几何模型主成份分析

一、研究背景

为达到节省空间、结构稳定、造型美观的设计理念，某公司准备生产一种可折叠的桌子。桌子外形由直纹曲面构成，桌面呈圆形，桌腿随着铰链的活动可以平摊成一张平板。两组桌腿由若干根木条组成，每组各用一根两端分别固定在桌腿各组最外侧的两根木条上的钢筋将木条连接，为保证滑动的自由度，沿木条有空槽。

给定长方形平板尺寸为120cm？0cm？cm，每根木条宽2.5cm，若要求连接桌腿木条的钢筋固定在桌腿最外侧木条的中心位置，折叠后桌面距离地面53cm。如何折叠桌的动态变化过程，依此给出此折叠桌的设计加工参数和桌脚边缘线的数学描述是本文的研究课题。

二、研究方案

首先以折叠桌平板状态下利用几何画板建立直角坐标系，从而求得桌腿各木条的长度。当然，我们只需研究一组桌脚即可，甚至通过分析可知一组桌脚本身具有对称性，故我们所求桌脚各木条的长度以折叠桌所有桌脚木条的四分之一为代表。在确定桌腿木条开槽的长度时，简化三维空间计算的复杂性，将其分成各个子模块：最外侧木条与其余所研究的每根木条所在平面，利用初等几何法确定出设计加工参数。在此基础上，求出相关数据，通过Matlab软件拟合这些数据，确定出桌脚边缘线。并在Matlab软件上进行编程模拟出折叠桌的动态变化过程。

三、研究过程

第一步：以圆桌的圆心为原点，建立平面直角坐标系，将圆的半径等分为10份，作为分割木条的标准，第一根木条与圆的交点为%Z0，%Z1，，第二根木条与圆的交点为%Z1，%Z2，依次，第十根木条与圆的交点为%Z9，%Z10，，为使数据更精确，故取相邻两交点的纵坐标的平均值为木条切口，di为各木条切口到X轴的距离。从而求出我们所需要的代表性十根木条的长度Li：

x%Zi2+y%Zi2=R2（i=0，1，2，…，10），（R==25cm）di=

第二步：根据前面所得的di，以最外侧木条与其余所研究的每根木条i=0，1，2，…，10所在平面建立子模块。通过比较bi与GC的大小，可以判断木条相对于XOZ平面而言是往外侧靠还是往里侧靠，如果biGC，木条往里侧靠。并且可以求出开槽长度hi（i=0，1，2，…，10）。利用投影，推出公式：GC+OA=G2C2+O`A2，且AG=，H为桌子的高度。由于AF、AP1可以先由已知条件容易计算出，则

sin∠ACG=，GC=ACtan∠ACG，G2C2=GC+OA-O`A2

tan∠A2C2G2=，A2C2=

∠ACG和∠A2C2G2分别对应第一、二根木条与地面的倾斜角度，这样，可以由上述公式求出第一、二根木条的倾斜角，其他木条的倾斜角也可类似求得，开槽长度的具体计算如下：b=di+1-d1，JD=Li-L1/2，时，CD=

i=3，4，…，10時，CD=

无论木条往外侧靠还是往里侧靠，CD都可以表示为

于是给出各木条的开槽长度h2的表达式：

hi=JC=CD-JD=-（Li-L1/2）（i=3，4，…，10）

第三步：根据第二步中的几何关系，可以求得点的空间坐标：xP2=xP1-2.5=22.5

xP2=d2+MP1=，

ZP2=-3-DM=-3-

依次可以求其他点的空间坐标：xp1=xp1-2.5（i-1）

根据所求Pi空间坐标数据和以上公式，利用Matlab软件进行了编程，求出了倾斜角度、开槽长度和桌脚边缘点的坐标，模拟出折叠桌的动态变化过程。