序（感谢9G对本博客证明的大力支持）
前置知识
- 1：排列组合
- 2：多步容斥
证明：
\(\dbinom{n}{x-1}+\dbinom{n}{x}=\dfrac{n!}{(x-1)!*(n-x+1)!}+\dfrac{n!}{x!*(n-x)!}\)
\(=\dfrac{n!*(n-x+1)+n!*x}{x!*(n-x+1)!}=\dfrac{n!*(n+1)}{x!*(n-x+1)!}=\dbinom{n+1}{x}\)
二项式定理
公式：\((a+b)^n=\sum^{n}_{i=0} \limits\dbinom{n}{i}a^ib^{n-i}\)
证明：
\(n=1\) 时带入显然成立
我们假设 \(n=m\) 时成立，那么我们只需要用它证明 \(n=m+1\) 时成立即可
\(n=m\) 时原式子等于 \((a+b)^m=\sum^{m}_{i=0} \limits\dbinom{m}{i}a^ib^{m-i}\)
即：
\[(a+b)^{m+1}=(a+b)*(a+b)^m=a*(a+b)^m+b*(a+b)^m \]\[=a*\sum^{m}_{i=0} \limits\dbinom{m}{i}a^ib^{m-i}+b*\sum^{m}_{j=0} \limits\dbinom{m}{j}a^jb^{m-j} \]\[=\sum^{m}_{i=0} \limits\dbinom{m}{i}a^{i+1}b^{m-i}+\sum^{m}_{j=0} \limits\dbinom{m}{j}a^jb^{m-j+1} \]\[=\sum^{m-1}_{i=0} \limits\dbinom{m}{i}a^{i+1}b^{m-i}+\sum^{m}_{j=1} \limits\dbinom{m}{j}a^jb^{m-j+1}+a^{m+1}+b^{m+1} \]\[=\sum^{m}_{j=1} \limits\dbinom{m}{j-1}a^{j}b^{m-j+1}+\sum^{m}_{j=1} \limits\dbinom{m}{j}a^jb^{m-j+1}+a^{m+1}+b^{m+1} \]\[=\sum^{m}_{j=1} \limits \left[ \dbinom{m}{j}+\dbinom{m}{j-1} \right] a^{j}b^{m-j+1}+a^{m+1}+b^{m+1} \]\[=\sum^{m}_{j=1} \limits \left[ \dbinom{m+1}{j} \right] a^{j}b^{m-j+1}+a^{m+1}+b^{m+1} \]\[=\sum^{m+1}_{j=0} \limits \left[ \dbinom{m+1}{j} \right] a^{j}b^{m-j+1} \]证毕。
二项式反演
基本形式
公式：
\[f_n=\sum^{n}_{i=0} \limits (-1)^{i} \dbinom{n}{i} g_i \]\[\Updownarrow \]\[g_n=\sum^{n}_{i=0} \limits (-1)^{i} \dbinom{n}{i} f_i \]证明：
多步容斥一般形式：
\[\mid A_1\cup A_2\cup...\cup A_n\mid=\sum^{n}_{i=1} \limits \mid A_i \mid - \sum^{n}_{i=1,j=1} \limits \mid A_i \cap A_j \mid +...+(-1)^{n-1}*\mid A_1\cap A_2\cap ...\cap A_n\mid \]我们设 \(A^c_i\) 为 \(A_i\) 的补集，即有：
\[\mid A^c_1\cup A^c_2\cup...\cup A^c_n\mid=\mid U \mid-\sum^{n}_{i=1} \limits \mid A_i \mid + \sum^{n}_{i=1,j=1} \limits \mid A_i \cap A_j \mid -...+(-1)^{n}*\mid A_1\cap A_2\cap ...\cap A_n\mid \]原集的补集的补集又是原集，又有：
\[\mid A_1\cup A_2\cup...\cup A_n\mid=\mid U \mid-\sum^{n}_{i=1} \limits \mid A^c_i \mid + \sum^{n}_{i=1,j=1} \limits \mid A^c_i \cap A^c_j \mid -...+(-1)^{n}*\mid A^c_1\cap A^c_2\cap ...\cap A^c_n\mid \]我们设 \(f_n\) 表示 \(n\) 个补集的大小，\(g_n\) 表示 \(n\) 个原集的大小，那两个公式可以表示为：
\[f_n=\sum^{n}_{i=0} \limits (-1)^{i} \dbinom{n}{i} g_i \]\[g_n=\sum^{n}_{i=0} \limits (-1)^{i} \dbinom{n}{i} f_i \]常见形式
形式1：
\[f_n=\sum^{n}_{i=0} \limits \dbinom{n}{i} g_i \]\[\Updownarrow \]\[g_n=\sum^{n}_{i=0} \limits (-1)^{n-i} \dbinom{n}{i} f_i \]形式2：
\[f_k=\sum^{n}_{i=k} \limits \dbinom{i}{k} g_i \]\[\Updownarrow \]\[g_k=\sum^{n}_{i=k} \limits (-1)^{i-k} \dbinom{i}{k} f_i \]这里形式1不再予以证明，在文末的参考博客里有
证明形式2
\[\sum^{n}_{i=k} \limits (-1)^{i-k} \dbinom{i}{k} \sum^{n}_{j=i} \limits \dbinom{j}{i} g_j \]\[=\sum^{n}_{i=k} \limits \sum^{n}_{j=i} \limits (-1)^{i-k} \dbinom{i}{k} \dbinom{j}{i} g_j \]\[=\sum^{n}_{i=k} \limits \sum^{n}_{j=i} \limits (-1)^{i-k} \dbinom{j}{k} \dbinom{j-k}{j-i} g_j \]\[=\sum^{n}_{j=k} \limits \sum^{j}_{i=k} \limits (-1)^{i-k} \dbinom{j}{k} \dbinom{j-k}{j-i} g_j \]注：\(i\) 从 \(k-n\), \(j>i\) 与 \(j\) 从 \(k-n\), \(j>i>k\) 等价
当 \(j=k\) 时，原式等于 \(g_k\) ,所以我们只需要证明除了 \(j=k\) 之外的和等于 \(0\) 即可，即：
\[\sum^{n}_{j=k+1} \limits \sum^{j}_{i=k} \limits (-1)^{i-k} \dbinom{j}{k} \dbinom{j-k}{j-i} g_j=0 \]我们钦定一个 \(j\) 使 \(j\) 固定，上式剩余变量即为：
\[\sum^{j}_{i=k} \limits (-1)^{i-k} \dbinom{j-k}{j-i} g_j \]我们令 \(n=j-k\), \(n\) 为定值，\(i\) 值域从 \(k-j\) 变到 \(0-n\),即让 \(i\) 表示 \(i-k\)。
原式可化为
\[\sum^{n}_{i=0} \limits (-1)^{i} \dbinom{n}{n-i} g_j \]\[=\sum^{n}_{i=0} \limits (-1)^{i} \dbinom{n}{i} g_j \]根据二项式定理可推：
\[(-1+1)^n=\sum^{n}_{i=0} \limits \dbinom{n}{i} (-1)^{i}*(1)^{n-i}=\sum^{n}_{i=0} \limits (-1)^{i} \dbinom{n}{i}=0 \]由此可知当 \(j\) \(!=k\) 时 \(g_j\) 的系数为 \(0\)，即当且仅当 \(j=k\) 时，\(g_j\) 的系数为 \(1\),
所以对于式子：
\[\sum^{n}_{i=k} \limits (-1)^{i-k} \dbinom{i}{k} \sum^{n}_{j=i} \limits \dbinom{j}{i} g_j=g_k \]即可证明，证毕。