排列组合进阶：容斥原理
产品经理的数学课 · 第11讲
排列组合进阶：容斥原理
当多个条件重叠时，如何避免「重复计数」或「遗漏计数」？容斥原理是你的数学武器。
前言
你的产品有三种会员：月卡、季卡、年卡。你想知道「至少拥有一种会员的用户有多少」。
你查了数据库：
- 月卡用户：10 万人
- 季卡用户：6 万人
- 年卡用户：3 万人
如果你直接加起来：10 + 6 + 3 = 19 万人。但总用户只有 15 万人！
问题出在哪里？重复计数——同时拥有月卡和季卡的用户被算了两次。
容斥原理就是解决这个问题的数学工具：它告诉你如何在多个条件重叠时，不重不漏地计数。
核心概念
两个集合的容斥原理
$$ |A \cup B| = |A| + |B| - |A \cap B| $$
直觉：A 和 B 的并集 = A 的元素 + B 的元素 - 重复计算的元素（A 和 B 的交集）
例子：你的 App 有两个功能：推送通知和邮件通知。
- 使用推送的用户：8 万
- 使用邮件的用户：5 万
- 同时使用两者的用户：3 万
至少使用一种通知的用户 = 8 + 5 - 3 = 10 万
三个集合的容斥原理
$$ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| $$
韦恩图：三个圆两两相交，中间有三重重叠。
┌─────────────────────────────┐
│ A │
│ ┌─────────┐ │
│ │ A∩B │ │
│ │ ┌───┐ │ B │
│ │ │A∩B∩C │ │ │
│ │ └───┘ │ │
│ │ A∩C │ B∩C │
│ └─────────┘ │
│ C │
└─────────────────────────────┘计算：
- 加上所有单个集合：A + B + C
- 减去所有两两交集：- A∩B - A∩C - B∩C
- 加上三三交集：+ A∩B∩C
例子：你的会员系统：
- 月卡用户：10 万
- 季卡用户：6 万
- 年卡用户：3 万
- 同时有月卡和季卡：4 万
- 同时有月卡和年卡：2 万
- 同时有季卡和年卡：1 万
- 同时有三种会员：0.5 万
至少有一种会员的用户 = 10 + 6 + 3 - 4 - 2 - 1 + 0.5 = 11.5 万
补集法：从全集中减去
有时候直接计算「至少有一个」很难，但计算「一个都没有」很容易。
$$ |A \cup B \cup C| = |U| - |\bar{A} \cap \bar{B} \cap \bar{C}| $$
例子：你的产品有三种付费功能。你想知道「至少使用一种付费功能的用户」。
- 总用户：100 万
- 不使用功能 A 的用户：70 万
- 不使用功能 B 的：80 万
- 不使用功能 C 的：85 万
- 不使用 A 且不使用 B 的：55 万
- 不使用 A 且不使用 C 的：60 万
- 不使用 B 且不使用 C 的：68 万
- 三种都不使用的：50 万
至少使用一种付费功能的用户 = 100 - 50 = 50 万
（补集法通常更简单——计算「都不满足」比「至少满足一个」容易。）
容斥原理与概率
容斥原理也适用于概率：
$$ P(A \cup B) = P(A) + P(B) - P(A \cap B) $$
例子：你的用户有 40% 的概率购买月卡，30% 的概率购买季卡，20% 的概率同时购买两者。用户购买至少一种会员的概率 = 0.4 + 0.3 - 0.2 = 0.5 = 50%
产品经理的应用
应用场景一：用户覆盖率计算
你有三种推荐算法，想知道「至少被一种算法覆盖的用户」。
| 算法 | 覆盖用户 | 两两重叠 | 三三重叠 |
|---|---|---|---|
| 算法 A | 80 万 | A∩B: 30 万 | A∩B∩C: 10 万 |
| 算法 B | 60 万 | A∩C: 20 万 | — |
| 算法 C | 40 万 | B∩C: 15 万 | — |
至少被一种算法覆盖的用户 = 80 + 60 + 40 - 30 - 20 - 15 + 10 = 125 万
决策：总用户 150 万，覆盖率 125/150 = 83%。还有 25 万用户没有被任何算法覆盖——需要开发新算法。
应用场景二：转化率计算
你的 App 有三种付费转化路径：
- 路径 A（应用内购买）：转化率 5%
- 路径 B（网页支付）：转化率 3%
- 路径 C（客服代付）：转化率 1%
- 同时用 A 和 B 的：2%
- 同时用 A 和 C 的：0.5%
- 同时用 B 和 C 的：0.3%
- 三种都用的：0.1%
至少使用一种付费路径的转化率 = 5% + 3% + 1% - 2% - 0.5% - 0.3% + 0.1% = 6.3%
洞察：三种路径的总和是 9%，但实际转化率只有 6.3%——因为很多用户会尝试多种路径。
应用场景三：A/B/C 测试的重叠
你同时运行了三个实验：
- 实验 A：1000 用户
- 实验 B：800 用户
- 实验 C：600 用户
- 同时在 A 和 B：300 用户
- 同时在 A 和 C：200 用户
- 同时在 B 和 C：150 用户
- 同时在三个实验：50 用户
至少在一个实验中的用户 = 1000 + 800 + 600 - 300 - 200 - 150 + 50 = 1800 用户
注意：如果实验之间有交互影响，你不能简单地合并实验结果——需要考虑重叠用户的影响。
常见误区
误区一：直接相加
「A 功能有 10 万用户，B 功能有 8 万用户，所以总用户 18 万」
错。如果两个功能有重叠用户，直接相加会重复计数。必须减去交集。
误区二：忘记加回三三交集
「三个集合的并集 = A + B + C - A∩B - A∩C - B∩C」
错。减去两两交集时，三三交集被多减了一次（在 A∩B、A∩C、B∩C 中各减了一次），所以需要加回来。
误区三：补集法计算错误
「至少一个 = 总数 - 一个都没有」
这是对的，但「一个都没有」的计算需要小心。你不能简单地把「不使用 A」「不使用 B」「不使用 C」相乘——因为它们可能不独立。
误区四：混淆「并集」和「交集」
「至少一个 = A ∪ B ∪ C（并集）」
「所有都有 = A ∩ B ∩ C（交集）」
这是正确的。但「恰好一个」「恰好两个」的计算需要更细致的容斥。
PM/BA 应用
| 场景 | 容斥工具 | 决策价值 |
|---|---|---|
| 用户覆盖 | 多集合并集 | 计算真实覆盖率 |
| 转化分析 | 转化路径重叠 | 避免重复计数 |
| 实验设计 | 实验组重叠 | 确保实验独立性 |
| 功能使用 | 功能使用并集 | 了解用户使用深度 |
| 风险评估 | 风险事件并集 | 计算综合风险概率 |
课后测验
题目 1
你的产品有两个付费功能：A 有 5 万用户，B 有 3 万用户，同时使用 A 和 B 的有 1 万用户。至少使用一种付费功能的用户有多少？
A. 8 万
B. 7 万
C. 6 万
D. 9 万
查看答案与解析
答案：B（7 万）
|A ∪ B| = |A| + |B| - |A ∩ B|
= 5 + 3 - 1
= 7 万
如果不减去交集，你会把同时使用 A 和 B 的 1 万用户计算两次。
题目 2
你的 App 有三种推送方式：App 内推送（60% 用户收到）、短信（40% 用户收到）、邮件（25% 用户收到）。同时收到 App 内推送和短信的有 20%，同时收到 App 内推送和邮件的有 10%，同时收到短信和邮件的有 8%，三种都收到的有 3%。至少收到一种推送的用户比例是多少？
A. 80%
B. 90%
C. 87%
D. 95%
查看答案与解析
答案：B（90%）
|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|
= 60% + 40% + 25% - 20% - 10% - 8% + 3%
= 90%
验证：90% 的用户至少收到一种推送。10% 的用户什么推送都没收到。
题目 3
你的总用户是 100 万。不使用功能 A 的有 70 万，不使用功能 B 的有 60 万，不使用功能 C 的有 50 万。如果三个功能的使用是独立的，至少使用一种功能的用户最接近多少？
A. 50 万
B. 60 万
C. 70 万
D. 80 万
查看答案与解析
答案：C（70 万）
如果独立：
- P(使用 A) = 0.3，P(使用 B) = 0.4，P(使用 C) = 0.5
- P(三种都不使用) = 0.7 × 0.6 × 0.5 = 0.21 = 21%
- P(至少使用一种) = 1 - 0.21 = 0.79 = 79%
79% × 100 万 = 79 万，最接近 C（70 万）。
注意：如果独立性假设不成立，实际值会不同。容斥原理在非独立情况下需要完整的交集数据。
本课要点
- 两个集合：|A ∪ B| = |A| + |B| - |A ∩ B|
- 三个集合：加单个、减两两交集、加三三交集
- 补集法：有时候计算「都不满足」比「至少一个」更容易
- 避免重复计数：容斥原理的核心价值
- 独立性假设：如果独立，可以简化计算；如果不独立，需要完整数据
延伸阅读
- Grimaldi, 《Discrete and Combinatorial Mathematics》第4章 — 容斥原理的详细推导
- Bóna, 《A Walk Through Combinatorics》 — 容斥原理的应用案例
- Stanley, 《Enumerative Combinatorics》 — 高级容斥原理
下一步
下一课：连续复利与年金 — 从离散到连续，理解指数增长的极限和年金的数学。
工具提示：画韦恩图是理解容斥原理的最好方法。把集合画成圆，重叠部分就是交集——然后按「加单个、减两两、加三三」的规则计算。