二项式反演
二项式反演
前置：组合数学基础
插板法
还是由一个例题引入。解不定方程 $\sum x_i = m$ 中正整数解的个数。
这就可以看成我们一共有 $m$ 个小球，然后分成 $n$ 组，其中每组不能为空。那这就相当于在 $m$ 个小球组成的 $m-1$ 个空隙中随意插板，这样就一共有 $\binom{m-1}{n-1}$ 种情况。
现在，如果 正整数 变为 非负整数，又该怎么办呢？
我们发现，如果提前先给每个人分到 $1$ 个小球，问题就又变成了正常的正整数问题了。这样小球会多出来 $n$ 个，于是这问题就是 $n+m$ 个小球中插入 $n$ 块板，答案就是 $\binom{n+m-1}{n-1}$。
现在，我们又要求所有的 $x_i$ 有一个限制条件是 $x_i\ge b_i$，那么如何做呢？
显然，我们先给每个人分 $b_i$ 个球，然后就变成了第二个问题，于是答案就是 $\displaystyle\binom{m-\sum b_i+n-1}{n-1}$。
多重集组合数
如果有集合 $S = {n_1\times a_1, n_2\times a_2,\dots,n_m\times a_m}$，其中 $a_i$ 前面的系数 $n_i$ 表示 $a_i$ 的个数，这样，我们在设 $n = \sum n_i$
，那么这些数的全排列的数量就是 $\displaystyle\frac{n!}{\prod n_i!}$，这是因为所有的排列里面同一个元素是不区分的。而这 $\displaystyle\frac{n!}{\prod n_i!}$ 就是多重集的排列数，也被称为 多重组合数。记为：
$$
\binom{n}{n_1,n_2,\dots,n_k} = \frac{n!}{\prod n_i !}
$$
它具体的内容拓展可以看 容斥原理 一节中有限制条件 $x_i\le b_i$ 的不定方程 $\sum x_i = m$。
二项式定理
这就不得不提到我们小学二年级就学过的二项式定理了。它被写作：
$$
(x+y)^n = \sum_{i=0}^n \binom{n}{i} x^iy^{n-i}
$$
同样，对于元数的拓展，我们可以使用多重集合数或者 杨辉高维体 的方法求得系数：
$$
(\sum x_i)^n = \sum_{\sum n_i = n} \binom{n}{n_1,n_2,\dots,n_k}\prod x_i^{n^i}
$$
其中，要求 $\forall i\in[1,k]\cap \mathbb{Z}$，有 $n_i \ge 0 \and n_i\in \mathbb{Z}$。
这里，多重组合数也有类似于一般组合数的性质，例如：
$$
\sum_{
\begin{matrix}
\sum n_i = n\
n_i\in [0,+\infty]\cap \mathbb{Z}
\end{matrix}
}
\binom{n}{n_1,n_2,\dots,n_k} = k^n
$$
组合数的性质
这里我们 根据 $\text{OI-wiki}$ 给出的式子，讲一讲组合数的一些进阶定理。
组合数的对称性
$$
\binom{n}{m} = \binom{n}{n-m}
$$
这是因为在 $n$ 中选择 $m$ 个显然等价于选择 $m$ 个剩下 $n-m$ 个。
递推式1
$$
\binom{n}{m} = \frac{n}{m}\binom{n-1}{m-1}
$$
证明
由定义：
$$
\begin{aligned}
\binom{n}{m} &= \frac{n!}{m!(n-m)!}\& = \frac{n}{m}\times \frac{(n-1)!}{(m-1)![(n-1)-(m-1)]!}\&=\frac{n}{m}\binom{n-1}{m-1}
\end{aligned}
$$
递推式2
$$
\binom{n}{m} = \binom{n-1}{m} +\binom{n-1}{m-1}
$$
证明
根据组合数的意义，相当于 $n$ 个数里面选择 $m$ 个，我枚举最后一个 选/不选，如果选，那么就在剩下的 $n-1$ 个里面选择 $m-1$ 个，否则在 $n-1$ 个里面选择 $m$ 个。
判零定理
$$
\sum_{i=1}^n(-1)^i\binom{n}{i} = [n=0]
$$
其中 $[n=0]$ 代表 $f(n) = \begin{cases} 1, &n=0\0, &n\not = 0 \end{cases}$。
证明
$$
\begin{aligned}
\sum_{i=1}^n(-1)^i\binom{n}{i} &= \sum_{i=1}^n\binom{n}{i}(-1)^i1^{n-i}
\ &=(-1+1)^n\&=0^n\&=[n=0]
\end{aligned}
$$
拆组合数
$$
\sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\binom{n+m}{m}
$$
证明
$$
\sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\sum_{i=0}^m\binom{n}{i}\binom{m}{m-i}
$$
而这个式子等价于在 $n+m$ 个数中枚举前 $n$ 个中要选择几个，然后给最后的答案贡献上前 $n$ 个选 $i$ 个的情况和后 $m$ 个选择 $m-i$ 个的情况，于是就等价于 $n+m$ 中选择 $m$ 个。
推论1
$$
\sum_{i=0}^n\binom{n}{i}^2 = \binom{2n}{n}
$$
由 拆组合数，该式显然成立。
带权组合数
$$
\sum_{i=0}^n i\binom{n}{i} = n\times 2^{n-1}
$$
证明
记：
$$
S = \sum_{i=0}^ni\binom{n}{i}
$$
于是：
$$
\begin{aligned}
2S &= \sum_{i=0}^ni\binom{n}{i} + \sum_{i=0}^ni\binom{n}{i}\
&= \sum_{i=0}^ni\binom{n}{i} + \sum_{i=0}^ni\binom{n}{n-i}\
&= \sum_{i=0}^ni\binom{n}{i} +\sum_{i=0}^n(n-i)\binom{n}{i}\
&= \sum_{i=0}^nn\binom{n}{i} = n\times 2^n
\end{aligned}
$$
因此有 $S = n\times 2^{n-1}$。
推论2
$$
\sum_{i=0}^ni^2\binom{n}{i} = n(n+1)2^{n-2}
$$
约分公式
$$
\binom{n}{k}\binom{k}{m} = \binom{n}{m}\binom{n-m}{k-m}
$$
证明
由定义：
$$
\begin{aligned}
\binom{n}{k}\binom{k}{m} &= \frac{n!}{k!(n-k)!}\times \frac{k!}{m!(k-m)!}\
&=\frac{n!(n-m)!}{(n-k)!(k-m)!m!(n-m)!}\
&=\frac{n!}{m!(n-m)!}\times \frac{(n-m)!}{(k-m)![(n-m)-(k-m)]!}\
&=\binom{n}{m}\binom{n-m}{k-m}
\end{aligned}
$$
正文：二项式反演
如果有函数 $f(n),g(n)$，满足关系：
$$
g(n) = \sum_{i=0}^n \binom{n}{i} f_i
$$
则一定有相反的关系：
$$
f(n) = \sum_{i=0}^n\binom{n}{i}(-1)^{n-i}g_i
$$
证明
不妨将 $g_n$ 的定义回带到反演公式中：
$$
\begin{aligned}
f(n) &= \sum_{i=0}^n\binom{n}{i}(-1)^{n-i}g_i\
&= \sum_{i=0}^n\binom{n}{i}(-1)^{n-i}\sum_{j=0}^i\binom{i}{j}f_j
\end{aligned}
$$
这时候我们改变枚举顺序：
$$
\begin{aligned}
f_n &= \sum_{i=0}^n\binom{n}{i}(-1)^{n-i}\sum_{j=0}^i\binom{i}{j}f_j
\&= \sum_{i=0}^n\sum_{j=0}^i\binom{n}{i}\binom{i}{j}(-1)^{n-i}f_j\
&=\sum_{j=0}^nf_j\sum_{i=j}^n\binom{n}{i}\binom{i}{j}(-1)^{n-i}
\end{aligned}
$$
这个时候我们想起来刚刚学习的 约分公式：
$$
\begin{aligned}
f_n &= \sum_{j=0}^nf_j\sum_{i=j}^n\binom{n}{i}\binom{i}{j}(-1)^{n-i}\
&= \sum_{j=0}^nf_j\sum_{i=j}^n\binom{n}{j}\binom{n-j}{i-j}(-1)^{n-i}\
&= \sum_{j=0}^nf_j\binom{n}{j}\sum_{i=j}^n \binom{n-j}{i-j}(-1)^{n-i}
\end{aligned}
$$
我们记 $k=i-j,m = n-j$，然后枚举 $k$，得到：
$$
\begin{aligned}
f_n &= \sum_{j=0}^nf_j\binom{n}{j}\sum_{i=j}^n \binom{m}{i-j}(-1)^{n-i}\
&= \sum_{j=0}^nf_j\binom{n}{j}\sum_{k=0}^{n-j}\binom{m}{k}(-1)^{m-k}\
&= \sum_{j=0}^n f_j\binom{n}{j} [n = j]\
&= f_n
\end{aligned}
$$
证毕。
拓展
另外，类似于莫比乌斯反演，它也有另一种表达形式：
如果有：
$$
g(n) = \sum_{i=n}^x\binom{i}{n}f_i
$$
则相反的，有：
$$
f_n = \sum_{i=n}^x\binom{i}{n}(-1)^{i-n}g_i
$$
例题
[P6478 [NOI Online #2 提高组] 游戏]([P6478 NOI Online #2 提高组] 游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
Des
给定一棵共有 $n=2m$ 个节点的树。树上的每个节点有一个颜色，一共有两种颜色，每种颜色共 $m$ 个节点。共进行 $m$ 次操作，每次操作会从这棵树上选择两个没有被选过的异色点对。现在问对于 $\forall k\in[0,m]\cap \mathbb{Z}$，求在随机选点的情况下，$m$ 次选择有 $k$ 次选择的点对不为 祖先-儿子 对的情况数量。模数。
Sol
题目的要求是求 恰好 $k$ 次不为 祖先-儿子 点对的情况数，我们设这为 $f_k$，而我们比较好求的是 钦定有 $k$ 次操作不为 祖先-儿子 关系的点对的情况数，设为 $g_k$。
Warning
这里的 钦定 可以理解为 至少 有 $k$ 对，剩下的是不是我们不管。
于是，显然有 $g$ 与 $f$ 的关系式：
$$
g_n = \sum_{i=n}^m\binom{i}{n}f_i
$$
于是我们可以根据二项式反演轻松写出 ：
$$
f_n = \sum_{i=n}^m\binom{i}{n}(-1)^{i-n}g_i
$$
于是只需要求出 $g_k$ 即可。
这里需要用到 树形背包，我们设 $dp_{u,k}$ 表示 $u$ 子树内钦定 祖先-儿子 点对的数量为 $k$ 时的方案数，那么显然在子树内有转移：
$$
f_{u,k} = \sum_{\begin{matrix}\sum k_v = k \ v\in son_u\end{matrix}} \prod f_{v,k_v}
$$
枚举子树一个一个乘起来即可，这一部分精细实现可以达到 $O(n^2)$。
然后我们再考虑当前节点 $u$。显然，当前节点 $u$ 可以与异色节点产生一个贡献，我们枚举 $k$，不难得到转移方程：
$$
f_{u,k} = f_{u,k} + f_{u,k-1}\times (sz_{!col_u} - (k-1))
$$
这是因为 $u$ 可以跟所有异色节点产生贡献，而因为贡献只能产生 $1$，于是会有 $k-1$ 个异色节点用掉了，剩下的 $sz_{!col_u}-(k-1)$ 个点徐阿换一个即可。
Code
1 |
|