容斥原理备忘录

这个备忘录可能很短,因为我也不知道要写什么。。。

容斥的普遍公式

要计算几个集合并集的大小,我们要先将所有单个集合的大小计算出来,然后减去所有两个集合相交的部分,再加回所有三个集合相交的部分,再减去所有四个集合相交的部分,依此类推,一直计算到所有集合相交的部分。
最终得到公式:
$$ \left|\bigcup_{i=1}^n A_i\right| = \sum_{\emptyset\neq J\subseteq{1,2,\ldots,n}}(-1)^{|J|-1} \Biggl|\bigcap_{j\in J} A_j\Biggr| $$
公式其实不太好看,还是从文字来理解比较好
接下来随便看一个例子

错排数

错排数是保证任意一个数字不在原位置 ($a_i\neq i$)的排列数
记长度为 $n$ 的错排数为 $D_n$ ,则
$$D_n=n!\sum_{i=0}^{n}\frac{(-1)^i}{i!} $$

解释一下,显然有 $\geq i$ 个数在原位置的方案数为 $C_n^i \cdot (n-i)!=\frac{n!}{i!}$ ,然后使用容斥原理得到 $D_n$
还有些别的方法求
给个表
0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570
发现一个递推关系
$$ D_n=nD_{n-1}+(-1)^n $$
也可以将 $D_n$ 以递推表示出
$$ D_n=(n-1)(D_{n-1}+D_{n-2}) $$
考虑前 $n-1$ 个已经处理完,第 $n$ 个的摆放方法
当前 $n-1$ 个已经错排时,可以拿当前这个和前面任意一个对换
当前 $n-1$ 个中有一个在原位置上时,可以将当前这个和它对换,总共有 $n-1$ 种可能的位置 $a_i=i$

总结

怎么才这么点就总结了
从应用途径上来看,容斥原理可以有效的弱化限制条件
当统计恰好 $k$ 个时,发现限制条件太强了,可以弱化为保证有 $k$ 个满足条件,剩下的随便
此时
$$ ans_k=\sum_{i=k}^{n} (-1)^i ans_{\geq i} $$

引用资料

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注