二项式反演

定理 \(1\)：\(F(n)=\sum_{i=0}^{n}{{n\choose i}G(i)}\Leftrightarrow G(n)=\sum_{i=0}^{n}{(-1)^{n-i}{n\choose i}F(i)}\)

证明：

提取系数有 \(F[n]=\sum_{i=0}^{n}{{n\choose i}G[n]}\)

\(\displaystyle \to \frac{F[n]}{n!}=\sum_{i=0}^{n}{\frac{1}{(n-i)!}\frac{G[i]}{i!}}\)

构造指数生成函数 \(\displaystyle f(n)=\sum_{i=0}^{\infty}{\frac{F[i]}{i!}x^i},g(n)=\sum_{i=0}^{\infty}{\frac{G[i]}{i!}x^i}, E(x)=e^x=\sum_{i=0}^{\infty}{\frac{x^i}{i!}}\)

可以发现卷积形式：\(f=g\ast E\)

于是，\(g=f\ast E^{-1}=f\ast e^{-x}\)

所以可以得到 \(\displaystyle g[n]=\frac{G[n]}{n!}=\sum_{i=0}^{n}f[i]\times (-1)^{n-i}\frac{1}{(n-i)!}\)

整理得：\(\displaystyle \frac{G[n]}{n!}=\sum_{i=0}^{n}{\frac{F[i]}{i!}\times (-1)^{n-i}\frac{1}{(n-i)!}}\)

证毕。

稍微变换一下，可以得到二项式反演的另一种形式。

定理 \(2\)： \(F(n)=\sum_{i=0}^{n}{(-1)^i{n\choose i}G(i)}\Leftrightarrow G(n)=\sum_{i=0}^{n}{(-1)^{i}{n\choose i}F(i)}\)

非常的对称唉。可以发现这只在定理 \(1\) 移动了 \(-1\) 的次幂。

定理 \(3\)： \(\displaystyle F(n)=\sum_{i=n}{{n\choose i}G(i)}\Leftrightarrow G(n)=\sum_{i=n}{(-1)^{n-i}{n\choose i}F(i)}\)

由对定理 \(2\) 关系矩阵进行转置可知。

定理 \(2,3\) 的证明可以戳这里 反演原理

定理 \(4\)： 移动定理 \(3\) 中 \(-1\) 的次幂，可得 \(\displaystyle F(n)=\sum_{i=n}{(-1)^i{n\choose i}G(i)}\Leftrightarrow G(n)=\sum_{i=n}{(-1)^i+{n\choose i}F(i)}\)

错排问题与二项式反演：

问题：设 \(a_{1\sim n}\) 是 \(1\sim n\) 的一个排列，且 \(\forall i\in (1,n),a_i\neq i\) 。

求满足条件的排列的方案数。

解：

设 \(D[n]\) 表示 \(n\) 个数的错排方案数（即满足 \(a_i\neq i\) ）。

那么有 \(n!=\sum_{i=0}^{n}{{n\choose i}D[i]}\) ，即：\(n\) 个数的全排列数 \(=\) \(\sum_{i=0}^{n}\) 选择 \(i\) 个数的错排方案数。

\(wc\)，这不就是二项式定理的标准形式吗。

二项式反演一下得到，\(\displaystyle D[n]=\sum_{i=0}^{n}{(-1)^{n-i}{\frac{n!}{(n-i)!}}}\)

\(\displaystyle \to D[n]=n!\sum_{i=0}^{n}{\frac{(-1)^i}{i!}}\)

这样，就求得了错排公式 \(\displaystyle D[n]=n!\sum_{i=0}^{n}{\frac{(-1)^i}{i!}}\)

应用

若记 \(f(n,k)\) 表示：\(n\) 个数钦定选 \(k\) 个 \(p_i=i\) ，其余的任意排列；记 \(g(n，k)\) 表示 \(n\) 个数恰好选 \(k\) 个，其余的都满足 \(a_i\neq i\)

那么对于任意的 \(f(n,k)\) 有 \(f(n,k)=\sum_{i=k}^{n}{{i\choose k}g(n,i)}\)

使用二项式反演得 \(\sum_{i=k}^{n}{}\)

在实际题目中，构造这样的 \(g\) 和 \(f\) 即可运用二项式反演解决问题。

练习题

[MtOI2018]情侣？给我烧了！ - 洛谷

题解：LuoguP4921 情侣？给我烧了