二项式反演的证明
摘自学长zsy的PPT。虽然没有原文链接，但为了表示对学长劳动成果的尊重，这里粘贴一个友情链接。zsy学长平时为人大方，上课生动有趣，并且对自己所讲的每个知识点都非常认真。推荐前往他的博客观摩学习。
我们都知道二项式的生成函数：
[ f(x) = (1+x)^n = sum_{k = 0}^{n}dbinom{n}{k}x^k
]
当我们带入(x=-1)时，会得到这样的式子：
[ f(-1) = (1 - 1)^n = sum_{k=0}^{n}dbinom{n}{k}(-1)^k
]
当(n=0)时，左边的部分没有意义。但右边算出来恰好为(inom{0}{0}=1)。因此我们得到了一个恒等式：
[ sum_{k=0}^{n}dbinom{n}{k}(-1)^{k} = [n = 0] = epsilon(n + 1)
]
假设我们知道(f(n) = sum_{k=0}^{n}inom{n}{k}g(k))，那么我们如何用(f(k))来表示(g(n))呢？
我们首先拼凑出一个二项式的形式：
[ g(n) = sum_{m=0}^{n}[n = m]g(m) = sum_{m=0}^{n}epsilon(n - m + 1)g(m)
]
然后代入上面那个恒等式：
[ g(n) = sum_{m=0}^{n}sum_{k=0}^{n-m}(-1)^{k}dbinom{n}{m}dbinom{n-m}{k}g(m)
]
根据组合的意义，不难得到：
[ g(n) = sum_{m=0}^{n}sum_{k=0}^{n-m}(-1)^{k}dbinom{n}{k}dbinom{n-k}{m}g(m)
]
接下来需要交换求和号。为了方便理解，我这里令(S_{mk} = (-1)^{k}dbinom{n}{k}dbinom{n-k}{m}g(m))，那么原式就变成了(sum_{m=0}^{n}sum_{k=0}^{n-m}S_{mk})。
[egin{bmatrix}
S_{0,0} & S_{0,1} & cdots & S_{0,n-1} & S_{0,n}\
S_{1,0} & S_{1,1} & cdots & S_{1,n-1}\
vdots & cdots & vdots\
S_{n -1 , 0} & S_{n-1, 1}\
S_{n,0}
end{bmatrix}
]
显然，之前的求法是一行一行，从左往右求和。我们同样以一列一列，从上往下求和。因此：
[ g(n) = sum_{k=0}^{n}sum_{m=0}^{n-k}(-1)^{k}dbinom{n}{k}dbinom{n-k}{m}g(m)
]
提出和(m)无关的系数：
[ g(n) = sum_{k=0}^{n}(-1)^k dbinom{n}{k}sum_{m=0}^{n-k}dbinom{n-k}{m}g(m)
]
注意到(sum_{m=0}^{n-k}dbinom{n-k}{m}g(m))就是(f(n-k))。因此：
[ g(n) = sum_{k=0}^{n}(-1)^kdbinom{n}{k}f(n-k)
]
把它改写成更加直观的形式：
[ g(n) = sum_{k=0}^{n}(-1)^{n-k}dbinom{n}{k}f(k)
]
这就是二项式反演了。通过它，我们可以利用二项式求和推出不好计算的答案。
说到底，反演还是和容斥脱不了干系。