二项式反演学习笔记

二项式反演在需要容斥问题的中经常出现，也是很多知识的基础。

引入

首先设 $A_1,A_2,\dots,A_n$ 是 $n$ 个集合，那么有：

$|A_i\cup A_2\cup\dots\cup A_n|=\left(\sum\limits_{1\le i\le n}|A_i|\right)-\left(\sum\limits_{1\le i<j\le n}|A_i\cap A_j|\right)+\left(\sum\limits_{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|\right)-\dots+(-1)^{n-1}\times|A_1\cap A_2\cap\dots\cap A_n|$

这其实很好理解，就是减掉算重一次的，加上算重两次的，减掉算重三次的……

变形一下，有：（$A_i^c$ 是 $A_i$ 的补集，$S$ 是全集）

$|A_i^c\cap A_2^c\cap\dots\cap A_n^c|=|S|-\left(\sum\limits_{1\le i\le n}|A_i|\right)+\left(\sum\limits_{1\le i<j\le n}|A_i\cap A_j|\right)-\left(\sum\limits_{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|\right)+\dots+(-1)^n\times|A_1\cap A_2\cap\dots\cap A_n|$

由于补集的补集是原集，所以有：

$|A_i\cap A_2\cap\dots\cap A_n|=|S|-\left(\sum\limits_{1\le i\le n}|A_i^c|\right)+\left(\sum\limits_{1\le i<j\le n}|A_i^c\cap A_j^c|\right)-\left(\sum\limits_{1\le i<j<k\le n}|A_i^c\cap A_j^c\cap A_k^c|\right)+\dots+(-1)^n\times|A_1^c\cap A_2^c\cap\dots\cap A_n^c|$

考虑一种特殊情况，集合的交集大小之和集合个数有关。设 $f(n)$ 表示 $n$ 个集合的补集的交集大小，$g(n)$ 表示 $n$ 个集合的交集大小，那么上面两条式子可以写成：

$f(n)=\sum\limits_{i=0}^n(-1)^i\binom{n}{i}g(i)$

$g(n)=\sum\limits_{i=0}^n(-1)^i\binom{n}{i}f(i)$

所以这两条式子是等价的关系，那么有：

$f(n)=\sum\limits_{i=0}^n(-1)^i\binom{n}{i}g(i)\iff g(n)=\sum\limits_{i=0}^n(-1)^i\binom{n}{i}f(i)$

这就是二项式反演的形式一。

更多形式

形式二

$f(n)=\sum\limits_{i=0}^n\dbinom{n}{i}g(i)\iff g(n)=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}f(i)$

证明：

令 $h(n)=(-1)^n g(n)$，那么带入形式一有 $f(n)=\sum\limits_{i=0}^n\binom{n}{i}h(i)\iff \frac{h(n)}{(-1)^n}=g(n)=\sum\limits_{i=0}^n(-1)^i\binom{n}{i}f(i)$，整理后即得证。

形式三

$f(n)=\sum\limits_{i=n}^m\binom{i}{n}g(i)\iff g(n)=\sum\limits_{i=n}^m(-1)^{i-n}\binom{i}{n}f(i)$

证明：

组合意义是 $f(n)$ 表示钦定 $n$ 个选，$g(n)$ 表示恰好选 $n$ 个。因为 $f(n)$ 同一种方案会计算多次，具体的，选 $n$ 个的方案钦定选 $i$ 个就会重复计算 $\binom{n}{i}$ 次，所以 $f(n)=\sum\limits_{i=n}^m\binom{i}{n}g(i)$。而

$\begin{aligned} g(n)&=\sum\limits_{i=n}^m(-1)^{i-n}\binom{i}{n}f(i)\\ &=\sum\limits_{i=n}^m(-1)^{i-n}\binom{i}{n}\sum\limits_{j=i}^m\binom{j}{i}g(j)\\ &=\sum\limits_{j=n}^mg(j)\sum\limits_{i=n}^j(-1)^{i-n}\binom{i}{n}\binom{j}{i}\\ &=\sum\limits_{j=n}^mg(j)\sum\limits_{i=n}^j(-1)^{i-n}\frac{i!}{n!(i-n)!}\frac{j!}{i!(j-i)!}\\ &=\sum\limits_{j=n}^mg(j)\sum\limits_{i=n}^j(-1)^{i-n}\frac{j!}{n!(i-n)!(j-i)!}\\ &=\sum\limits_{j=n}^mg(j)\sum\limits_{i=n}^j(-1)^{i-n}\frac{j!(j-n)!}{n!(i-n)!(j-i)!(j-n)!}\\ &=\sum\limits_{j=n}^m\binom{j}{n}g(j)\sum\limits_{i=n}^j(-1)^{i-n}\binom{j-n}{i-n}\\ &=\sum\limits_{j=n}^m\binom{j}{n}g(j)\sum\limits_{i=0}^{j-n}(-1)^{i}\binom{j-n}{i}\\ &=\sum\limits_{j=n}^m\binom{j}{n}g(j)(1-1)^{j-n}\\ &=\sum\limits_{j=n}^m\binom{j}{n}g(j)[j==n]\\ &=\binom{n}{n}g(n)\\ &=g(n)\\ \end{aligned}$

所以得证。

例题

bzoj 2839 集合计数

设 $f(i)$ 表示钦定交集有 $i$ 个的方案数，$g(i)$ 表示交集恰好有 $i$ 个的方案数，那么有 $f(i)=\binom{n}{i}(2^{2^{n-i}}-1)$，$f(i)=\sum\limits_{j=i}^n\binom{j}{i}g(j)$，反演一下得到 $g(i)=\sum\limits_{j=i}^n(-1)^{j-i}\binom{j}{i}f(j)$，由于只要算一次，所以直接算就行了。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=1000005,p=1000000007;

int fra[S],inv[S];
int n,k;
int f[S];

inline int qpow(int x,int y,int p)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=(y&1)?1ll*res*x%p:res;
	return res;
}

inline int C(int n,int m)
{
	return 1ll*fra[n]*inv[n-m]%p*inv[m]%p;
}

int main()
{
	fra[0]=1;
	for(int i=1;i<=S-3;i++) fra[i]=1ll*fra[i-1]*i%p;
	inv[S-3]=qpow(fra[S-3],p-2,p);
	for(int i=S-3;i>=1;i--) inv[i-1]=1ll*inv[i]*i%p;
	scanf("%d%d",&n,&k);
	for(int i=0;i<=n;i++) f[i]=1ll*C(n,i)*((long long)qpow(2,qpow(2,n-i,p-1),p)-1+p)%p;
	int ans=0;
	for(int i=k;i<=n;i++)
	{
		int pre=1ll*C(i,k)*f[i]%p;
		if(i-k&1) ans=(ans-pre+p)%p;
		else ans=(ans+pre)%p;
	}
	printf("%d\n",ans);
	return 0;
}

习题

• P4859 已经没有什么好害怕的了

• P5505 [JSOI2011]分特产