二项式反演学习笔记

2024-06-13 04:40| 来源: 网络整理| 查看: 265

二项式反演学习笔记

目录二项式反演学习笔记基本定理标准形式容斥解释代数解释至多和恰好的转化至少和恰好的转化*广义的反演应用形式2(至多)的应用错排问题min-max容斥形式3(至少)的应用

二项式反演(Binomial Inversion)是一种反演,它基于容斥原理.它可以把计数问题中求解"恰好X个的方案数"转化为求解"至少X个的方案数",让问题变得更简单。

约定:

$C_n^m$表示从$n$个数里选$m$个数的方案数,等价于$\binom{m}{n}$.另外为了方便推式子,规定$n=j$的$(-1)^iC_n^i$更新。那么这样只需要后面的和式在$j \neq n$时为0,$j=n$时为1,那么总和就为$g_n$

接下来需要用到组合数的性质

\[\begin{aligned} C_n^i C_j^i &=\frac{n!}{(n-i)!i!}\frac{i!}{(i-j)!j!} \\ &=\frac{n!}{(n-i)!(i-j)!j!} \\ &=\frac{n!(n-j)!}{j!(n-j)!(n-i)!(i-j)!} \ \ (\text{ 为了构造组合数，上下同乘}(n-j)!) \\ &=\frac{n!}{j!(n-j)!} \frac{(n-j)!}{(n-i)![(n-i)-(n-j)]!} \\ &= C_n^j C_{n-j}^{n-i} (1.1.2)\end{aligned} \]

代回上式

\[\begin{aligned} \sum_{i=j}^n (-1)^{i+j}C_{n}^i C_{i}^j &=(-1)^jC_n^j \sum_{i=j}^n (-1)^i C_{n-j}^{n-i} \\ &=(-1)^jC_n^j \sum_{i=0}^{n-j} (-1)^{n-i} C_{n-j}^{i} \ \ (\text{把}i\text{换成}n-i) \\ &= (-1)^jC_n^j (1-1)^{n-j} \ \ (\text{二项式定理})\end{aligned} \]

当$n \neq j$时$\text{原式}=0$ 当$n = j$时出现了$0^0$无法直接算,考虑直接用原式(因为最后一步转化破坏了等价性),$\sum_{i=j}^n (-1)^{i+j}C_{n}^i C_{i}^j=\sum_{i=n}^n (-1)^{i+n}C_{n}^n C_{i}^n=(-1)^{2n}C_n^nC_n^n=1$ 因此$\text{原式}=[n=j]$ 也就是说

\[\begin{aligned}\sum_{i=0}^n (-1)^i C_n^i f_i =\sum_{j=0}^n g_j [n=j]=g_n\end{aligned} \]

至多和恰好的转化

定理2(二项式反演形式2):$$f_n = \sum_{i=0}^n C_n^i g_i \Leftrightarrow g_n = \sum_{i=0}^n (-1)^{n-i} C_n^i f_i \ \ \tag{1.2}$$

这个式子的意义是,$f_n$表示至多$n$个的方案数,那么$g_n$就表示恰好$n$个的方案数。

证明: 考虑形式1

\[f_n = \sum_{i=0}^n (-1)^i C_n^i g_i \Leftrightarrow g_n = \sum_{i=0}^n (-1)^i C_n^i f_i \]

令$g'_i=(-1)^{-i} g_i,那么f_n= \sum_{i=0}^n (-1)^i C_n^i g'_i$ 那么$g'_n = \sum_{i=0}^n (-1)^i C_n^i f_i$ 即$(-1)^{-n}g_n=\sum_{i=0}^n (-1)^i C_n^i f_i$ 两边同乘$(-1)^{-2n}=1$,得到$g_n=\sum_{i=0}^n (-1)^{i-n} C_n^i f_i=\sum_{i=0}^n (-1)^{n-i} C_n^i \ (\forall x \in \mathbb{Z},(-1){-x}=(-1)(-1){-x}=(-1)x)$

至少和恰好的转化

这是最常见的二项式反演形式，一定要掌握!

定理3(二项式反演形式3):$$f_n = \sum_{i=n}^m C_i^n g_i \Leftrightarrow g_n = \sum_{i=n}^m (-1)^{i-n} C_i^n f_i \ \ \tag{1.3}$$ 对于$\forall m \geq n$,结论都成立,即使是一个无限求和也可以

这个式子的意义是,$f_n$表示 "至少" $n$个的方案数,那么$g_n$就表示恰好$n$个的方案数.这里的 "至少"打引号是因为它不是一个简单的后缀和,它表示我们"钦定"$n$个数满足条件,剩下的数不一定满足条件求$f$的时候每个$g_i$是会被重复计算的，计算了$C_n^i$次.

证明:

\[\begin{aligned} \sum_{i=n}^m (-1)^{i-n} C_i^n f_i &= \sum_{i=n}^m (-1)^{i-n} C_i^n \sum_{j=i}^m C_j^i f_j\end{aligned} \]

同$(1.1)$的证明,交换求和顺序

\[\begin{aligned} \text{原式} &= \sum_{j=n}^m f_j \sum_{i=n}^j (-1)^{i-n} C_{j}^i C_i^n\end{aligned} \]

注意到后面的$\sum_{i=n}^j (-1)^{i-n} C_{j}^i C_i^n$部分也很相似,因此可以用类似的方法处理。代入组合数的性质$(1.1.2）$

\[\begin{aligned} \sum_{i=n}^j (-1)^{i-n} C_{j}^i C_i^n &= \sum_{i=n}^k C_j^n C_{j-n}^{j-i} \\ &= (-1)^{-n}C_n^j \sum_{i=n}^j (-1)^i C_{j-n}^{j-i} \\ &= (-1)^{-n}C_n^j \sum_{i=0}^{j-n} (-1)^{j-i} C_{j-n}^{i} \\ &= (-1)^{-n}C_n^j (1-1)^{j-n} \\&=[n=j] \end{aligned} \]

容易发现这个证明过程只是把原来的$n-j$换成$j-n$而已。

*广义的反演

我们发现形式$1$和形式$3$的证明有相似之处,都是交换求和顺序然后提取出和式,证明它等于$[n=k]$. 我们不妨将这个方法推广到任意序列。

定理4 命题$$f_n = \sum_{i=0}^n a_{n,i} g_i \Leftrightarrow g_n = \sum_{i=0}^n b_{n,i} f_i $$成立的充要条件是

\[\forall i \in \mathbb{N},\sum_{j=i}^n b_{n,j}a_{j,i}=[n=i] \]

证明: 还是交换求和顺序

\[\sum_{i=0}^n b_{n,i} f_i=\sum_{i=0}^n b_{n,i} \sum_{j=0}^i a_{i,j}g_j=\sum_{j=1}^n g_j \sum_{i=j}^n b_{n,j} a_{i,j} \]

把字母换一下就得到了上面的定理

应用

在做题中,看到求"恰好X"的方案数,就要敏感的想到二项式反演。

形式1几乎没有什么用

形式2(至多)的应用错排问题

求错排问题的通项公式: 若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 $n$个元素的错排数记为$D_n$

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

其实可以把$D_n$看成不在原来位置上的元素有$n$个的排列数。设$f_n$表示长度为n的排列,在原来位置上的元素至多有$n$个的排列数,显然所有排列都满足这个性质,即$f_n=n!$

那么

\[\begin{aligned} \sum_{i=0}^n (-1)^{n-i} C_n^i f_i &= \sum_{i=0}^n (-1)^{n-i} \frac{n!}{i!(n-i)!}i! \\ &=\sum{i=0}^n n! \frac{(-1)^{n-i}}{(n-i)!} \\ &= n!\sum_{i=0}^n \frac{(-1)^i}{i!}\end{aligned} \]

min-max容斥

设$S$为一个集合,$\max(S),\min(S)$分别表示集合中的最大值和最小值。特别地,规定$\max(\emptyset)=\min(\emptyset)=0$,则$$\max(S)=\sum_{T\subset S}(-1)^{|T|-1} \min(T)$$

证明: 设存在一个以集合大小为自变量的函数$f$满足

\[\max(S)=\sum_{T\subset S}f(|T|) \min(T) \]

记$S$中元素从大到小分别为$a_1,a_2 \dots a_{|S|}$. 那么$a_i$对等式左边的贡献是$[i=1]$,因为$a_1=\max(S)$. $a_i$对等式右边的贡献为$\sum_{j=0}^{i-1}C_{i-1}^j f(j+1)$. 这是因为要$i$成为大小为$j+1$的集合的集合中的最小值,就要从$a_1,a_2 \dots a_{i-1}$这些比$i$大的数中选出$j$个,再加上$a_i$构成一个集合。

那么为了等式成立,左右的贡献应该两两抵消,只剩下$a_1$.所以必有

\[[i=1]=\sum_{j=0}^{i-1}C_{i-1}^j f(j+1) \]

构造函数$A(x)=[x=0]$,那么$A(x-1)=[x=1]$. 注意到右边有$f(j+1)$,不方便反演,不妨令$B(x)=f(x+1)$

那么$A(i)=\sum_{j=0}^i C_i^j B(j)$ 反演得到$B(i)=\sum_{j=0}^i (-1)^{n-j} C_i^jA(j)=\sum_{j=0}^i (-1)^{n-j} C_i^j[j=0]=(-1)^{i}$

所以$f(x)=B(x-1)=(-1)^{x-1}$,代回原式,得

\[\max(S)=\sum_{T\subset S}(-1)^{|T|-1} \min(T) \]

min-max容斥有许多应用,这里不再赘述。

形式3(至少)的应用

由于形式3的$f$定义是可以有重复计数的,因此它会比"恰好"的形式好求,因为不需要考虑计数时的一些判重问题。这也给求$f$的过程(如直接数学计算/DP)提供了方便。

[BZOJ2839] 集合计数一个有N个元素的集合有$2^N$个不同子集（包含空集），现在要在这$2^N$个集合中取出若干集合（至少一个），使得它们的交集的元素个数为K，求取法的方案数，答案模1000000007。

设$f_i$表示交集的元素个数 "至少" 为$i$的方案数。那么我们可以从$n$个元素中选出$i$个钦定为交集。剩下的$n-i$个元素组成$2^{n-i}$个包含空集的集合。从这些集合中任意选一些集合并上那$i$个数,它们的交集一定是这$i$个数。因此

\[f_i=C_n^i (2^{2^{n-i}}-1) \]

根据二项式反演,答案为

\[\sum_{i=k}^n (-1)^{i-k}C_{i}^kf_i \]

注意$2^{2^{n-i}}$无法快速幂,只需要递推求即可。因为$2^{2^i}=2^{2^{i-1}} \cdot2^{2^{i-1}}$

#include #include #include #include #define mod 1000000007 #define maxn 1000000 using namespace std; typedef long long ll; inline ll fast_pow(ll x,ll k){ ll ans=1; while(k){ if(k&1) ans=ans*x%mod; x=x*x%mod; k>>=1; } return ans; } inline ll inv(ll x){ return fast_pow(x,mod-2); } ll fact[maxn+5],invfact[maxn+5]; void ini(int n){ fact[0]=1; for(int i=1;i=0;i--) invfact[i]=invfact[i+1]*(i+1)%mod; } ll C(int n,int m){ return fact[n]*invfact[n-m]%mod*invfact[m]%mod; } int n,k; ll f[maxn+5],g[maxn+5]; int main(){ scanf("%d %d",&n,&k); ini(n); ll pw=2;//2^(2^(n-i)),无法快速幂计算,只能递推 for(int i=n;i>=0;i--){ f[i]=C(n,i)*(pw-1)%mod; pw=pw*pw%mod; } ll ans=0; for(int i=k;ib_y\)的配对数比$a_xb$的个数有$\frac{n+k}{2}$

设$f(i)$表示保证(钦定)有$i$对$a>b$,其余不一定。$g(i)$表示恰好$i$对a>b.显然$f(i)=\sum_{j=i}^m C_j^i g(j)$,根据二项式反演定理$g(i)=\sum_{j=i}^m C_{j}^i f(j)$

考虑如何求$f$.把$a$从小到大排序,记$cnt(i)$表示$b$中小于$a_i$的数的个数。设$dp_{i,j}$为$a$序列的前$i$个,保证有$j$对$a>b$的方案数,则$f_i=dp_{n,i}(n-i)!$

容易写出转移方程： $dp_{i,j}=dp_{i,j-1}+dp_{i-1,j-1}\cdot (cnt(i)-(j-1))$

我们按$a$排序,因此$b$中小于$a_i$的数的集合一定包含$b$中小于$a_{i-1}$的数的集合.之前已经选了$j-1$个数,那只能选剩下的$cnt(i)-(j-1)$个数来使得$a_i>b_x$,这样对数会增加1。

#include #include #include #include #define mod 1000000009 #define maxn 2000 using namespace std; typedef long long ll; inline ll fast_pow(ll x,ll k){ ll ans=1; while(k){ if(k&1) ans=ans*x%mod; x=x*x%mod; k>>=1; } return ans; } inline ll inv(ll x){ return fast_pow(x,mod-2); } ll fact[maxn+5],invfact[maxn+5]; void ini(int n){ fact[0]=1; for(int i=1;i=0;i--) invfact[i]=invfact[i+1]*(i+1)%mod; } ll C(int n,int m){ return fact[n]*invfact[n-m]%mod*invfact[m]%mod; } int n,k; int a[maxn+5],b[maxn+5]; int cnt[maxn+5];//a从小到大排序后,a[i]>b[j]的j的数量 ll dp[maxn+5][maxn+5]; ll f[maxn+5],g[maxn+5]; void calc_inv(ll *f,ll *g,int n){ for(int i=0;i

【本文地址】

公司简介

联系我们