关于容斥原理

2018-09-29 11:38:45


对容斥的理解一直不是很透彻,略写一点,稍作整理

注:本文有部分引自没想好叫什么名字大佬的博客


最简单的容斥

求几个集合的并集,如:

$|A∩B∩C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|$

用维恩图也可以轻松得出

由三个集合的并集大小可以推广到 $n$ 个集合的并集大小

即:各集合之和-两个集合的交集+三个集合的交集……

同理,也可以用这种方法求解概率的问题

如:事件集合 $A_i(i∈[1,n])$ ,求发生其中某些事件(至少发生一个事件)的概率


关于证明

贴个链接


实际问题中的应用

  • 简单排列问题:用 $0$ 到 $9$ 的数字组成不重复的排列,要求第一个数大于 $1$ ,最后一个数小于 $8$ ,有多少种排列方式

    正难则反,我们可以求出第一个数小于等于 $1$ ,最后一个数大于等于 $8$ 的排列数

    设第一个数小于等于 $1$ 时的集合为 $X$ ,最后一个数大于等于 $8$ 的集合为 $Y$

    根据容斥原理得,所求为 $|X|+|Y|-|X∩Y|$

    用简单的排列组合可以得到答案为 $S=2\times9!+2\times9!-2\times2\times8!$

    那么原题答案 $Ans=10!-S$


  • $0,1,2$ 序列问题:长度为 $n$ 的由 $0,1,2$ 组成的序列,要求每个数字至少出现 $1$ 次,有多少种排列方式

    还是逆向思维,考虑不出现某些数字的情况

    设 $A_i$ 表示不出现数字 $i$ 的序列数,根据容斥原理,得到逆问题的结果为:

    $|A_0|+|A_1|+|A_2|-|A_0∩A_1|-|A_0∩A_2|-|A_1∩A_2|+|A_0∩A_1∩A_2|$

    可以发现每个 $A_i$ 的值都是 $2^n$ (因为只有两个数)

    $A_i$ 两两相交的值都是 $1$ (只有一个数)

    所以原题答案为 $3^n-3\times2^n+3\times1-0$


  • 方程整数解问题:给出一个方程: $x_1+x_2+...+x_n=t$ ,其中 $0<=x_i<=m$ ,求方程整数解的数量

    先忽略 $x_i$ 的限制,考虑方程非负整数解的数量

    问题等价于求方程 $(x_1+1)+(x_2+1)+...(x_n+1)=t+n$ 的正整数解

    相当于有 $t+n$ 个 $1$ ,要在其中放 $(n-1)$ 块隔板,因此有 $C_{t+n-1}^{n-1}$ 中放法

    所以原方程的非负整数解有 $C_{t+n-1}^{n-1}$ 组

    用容斥原理来讨论它的逆问题,即当 $x>m$ 时的解

    定义 $A_k$ 为 $x_k>m$ 且其他 $x_i>=0$ 时的集合

    沿用隔板的思想,有 $m+1$ 个位置已经被占用了,所以 $|A_k|=C_{t+n-m-2}^{n-1}$

    计算这样两个集合 $A_k$ 和 $A_p$ 的交集

    $|A_k∩A_p|=C_{t+n-2m-3}^{n-1}$

    考虑到总和为 $t$ ,这样的集合个数是有限制的,设最多有 $k$ 个

    逆问题答案 $Res=C_{n}^{1}*C_{t+n-m-2}^{n-1}-C_{n}^{2}*C_{t+n-2m-3}^{n-1}+...C_{n}^{k}*C_{t+n-km-k-1}^{n-1}$

    原问题答案即为 $Ans=C_{t+n-1}^{n-1}-Res$

    这道题里有用到


  • 求区间 $[1,r]$ 内与 $n$ 互质的数的个数

    先计算不与 $n$ 互质的数的个数

    考虑 $n$ 的所有质因子 $p_i(i∈[1,k])$

    在 $[1,r]$ 内能被 $p_i$ 整除的数的个数为: $\lfloor{r/p_i}\rfloor$

    但是如果直接相加,就会出现重复计算的情况(一个数可能被多个质因子整除)

    可以用 $2^k$ 的算法求出所有的质因子组合,计算每种组合的 $p_i$ 乘积,通过容斥原理处理结果

    题在这

    具体实现代码