容斥原理

提出者：张超

来自知乎：数值策划备忘录——用容斥原理解决套装收集问题

说明

简单介绍一下容斥原理：

在计数的时候，为了避免重叠部分被反复计算，我们可以先不考虑重叠部分，直接进行求和计算，再把重叠的部分减去。

首先我先抛出公式：

已知三个圆圈的面积，以及它们两两重叠、三个重叠的面积，如何算出以上所有区域总的面积大小？

思路是：

直接把已知的三个圆圈面积求和，再减去多加了一次的两两重叠的面积，再加上多减了一次的三个重叠的面积

即：

总面积=三个圆圈的面积和-两两重叠的面积和+三个重叠的面积和

（上面的公式用大白话翻译过来就是这样）

我们分别记图中1-7块区域的面积为

已知：

橙色圆圈的面积

绿色圆圈的面积

蓝色圆圈的面积

橙绿重叠的面积

橙蓝重叠的面积

绿蓝重叠的面积

橙绿蓝重叠的面积

那么按照我们上面的结论：

总面积=三个圆圈的面积和-两两重叠的面积和+三个重叠的面积和

计算结果符合我们的预期。

*拓展：如果圆圈的数量增多，那么：

总面积=n个圆圈的面积和-两两重叠的面积和+三三重叠的面积和-四四重叠的面积和

n个重叠的面积和

应用

OK，现在我们回到套装收集问题。

击杀1只史莱姆最多会掉落1件装备，有10%的概率掉落头盔，有20%的概率掉落衣服，有25%的概率掉落裤子，求平均集齐1套装备需要击杀史莱姆的次数。

我们将“掉落头盔”这个事件记为A，P(A)=10%；

“掉落衣服”这个事件记为B，P(B)=20%；

“掉落裤子”这个事件记为C，P(C)=25%；

那么，我们很容易知道：

平均掉落1件头盔需要击杀史莱姆次数E(A)=1/P(A)=10次

平均掉落1件衣服需要击杀史莱姆次数E(B)=1/P(B)=5次

平均掉落1件裤子需要击杀史莱姆次数E(C)=1/P(C)=4次

现在我们画出三个圆圈

圆圈的面积表示掉落单个装备所需击杀史莱姆的次数；

圆圈两两重叠部分的面积表示这两个装备至少掉落一个所需击杀史莱姆的次数；

总面积表示集齐1套装备所需击杀史莱姆的次数。

根据容斥原理：

所以集齐1套装备需要击杀史莱姆的次数为12.4055次。

装备的件数变多，也依旧可以如法炮制。

这样一来，通过简单的加减乘除运算，我们就能获得我们所需要的期望。