容斥原理(翻译)



这篇文章发表于http://e-maxx.ru/algo/inclusion_exclusion_principle,原文是 俄语的。由于文章确实很实用,而且鉴于国内俄文资料翻译的匮乏,我下决心将其翻译之。由 于俄语对我来说如同乱码,而用Google直接翻译中文的话又变得面目全非,所以只能先用Google翻译成英语,再反复读,慢慢理解英语的意思,实在是弄得我头昏脑胀。因此在理解文章意思然后翻译成中文的时候,中文都不知道如何表述了。而又由于我对容斥原理知识的匮乏,很可能有些地方我的表述是错误的。

如果你对这篇文章有什么不理解的地方,可以去网站论坛的Feedback版(http://e-maxx.ru/forum/viewforum.php?id=6)发问。不过这可是俄语的,所以直接问我吧:)

QQ:573525822,E-mail: 573525822@qq.com 或 veecci@gmail.com
pdf版本:/Files/vici/inclusion-exclusion.pdf

UPD 9.6:感谢原作者的回复,一些错误已经被修正了。


容斥原理 原作:e-maxx(Russia)发表于 2011.8.25
翻译:vici
对容斥原理的描述 容斥原理是一种重要的组合数学方法,可以让你求解任意大小的集合,或者计算复合事件的概率。
描述
容斥原理可以描述如下:
要计算几个集合并集的大小,我们要先将所有单个集合的大小计算出来,然后减去所有两个集合相交的部分,再加回所有三个集合相交的部分,再减去所有四个集合相交的部分,依此类推,一直计算到所有集合相交的部分。
关于集合的原理公式
上述描述的公式形式可以表示如下:

容斥原理(翻译)
文章图片

它可以写得更简洁一些,我们将B作为所有Ai的集合,那么容斥原理就变成了:
容斥原理(翻译)
文章图片

这个公式是由 De Moivre (Abraham de Moivre)提出的。
关于维恩图的原理
用维恩图来表示集合A、B和C:
容斥原理(翻译)
文章图片

那么容斥原理(翻译)
文章图片
的面积就是集合A、B、C各自面积之和减去容斥原理(翻译)
文章图片
, 容斥原理(翻译)
文章图片
, 容斥原理(翻译)
文章图片
的面积,再加上容斥原理(翻译)
文章图片
的面积。
容斥原理(翻译)
文章图片


由此,我们也可以解决n个集合求并的问题。
关于概率论的原理
设事件容斥原理(翻译)
文章图片
容斥原理(翻译)
文章图片
代表发生某些事件的概率(即发生其中至少一个事件的概率),则:
容斥原理(翻译)
文章图片

这个公式也可以用B代表Ai的集合:
容斥原理(翻译)
文章图片


容斥原理的证明 我们要证明下面的等式:
容斥原理(翻译)
文章图片

其中B代表全部Ai的集合
我们需要证明在Ai集合中的任意元素,都由右边的算式被正好加上了一次(注意如果是不在Ai集合中的元素,是不会出现在右边的算式中的)。
假设有一任意元素在k个Ai集合中(k>=1),我们来验证这个元素正好被加了一次:
当size(C)=1时,元素x被加了k次。
当size(C)=2时,元素x被减了C(2,k)次,因为在k个集合中选择2个,其中都包含x。
当size(C)=3时,元素x被加了C(3,k)次。
……
当size(C)=k时,元素x被加/减了C(k,k)次,符号由sign(-1)^(k-1)决定。
当size(C)>k时,元素x不被考虑。
然后我们来计算所有组合数的和。
容斥原理(翻译)
文章图片

由二项式定理,我们可以将它变成:
容斥原理(翻译)
文章图片

我们把x取为1,这时容斥原理(翻译)
文章图片
表示1-T(其中T为x被加的总次数),所以容斥原理(翻译)
文章图片
,证明完毕。
对于实际问题的应用 容斥原理的理论需要通过例子才能很好的理解。
首先,我们用三个简单的例子来阐释这个理论。然后会讨论一些复杂问题,试看如何用容斥原理来解决它们。
其中的“寻找路径数”是一个特殊的例子,它反映了容斥问题有时可以在多项式级复杂度内解决,不一定需要指数级。
一个简单的排列问题
由0到9的数字组成排列,要求第一个数大于1,最后一个数小于8,一共有多少种排列?
我们可以来计算它的逆问题,即第一个元素<=1或者最后一个元素>=8的情况。
我们设第一个元素<=1时有X组排列,最后一个元素>=8时有Y组排列。那么通过容斥原理来解决就可以写成:
容斥原理(翻译)
文章图片

经过简单的组合运算,我们得到了结果:
容斥原理(翻译)
文章图片

然后被总的排列数10!减,就是最终的答案了。
(0,1,2)序列问题
长度为n的由数字0,1,2组成的序列,要求每个数字至少出现1次,这样的序列有多少种?
同样的,我们转向它的逆问题。也就是不出现这些数字的序列 不出现其中某些数字的序列。
我们定义Ai(i=0…2)表示不出现数字i的序列数,那么由容斥原理,我们得到该逆问题的结果为:
容斥原理(翻译)
文章图片


可以发现每个Ai的值都为2^n(因为这些序列中只能包含两种数字)。而所有的两两组合容斥原理(翻译)
文章图片
都为1(它们只包含1种数字)。最后,三个集合的交集为0。(因为它不包含数字,所以不存在)
要记得我们解决的是它的逆问题,所以要用总数减掉,得到最终结果:
容斥原理(翻译)
文章图片

方程整数解问题
给出一个方程:
容斥原理(翻译)
文章图片

其中容斥原理(翻译)
文章图片

求这个方程的整数解有多少组。
我们先不去理会xi<=8的条件,来考虑所有正整数解的情况。这个很容易用组合数来求解,我们要把20个元素分成6组,也就是添加5块“夹板”,然后在25个位置中找5块“夹板”的位置。
容斥原理(翻译)
文章图片

然后通过容斥原理来讨论它的逆问题,也就是x>=9时的解。
我们定义Ak为xk>=9并且其他xi>=0时的集合,同样我们用上面的添加“夹板”法来计算Ak的大小,因为有9个位置已经被xk所利用了,所以:
容斥原理(翻译)
文章图片

然后计算两个这样的集合Ak、Ap的交集:
容斥原理(翻译)
文章图片

因为所有x的和不能超过20,所以三个或三个以上这样的集合时是不能同时出现的,它们的交集都为0。最后我们用总数剪掉用容斥原理所求逆问题的答案,就得到了最终结果:
容斥原理(翻译)
文章图片

求指定区间内与n互素的数的个数:
给出整数n和r。求区间[1; r]中与n互素的数的个数。
去解决它的逆问题,求不与n互素的数的个数。
考虑n的所有素因子pi(i=1…k)
在[1; r]中有多少数能被pi整除呢?它就是:
容斥原理(翻译)
文章图片

然而,如果我们单纯将所有结果相加,会得到错误答案。有些数可能被统计多次(被好几个素因子整除)。所以,我们要运用容斥原理来解决。
我们可以用2^k的算法求出所有的pi组合,然后计算每种组合的pi乘积,通过容斥原理来对结果进行加减处理。
关于此问题的最终实现:

int solve (int n, int r) {

vector p;

for (int i=2; i*i<=n; ++i)

if (n % i == 0) {

p.push_back (i);

while (n % i == 0)

n /= i;

}

if (n > 1)

p.push_back (n);


int sum = 0;

for (int msk=1; msk<(1<
int mult = 1,

bits = 0;

for (int i=0; i<(int)p.size(); ++i)

if (msk & (1<
++bits;

mult *= p[i];

}


int cur = r / mult;

if (bits % 2 == 1)

sum += cur;

else

sum -= cur;

}


return r - sum;

}

算法的复杂度为 容斥原理(翻译)
文章图片

求在给定区间内,能被给定集合至少一个数整除的数个数
给出n个整数ai和整数r。求在区间[1; r]中,至少能被一个ai整除的数有多少。
解决此题的思路和上题差不多,计算ai所能组成的各种集合(这里将集合中ai的最小公倍数作为除数)在区间中满足的数的个数,然后利用容斥原理实现加减。
此题中实现所有集合的枚举,需要2^n的复杂度,求解lcm需要O(nlogr)的复杂度。
能满足一定数目匹配的字符串的个数问题
给出n个匹配串,它们长度相同,其中有一些’?’表示待匹配的字母。然后给出一个整数k,求能正好匹配k个匹配串的字符串的个数。更进一步,求至少匹配k个匹配串的字符串的个数。
首先我们会发现,我们很容易找到能匹配所有匹配串的字符串。只需要对比所有匹配串,去在每一列中找出现的字母(或者这一列全是’?’,或者这一列出现了唯一的字母,否则这样的字符串就存在),最后所有字母组成的单词即为所求。
现在我们来学习如何解决第一个问题:能正好匹配k个匹配串的字符串。
我们在n个匹配串中选出k个,作为集合X,统计满足集合X中匹配的字符串数。求解这个问题时应用容斥原理,对X的所有超集进行运算,得到每个X集合的结果:
容斥原理(翻译)
文章图片

此处f(Y)代表满足匹配集合Y的字符串数。
如果我们将所有的ans(X)相加,就可以得到最终结果:
容斥原理(翻译)
文章图片

这样,就得到了一个复杂度容斥原理(翻译)
文章图片
的解法。
这个算法可以作一些改进,因为在求解ans(X)时有些Y集合是重复的。
回到利用容斥原理公式可以发现,当选定一个Y时,所有 容斥原理(翻译)
文章图片
中X的结果都是相同的,其符号都为容斥原理(翻译)
文章图片
。所以可以用如下公式求解:
容斥原理(翻译)
文章图片

这样就得到了一个复杂度容斥原理(翻译)
文章图片
的解法。
【容斥原理(翻译)】

    推荐阅读