二项式反演似乎是个很有趣的东西~
二项式反演似乎有很多条.
第一条 (最基本, 最好记的一条): 若序列 $f$ 和 $g$ 满足:
$$g_n=\sum\limits^n_{i=0}(-1)^i{n\choose i}f_i$$
那么
$$f_n=\sum\limits^n_{i=0}(-1)^i{n\choose i}g_i$$
反过来也成立.
证明:(公式恐惧症者可以跳过)
第一个式子代入第二个式子:
$$f_n=\sum\limits^n_{i=0}(-1)^i{n\choose i}\sum\limits^i_{j=0}(-1)^j{i\choose j}f_j$$
全部放到后面:
$$f_n=\sum\limits^n_{i=0}\sum\limits^i_{j=0}(-1)^{i+j}{n\choose i}{i\choose j}f_j$$
拆开:
- $$f_n=\sum\limits^n_{
- i=0
- }\sum\limits^i_{
- j=0
- }(-1)^{
- i+j
- }\frac{
- n!
- }{
- i!(n-i)!
- }\frac{
- i!
- }{
- j!(i-j)!
- }f_j$$
- $$f_n=\sum\limits^n_{
- i=0
- }\sum\limits^i_{
- j=0
- }(-1)^{
- i+j
- }\frac{
- n!
- }{
- (n-i)!j!(i-j)!
- }f_j$$
- $$f_n=\sum\limits^n_{
- i=0
- }\sum\limits^i_{
- j=0
- }(-1)^{
- i+j
- }\frac{
- n!
- }{
- (n-j)!j!
- }\frac{
- (n-j)!
- }{
- (n-i)!(i-j)!
- }f_j$$
- $$f_n=\sum\limits^n_{
- i=0
- }\sum\limits^i_{
- j=0
- }(-1)^{
- i+j
- }\frac{
- n!
- }{
- (n-j)!j!
- }\frac{
- (n-j)!
- }{
- (n-i)!((n-j)-(n-i))!
- }f_j$$
- $$f_n=\sum\limits^n_{
- i=0
- }\sum\limits^i_{
- j=0
- }(-1)^{
- i+j
- }{
- n\choose j
- }{
- n-j\choose n-i
- }f_j$$
改变枚举顺序:
$$f_n=\sum\limits^n_{j=0}\sum\limits^n_{i=j}(-1)^{i+j}{n\choose j}{n-j\choose n-i}f_j$$
跟 $i$ 无关的提出去:
$$f_n=\sum\limits^n_{j=0}(-1)^j{n\choose j}f_j\sum\limits^n_{i=j}(-1)^i{n-j\choose n-i}$$
枚举 $i$ 改为枚举 $i+j$:
- $$f_n=\sum\limits^n_{
- j=0
- }(-1)^j{
- n\choose j
- }f_j\sum\limits^{
- n-j
- }_{
- i=0
- }(-1)^{
- i+j
- }{
- n-j\choose n-(i+j)
- }$$
- $$f_n=\sum\limits^n_{
- j=0
- }(-1)^{
- 2j
- }{
- n\choose j
- }f_j\sum\limits^{
- n-j
- }_{
- i=0
- }(-1)^i{
- n-j\choose n-j-i
- }$$
前面,$(-1)^{2j}$ 一定是 $1$, 可以省略; 后面, 可以添上 $1^{n-j-i}$, 式子不变.
$$f_n=\sum\limits^n_{j=0}{n\choose j}f_j\sum\limits^{n-j}_{i=0}(-1)^i1^{n-j-i}{n-j\choose n-j-i}$$
后面用二项式定理:
$$f_n=\sum\limits^n_{j=0}{n\choose j}f_j(-1+1)^{n-j}$$
根据 $0^n=[n=0]$:
$$f_n=\sum\limits^n_{j=0}{n\choose j}f_j[n=j]$$
有用的只有 $n=j$:
$$f_n={n\choose n}f_n$$
得证.(似乎网上没有这个式子的证明, 我仿照了别的证明才死磕出来的 Q^Q)
然而这个式子不是很常用.
第二条 (最常用的一条): 若序列 $f$ 和 $g$ 满足:
$$g_n=\sum^n_{i=0}{n\choose i}f_i$$
那么
$$f_n=\sum^n_{i=0}(-1)^{n-i}{n\choose i}g_i$$
反过来也成立.
证明:(公式恐惧症者可以跳过)
第一个式子代入第二个式子:
$$f_n=\sum\limits^n_{i=0}(-1)^{n-i}{n\choose i}\sum\limits^i_{j=0}{i\choose j}f_j$$
全部放到后面:
$$f_n=\sum\limits^n_{i=0}\sum\limits^i_{j=0}(-1)^{n-i}{n\choose i}{i\choose j}f_j$$
拆开, 同上可得:
$$f_n=\sum\limits^n_{i=0}\sum\limits^i_{j=0}(-1)^{n-i}{n\choose j}{n-j\choose n-i}f_j$$
改变枚举顺序:
$$f_n=\sum\limits^n_{j=0}\sum\limits^n_{i=j}(-1)^{n-i}{n\choose j}{n-j\choose n-i}f_j$$
跟 $i$ 无关的提出去:
$$f_n=\sum\limits^n_{j=0}{n\choose j}f_j\sum\limits^n_{i=j}(-1)^{n-i}{n-j\choose n-i}$$
枚举 $i$ 改为枚举 $n-i$:
$$f_n=\sum\limits^n_{j=0}{n\choose j}f_j\sum\limits^{n-j}_{i=0}(-1)^i{n-j\choose i}$$
后面, 可以添上 $1^{n-j-i}$, 式子不变.
$$f_n=\sum\limits^n_{j=0}{n\choose j}f_j\sum\limits^{n-j}_{i=0}(-1)^i1^{n-j-i}{n-j\choose i}$$
后面用二项式定理:
$$f_n=\sum\limits^n_{j=0}{n\choose j}f_j(-1+1)^{n-j}$$
根据 $0^n=[n=0]$:
$$f_n=\sum\limits^n_{j=0}{n\choose j}f_j[n=j]$$
有用的只有 $n=j$:
$$f_n={n\choose n}f_n$$
得证. 实际上上面这两条和下面将提到的两条证明过程都十分相似, 我就不赘述了.
第三条 (比较冷门的一条): 若序列 $f$ 和 $g$ 满足:
$$g_k=\sum^n_{i=k}(-1)^i{i\choose k}f_i$$
那么
$$f_k=\sum^n_{i=k}(-1)^i{i\choose k}g_i$$
反过来也成立.
第四条 (比较常用的一条): 若序列 $f$ 和 $g$ 满足:
$$g_k=\sum^n_{i=k}{i\choose k}f_i$$
那么
$$f_k=\sum^n_{i=k}(-1)^{i-k}{i\choose k}g_i$$
反过来也成立.
二项式定理主要用来解决一些形如 "恰好" 的这类计数问题. 通常恰好的方案数不好算, 但是至多或者至少的方案比较好算, 就可以用二项式反演.
那么来几道例题:
Color:UVAlive-7040 https://vjudge.net/problem/UVALive-7040 (题解 https://www.cnblogs.com/1000Suns/p/10353695.html )
已经没什么好害怕的了: 洛谷 4859 https://www.luogu.org/problemnew/show/P4859 ,BZOJ3622(Todo)
(欢迎 dalao 们帮忙找更多的例题, 谢谢 OvO)
来源: http://www.bubuko.com/infodetail-2946003.html