反演
\[f_n=\sum\limits_{i=0}^{n}(-1)^i\dbinom{n}{i}g_i \iff g_n=\sum\limits_{i=0}^{n}(-1)^i\dbinom{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
\]
证明
把第一个形式中的右侧\(g_n\)代入左侧的式子
\[f_n=\sum\limits_{i=0}^{n}(-1)^i\dbinom{n}{i}\sum\limits_{j=0}^{i}(-1)^j\dbinom{i}{j}f_j
\]
\[=\sum\limits_{j=0}^{n}f_j\sum\limits_{i=j}^{n}(-1)^{i+j}\dbinom{n}{i}\dbinom{i}{j}
\]
\[=\sum\limits_{j=0}^{n}f_j\sum\limits_{i=j}^{n}(-1)^{i+j}\dbinom{n}{j}\dbinom{n-j}{n-i}
\]
组合数的变化可以理解为原本是从\(n\)个中选\(i\)个，再从\(i\)个中选\(j\)个 变为 先从\(n\)个中选\(j\)个，再从剩下的里面选\(n-i\)个
\[=\sum\limits_{j=0}^{n}f_j\dbinom{n}{j}(-1)^j\sum\limits_{i=j}^{n}(-1)^i\dbinom{n-j}{n-i}
\]
\[=\sum\limits_{j=0}^{n}f_j\dbinom{n}{j}(-1)^j\sum\limits_{i=0}^{n-j}(-1)^{n-i}\dbinom{n-j}{i}
\]
可以发现后面是二项式定理的形式
\[=\sum\limits_{j=0}^{n}f_j\dbinom{n}{j}(-1)^j(1-1)^{n-j}
\]
\[=f_n
\]
例题
已经没有什么好害怕的了
题目大意：\(a_i\)与\(b_i\)一一配对，使得\(a_i>b_i\)的数量恰好为\(\frac{n+k}{2}\)的方案数
设\(pos_i=\sum\limits_{i=1}^{n}[a_i>b_i]\)
设\(f[i][j]\)为前\(i\)个\(a\)，选了\(j\)组\(a>b\)的方案数
得到\(dp\)方程：\(f[i][j]=f[i-1][j]+(pos[i]-j+1)*f[i-1][j-1]\)
设\(g_i=f[n][i]*(n-i)!\)，\(f_i\)为恰好有\(i\)对\(a>b\)的方案数
根据我个人理解，\(g_i\)并不是至少有\(i\)对\(a>b\)的方案数，而是选出\(i\)对\(a>b\)的方案之后，其他数据随意排列的方案数，显然第二种解释的方案数应该多于第一种，因为会有大量重复情况
那么有
\[g_k=\sum\limits_{i=k}^{n}\dbinom{i}{k}f_i
\]
根据二项式反演得到
\[f_k=\sum\limits_{i=k}^{n}(-1)^{i-k}\dbinom{i}{k}g_i
\]
二项式反演
原文：https://www.cnblogs.com/knife-rose/p/13042516.html
