挑战≈ 15 分钟未开始

容斥原理

核心概念

容斥原理——两集合:

|A \cup B| = |A| + |B| - |A \cap B|.

三集合:

|A\cup B\cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|.

记忆规律:奇数个集合的交加上,偶数个集合的交减去——"加单减双"。

补集思想(常配合使用):"至少有一个"往往用总数减去"一个都没有"来算:

|\text{至少一个}| = |\text{全体}| - |\text{一个都不满足}|.

容斥原理处理的是"重叠计数"。把两个集合的元素简单相加,落在交集里的元素被算了两次,所以要减掉一份交集补偿。到三个集合时,交集减过头了,又要把"三者公共部分"加回来——于是出现"加、减、加"的交替节奏。

它的画面感来自韦恩图:每块区域恰好被算一次,才是正确的总数。解题时先画三个圈,看清每块重叠被加了几次、应该补几次,公式就自然浮现。遇到"至少一个"难算时,反过来数"一个都不满足"往往更省力,这就是补集思想。

容斥原理

|A ∪ B| = 30 + 25 − 20 = 35

只在 A10

A∩B20

只在 B5

简单相加会把中间的交集算两次,所以要减掉一份。三个集合时则「加单减双」交替补偿。

例题 1两集合容斥

某班 $50$ 人,参加数学竞赛的有 $30$ 人,参加物理竞赛的有 $25$ 人,两科都参加的有 $20$ 人。至少参加一科的有几人?

▸查看解答步骤

答: 35 人

例题 2用补集数被整除问题

$1$ 到 $100$ 中,不能被 $2$ 也不能被 $5$ 整除的数有多少个?

▸查看解答步骤

答: 40 个

$|A|=30,\ |B|=25,\ |A\cap B|=20$ ,求 $|A\cup B|$ 。

$30+25-20 = 35$ 。

$1$ 到 $100$ 中,既不能被 $2$ 整除也不能被 $5$ 整除的数有几个?

被 $2$ 或 $5$ 整除的有 $50+20-10 = 60$ 个,其余 $100-60 = 40$ 个。

$1$ 到 $30$ 中,能被 $2$ 或 $3$ 整除的数有几个?

被 $2$ : $15$ 个;被 $3$ : $10$ 个;被 $6$ (同时): $5$ 个。 $15 + 10 - 5 = 20$ 个。

三集合容斥公式中, $|A\cap B\cap C|$ 前的符号是?

+

(加上)

-

(减去)不出现有时加有时减

"加单减双":三个集合的交是奇数个,符号为 $+$ 。

$1$ 到 $50$ 中能被 $2$ 或 $3$ 整除的数有几个?

被 $2$ : $25$ ;被 $3$ : $16$ ;被 $6$ : $8$ 。 $25+16-8 = 33$ 。

$|A|=20,\ |B|=15,\ |A\cup B|=30$ ,求 $|A\cap B|$ 。

$|A\cap B| = |A|+|B|-|A\cup B| = 20+15-30 = 5$ 。

前置知识点

接下来学习