二项式反演 & 广义容斥笔记

· · 算法·理论

读前提醒：本文偏个人学习记录向，比较基础，如有不足或者欠缺请多多提出，欢迎评论或者私信指出问题、提出扩展谢谢！

1. 二项式反演

1.1 结论

若有：

f(x) = \sum_{i=0}^x \dbinom{x}{i} g(i)

则就有：

g(x) = \sum_{i=0}^{x} (-1)^{x-i} \dbinom{x}{i} f(i)

1.2 证明

看上面的右式：

\begin{aligned} \sum_{i=0}^x (-1)^{x-i} \dbinom{x}{i} f(i) &= \sum_{i=0}^x (-1)^{x-i} \dbinom{x}{i} \sum_{j=0}^i \dbinom{i}{j} g(j) \qquad (f(i) = \sum_{j=0}^i \dbinom{i}{j} g(j)) \\ &= \sum_{j=0}^x g(j) \sum_{i=j}^x (-1)^{x-i} \dbinom{x}{i} \dbinom{i}{j} \qquad (\text{移项}) \\ &= \sum_{j=0}^x g(j) \sum_{i=j}^x (-1)^{x-i} \dbinom{x}{j} \dbinom{x-j}{i-j} \quad ( \dbinom{x}{i} \dbinom{i}{j} = \dbinom{x}{j} \dbinom{x-j}{i-j})^1 \\ &= \sum_{j=0}^x \dbinom{x}{j} g(j) \sum_{i=j}^x (-1)^{x-i} \dbinom{x-j}{i-j} \\ &= \sum_{j=0}^x \dbinom{x}{j} g(j) \sum_{i'=0}^{x-j} (-1)^{x-i'-j} \dbinom{x-j}{i'} \qquad (i' = i-j) \\ &= \sum_{j=0}^x \dbinom{x}{j} g(j) \sum_{i'=0}^{x-j} (1)^{i'} (-1)^{x-i'-j} \dbinom{x-j}{i'} \\ &= \sum_{j=0}^x \dbinom{x}{j} g(j) (1 + (-1))^{x-j} \qquad (二项式定理) \\ &= g(x) \end{aligned} ### 1.3 其他形式 若有： $$ f(x) = \sum_{i=x}^n \dbinom{i}{x} g(i) $$ 则就有： $$ g(x) = \sum_{i=x}^{n} (-1)^{i-x} \dbinom{i}{x} f(i) $$ 证明和上面的差不多，可以自己试着推一下，这里给出完整过程： $$ \begin{aligned} \sum_{i=x}^n (-1)^{i-x} \dbinom{i}{x} f(i) &= \sum_{i=x}^n (-1)^{i-x} \dbinom{i}{x} \sum_{j=i}^n \dbinom{j}{i} g(j) \qquad (f(i) = \sum_{j=i}^n \dbinom{j}{i} g(j)) \\ &= \sum_{j=x}^n g(j) \sum_{i=x}^j (-1)^{i-x} \dbinom{i}{x} \dbinom{j}{i} \qquad (\text{移项}) \\ &= \sum_{j=x}^n g(j) \sum_{i=x}^j (-1)^{i-x} \dbinom{j}{x} \dbinom{j-x}{i-x} \quad ( \dbinom{j}{i} \dbinom{i}{x} = \dbinom{j}{x} \dbinom{j-x}{i-x})^2 \\ &= \sum_{j=x}^n \dbinom{j}{x} g(j) \sum_{i=x}^j (-1)^{i-x} \dbinom{j-x}{i-x} \\ &= \sum_{j=x}^n \dbinom{j}{x} g(j) \sum_{i'=0}^{j-x} (-1)^{i'} \dbinom{j-x}{i'} \qquad (i' = i-x) \\ &= \sum_{j=x}^n \dbinom{j}{x} g(j) \sum_{i'=0}^{j-x} (1)^{j-x-i'} (-1)^{i'} \dbinom{j-x}{i'} \\ &= \sum_{j=x}^n \dbinom{j}{x} g(j) (1 + (-1))^{j-x} \qquad (\text{二项式定理}) \\ &= g(x) \end{aligned} $$ $^2$：证明同 1.2 节中的 $^1$。 ### 1.4 例题 **[P5824 十二重计数法（$\text{III}$，$\text{VI}$）（第二类斯特林数）](https://www.luogu.com.cn/problem/P5824)** 有 $n$ 个球和 $m$ 个盒子，要全部装进盒子里，求方案数。 $\text{III}$：球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。 $\text{VI}$：球之间互不相同，盒子全部相同，每个盒子至少装一个球。 发现盒子相同的情况就是盒子不同的情况除以 $m!$，**先考虑盒子不同怎么做。** 固定盒子总数 $m$，令 $f_t$ 为将 $n$ 个球装进 $t$ 个箱子中的方案数（不要求非空），$g_t$ 为将 $n$ 个球装进 $t$ 个箱子中的方案数（非空）。 不难发现有 $f_t = t^n$，但因不要求非空，不能直接作为答案。 不要求非空时可把空盒子去掉，**那么 $f(m)$ 就是 $n$ 个球恰好装进 $1,2,...,m$ 个盒子的方案数总和**，形式化表示为： $$ f(m) = \sum_{i=0}^m \dbinom{m}{i} g(i) $$ 根据二项式反演可得： $$ g(m) = \sum_{i=0}^m (-1)^{m-i} \dbinom{m}{i} f(i) = \sum_{i=0}^m (-1)^{m-i} \dbinom{m}{i} i^n $$ 那么 $\text{III}$ 就完成了，而上面的式子正是**第二类斯特林数**（对应 $\text{VI}$）的计算式，即 $S(n,m) = \frac{1}{m!} g(m)$。 ## 2 广义容斥 ### 2.1 问题描述 若存在全集 $U = \{A_1,A_2,...,A_n\}$，其中 $A_i$ 表示所有含有第 $i$ 项特征的元素组成的集合，现要求恰好含有 $k$ 项特征的元素的个数 $\alpha(k)$。 ### 2.2 算法过程 恰好含有 $k$ 项特征的元素个数 $\alpha(k)$，需满足“属于某 $k$ 个特征集合的交集，且不属于其余所有特征集合”，形式化表示为： $$ \alpha(k) = \sum_{S\subseteq U,|S|=k} |\bigcap_{A \in S}A \cap \bigcap_{A^{'} \in U,A^{'} \notin S}\overline{A^{'}} | $$ 恰好含有不好处理，考虑“按特征子集计数”的中间量 $\beta(k)$：$\beta(k)$ 是所有大小为 $k$ 的特征子集 $S$ 对应的“$S$ 中所有特征至少都成立”的元素个数之和，即： $$ \beta(k) = \sum_{S\subseteq U,|S|=k} |\bigcap_{A\in S}A| $$ $\alpha(k)$ 与 $\beta(k)$ 满足如下等式： $$ \beta(k) = \sum_{i=k}^n \dbinom{i}{k} \alpha(i) $$ 证明：一个含有 $x$ 项特征的元素 $a$，记入 $\alpha(x)$ 一次，在算 $\beta(k)$ 时，贡献为从 $a$ 的 $x$ 个特征中选 $k$ 个的方案数 $\dbinom{x}{k}$，因此 $a$ 对左式和右式的贡献一致，等式成立。 根据二项式反演（1.3 中的其他形式），可推出： $$ \alpha(k) = \sum_{i=k}^n (-1)^{i-k} \dbinom{i}{k} \beta(i) $$ 而 $\beta(k)$ 可通过容斥原理计算并集大小得到，因此可借助 $\beta(k)$ 间接求出 $\alpha(k)$。 以上就是广义容斥的基本内容，推荐完成习题 1。 #### 2.3 习题 1. [[洛谷 P4859] 已经没有什么好害怕的了](https://www.luogu.com.cn/problem/P4859) 2. [[ATCoder AGC005D] ~K Perm Counting](https://www.luogu.com.cn/problem/solution/AT_agc005_d) 3. [[洛谷 P5395] 第二类斯特林数·行](https://www.luogu.com.cn/problem/P5395)（需要有多项式前置知识） 感谢你阅读我的文章！