Skip to content

容斥问题

一、两者容斥

  如果被计数的事物有 A、B 两类,那么,先把 A、B 两个集合的元素个数相加,A 和 B 中都算了一次 A∩B 部分的元素,所以要把这部分重复计算的元素减去一次。如下图所示。


I-非A且非B=A+B-A‌∩B


  1. 如果题目中有提到类似“每人参加了至少一项”的表述,说明都不满足数=0、非A且非B=0

二、三者容斥


I-非A且非B且非C=A+B+C-A‌∩B-B‌∩C-A‌∩C+A‌∩B‌∩C


  三集合标准公式:总数-都不满足=A+B+C-(A∩B)-(A∩C)-(B∩C)+(A∩B∩C)
  三集合变形公式 :总数-都不满足=A+B+C-只满足两项-2×满足三项

公式推导

  1. 根据上图:总数-都不满足=1+2+3+4+5+6+7A=1+4+6+7B=3+5+6+7C=2+4+5+7
  2. 然后A+B+C=1+2+3+++++++++
  3. 发现跟总数-都不满足相比,4、5、6多计算了一次,7多计算两次。
  4. 4代表只满足AC,5代表只满足BC,6代表只满足AB,我们把4、5、6三块统称为“只满足两项”
  5. 7是A‌∩B‌∩C,统称为“满足三项”
  6. 因此总数-都不满足=A+B+C-只满足两项-2×满足三项(变形公式)
  7. 我们在换个思路,4+7可以表示A∩C,5+7可以表示B∩C,6+7可以表示A∩B
  8. 因此我们可以这样写:A+B+C-(4+7)-(5+7)-(6+7)=1+2+3+4+5+6
  9. 发现多减了一个7,因此需要加回来,所以总数-都不满足=A+B+C-(4+7)-(5+7)-(6+7)+7
  10. 即所以总数-都不满足=A+B+C-A∩B-A∩C-B∩C+A∩B∩C(标准公式)

  如果题目中有提到类似“每人参加了至少一项”的表述,说明都不满足数=0,即 非A且非B且非C=0

  1. 解题步骤分三步走
    1. ①画文氏图;
    2. ②弄清楚图形中每一部分所代表的含义;
    3. ③代入公式

三、容斥的极值问题

方法1:多集合反向构造

  1. 第一步:反向。先分别反向求出各集合的补集;例如:不喜欢音乐、舞蹈、美术的学生,分别有9、11、14人;
  2. 第二步:加和。反向的补集进行相加;例如:这9、11、14人毫无重复,则此时’不都喜欢’的最多,有9+11+14=34(人);
  3. 第三步:做差。例如:’不都喜欢‘的最多,那么‘都喜欢的’最少,有45-34=11(人)。
  4. 这种思路的核心是“让不都喜欢的无任何重复,则不满足要求的最多”。

方法2:正向思路

  1. 求最小值
    1. 两个集合A、B交集的最小值为A+B-U(U为全集)
    2. 三个集合A、B、C交集的最小值为A+B+C-2U(U为全集)
    3. 四个集合A、B、C、D交集的最小值为A+B+C+D-3U(U为全集)
  2. 求最大值
    1. N个集合交集的最大值均为较小的集合

四、随笔练习

  1. 例1:(2016年河南省) 某公司组织歌舞比赛,共 68 人参赛。其中,参加舞蹈比赛的有 12 人,参加歌唱比赛的有 18 人,45 人什么比赛都没有参加。问同时参加歌舞比赛的有多少人? ( )
  2. A.7
  3. B.8
  4. C.9
  5. D.10
。所以两项比赛都参加的人数为 12+18-(68-45)=7 人。故答案为A

  1. 例2:(2011年国家) 某市对 52 种建筑防水卷材产品进行质量抽检,其中有 8 种产品的低温柔度不合格,10 种产品的可溶物含量不达标,9 种产品的接缝剪切性能不合格,同时两项不合格的有 7 种,有 1 种产品这三项都不合格。则三项全部合格的建筑防水卷材产品有多少种? ( )
  2. A.34
  3. B.35
  4. C.36
  5. D.37
:在将低温柔度不合格、可溶物含量不达标、接缝剪切性能不合格的产品数相加时,两项同时不合格的产品数被计算了两次,;三项同时不合格的产品数被计算了三次,。设三项全合格的建筑防水卷材产品有 x 种,根据容斥原理可得,8+10+9-7-2×1+x=52,解得 x=34。故答案为A

  1. 例3:(2018年江西) 某高校做有关碎片化学习的问卷调查,问卷回收率为90%,在调查对象中有180人会利用网络课程进行学习,200人利用书本进行学习,100人利用移动设备进行碎片化学习,同时使用三种方式学习的有50人,同时使用两种学习方式的有20人,不存在三种学习都不用的人。那么这次共发放了多少份问卷?
  2. A.370
  3. B.380
  4. C.390
  5. D.400
:这是一道。注意题目中提到:不存在三种学习都不用的人。所以在的过程中,非A且非B且非C=0。代入三集合容斥问题非标准形式得到:总人数=180+200+100-20-2*50,总人数=360,总问卷=360/90%=400。答案选D。

  1. 例4:(2024广东梅州事业单位) 某单位42名职工参加健身活动,每人至少参加一种,已知参加瑜伽的有22人,参加蛙跳的有30人,参加跑步的有15人,其中5名职工三种健身活动都参加了,该单位有( )名职工只参加了一种健身活动?
  2. A.19
  3. B.20
  4. C.21
  5. D.22
:这是一道。根据三集合容斥问题非标准型公式:A+B+C-满足两项-满足三项×2=总数-都不,可得:22+30+15-参加两种健身活动-5x2=42-0,解得参加两种健身活动的人数 = 15。根据三集合容斥问题常识公式:满足一项+ 满足两项 + 满足三项 = 总数-都不,则只参加一种健身活动的人数=42-15-5=22人。故正确答案为D。