二项式反演及其运用
Godのfather
·
·
个人记录
（一）什么是反演
我们有一个数列（或者数论函数），设为g(x)。现在我们知道了这个数列与另一个数列f(x)的对应关系：
g(n)=\sum\limits_{i=0}^na_if(i)
通过这个对应关系，我们不仅能从f(x)推出g(x)，还能从g(x)反推出f(x)。这个反推的过程，就是所谓的反演了。显然，在反推的过程中，我们求解一个关于f(x)的线性方程。例如上面所给的关系式，实质上就是解一个关于f(x)的n元1次方程。
当然，如果仅仅是解线性方程，还不足以给“反演”单独取一个名字。在一些特定的关系式上，反演会化出一些优美的形式。常见的反演有莫比乌斯反演，单位根反演，子集反演，二项式反演等。
（二）容斥原理那些事
对于二项式反演，个人不喜欢网络上一些blogs直接将结论写在最前面。我认为用容斥原理引入会更加自然一些。毕竟人的认知过程是循序渐进的。
先从最基础问题引入：
求100以内，能被3或5或7整除的正整数的个数。
假设能够被3整除的数集为S_1，能够被5整除的数集为S_2，能够被7整除的数集为S_3，那么，能被3或5或7整除的正整数的个数就是|S_1\cup S_2\cup S_3|。那么，有：
|S_1\cup S_2\cup S_3|=|S_1|+|S_2|+|S_3|-|S_1\cap S_2|-|S_2\cap S_3|-|S_3\cap S_1|+|S_1\cap S_2\cap S_3|
更一般地：
\big|\bigcup\limits_{i=1}^nS_i\big|=\sum\limits_{1\leq i\leq n}|S_i|-\sum\limits_{1\leq i< j\leq n}|S_i\cap S_j|+\sum\limits_{1\leq i<j<k\leq n}|S_i\cap S_j\cap S_k|...+(-1)^{n-1}|S_1\cap S_2\cap ...\cap S_{n-1}\cap S_n|
容斥原理的核心思想十分简单，通过减去重复算的个数以得到准确的答案。
容斥原理就复习完啦。可是，二项式反演又是什么呢？容斥原理又和二项式反演有什么关系呢？
（三）二项式反演那些事
3.1从容斥原理到二项式反演
在上一节已经列出了容斥原理的一般形式，是不是感觉用数学公式表达容斥的思想很繁琐？再次将容斥简化：假设全集U=\{S_1,S_1,...,S_{n-1},S_n\}中任意i个元素的并集的大小都相等。设g(x)是任意x个集合的交集，f(x)是任意x个集合的补集的交集。特别地，g(0)=|U|,f(0)=|U|。
那么，我们会有以下两条容斥式子：
|S_1\cap S_2\cap...\cap S_{n-1}\cap S_n|=|U|-|\overline{S_1}|-|\overline{S_2}|-...+(-1)^n\times |\overline{S_1}\cap \overline{S_2}\cap...\cap\overline{S_{n-1}}\cap \overline{S_n}|=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}f(i)
|\overline{S_1}\cap\overline{ S_2}\cap...\cap \overline{S_{n-1}}\cap \overline{S_n}|=|U|-|{S_1}|-|{S_2}|-...+(-1)^n\times |{S_1}\cap {S_2}\cap...\cap{S_{n-1}}\cap {S_n}|=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}g(i)
注意到g(n)=|S_1\cap S_2\cap ...\cap S_{n-1}\cap S_n|\\f(n)=|\overline{S_1}\cap\overline{ S_2}\cap...\cap \overline{S_{n-1}}\cap \overline{S_n}|
所以，我们就得到了优美的二项式反演：
g(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}f(i)\Longleftrightarrow f(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}g(i)
做一个恒等变换，更加实用：
g(n)=\sum\limits_{i=0}^n\dbinom{n}{i}f(i)\Longleftrightarrow f(n)=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}g(i)
3.2二项式反演的代数证明
回到文章开头的公式：
g(x)=\sum\limits_{i=0}^na_if(i)
实际上，在二项式反演中，a_i=(-1)^i\dbinom{n}{i}
若g(n)=\sum\limits_{i=0}^na_if(i)\Longrightarrow f(n)=\sum\limits_{i=0}^nb_ig(i)成立，需要的条件为：
f(n)=\sum\limits_{i=0}^nb_ig(i)=\sum\limits_{i=0}^nb_i\sum\limits_{j=0}^ia_{ij}f(j) = \sum\limits_{j=0}^nf(j)\sum\limits_{i=j}^nb_ia_{ij}
显然，如果让上式成立，必须满足：
\sum\limits_{i=j}^nb_ia_{ij}=[j=n]
也就是说，现在需要的工作是证明\sum\limits_{i=j}^n(-1)^i\dbinom{n}{i}\times(-1)^j\dbinom{i}{j}=[j=n]
引理：\dbinom{n}{i}\dbinom{i}{j}=\dbinom{n}{j}\dbinom{n-j}{n-i}
引理证明1（代数）：
\dbinom{n}{i}\dbinom{i}{j}=\dfrac{n!}{(n-i)!i!}\times \dfrac{i!}{(i-j)!j!}=\dfrac{n!}{(n-j)!j!}\times\dfrac{(n-j)!}{[(n-j)-(n-i)]!(i-j)!}=\dbinom{n}{j}\dbinom{n-j}{n-i}
引理证明2（组合意义）：
考虑其组合意义：
设数集|S|=n,|A|=i,|B|=j,B\sube A\sube S，求三个集合有多少种不同的情况。
计算从S中取i个数组成集合A，再从A中取出j个数组成集合B的方案数。显然，方案数为\dbinom{n}{i}\dbinom{i}{j}。
用另一种方式计算，从S中取出j个数组成集合B，在从剩下的数中取出i-j个数组成集合A，这样的方案数就是\dbinom{n}{j}\dbinom{n-j}{i-j}。
又因为\dbinom{n-j}{n-i}=\dbinom{n-j}{i=j}，引理得证。
有了引理，接下来就简单多了：
原式=\sum\limits_{i=j}^n(-1)^{i}(-1)^j\dbinom{n}{j}\dbinom{n-j}{n-i}=\dbinom{n}{j}(-1)^j\sum\limits_{i=0}^{n-j}{(-1)}^{i+j}\dbinom{n-j}{i}=\dbinom{n}{j}(1-1)^{n-j}
显然，当j!=n的时候，原式值为0；当j=n时，代入，解得原式值为1。
所以，原式=[j=n]得证。
反之亦然。二项式反演得证。
（四）二项式反演的运用
4.1错位排列问题
这是十分经典的问题，可以从二项式反演的角度思考。
定义g_n(x)表示n个数中，至多有x个a_i\not=i的总方案数。f_n(x)表示n个数中，恰好有x个a_i\not=i的方案数（钦定x个a_i错排）。显然，g_n和f_n满足如下关系：
g_n(n)=\sum\limits_{i=0}^n\dbinom{n}{i}f_n(i)
$$
g_n(x)=x!
$$
可以通过二项式反演得到$f_n(n)$：
$f_n(n)=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}g(i) \\=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}i!\\ =\sum\limits_{i=0}^n(-1)^{n-i}\dfrac{n!}{(n-i)!}\\=n!\sum\limits_{i=0}^n\dfrac{(-1)^i}{i!}
这就是所谓的全错位排列公式：
f_n(n)=n!\sum\limits_{i=0}^n\dfrac{(-1)^i}{i!}
4.2染色问题
给定从左到右n个球，将这n个球用k种颜色染色。要求相邻两个球必须是不同的颜色，并且每种颜色恰好用一次，问有多少种染色方案。
定义g_n(x)表示n个球，至多用x种颜色染色的总方案数。f_n(x)表示n个球，恰好用x种颜色染色的方案数（钦定x种颜色）。关系式如下：
g_n(k)=\sum\limits_{i=0}^k\dbinom{k}{i}f_n(i)
$$
g_n(k)=k(k-1)^{n-1}
$$
二项式反演得到：
$f_n(k)=\sum\limits_{i=0}^{k}(-1)^{k-i}\dbinom{k}{i}g_n(i)\\=\sum\limits_{i=0}^k(-1)^{k-i}\dbinom{k}{i}i(i-1)^{n-1}
最后的结果：
f_n(k)=\sum\limits_{i=0}^k(-1)^{k-i}\dbinom{k}{i}i(i-1)^{n-1}