前置知识：
1.排列组合
2.多步容斥
二项式定理：
公式
\((a+b)^n=\sum^{n}_{i=0}C_n^ia^ib^{n-i}\)
证明：
n=1时代入显然成立
设n=m时该式子成立在证明n=m+1时该式子成立就可以推得该式子成立。
n=m代入得到
\((a+b)^m=\sum^{m}_{i=0}C_m^ia^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}C_m^ia^ib^{m-i}+b\sum^{m}_{j=0}C_m^ja^ib^{m-j}\)
=\(\sum^{m}_{i=0}C_m^ia^{i+1}b^{m-i}+\sum^{m}_{j=0}C_m^ja^{j}b^{m-j+1}\)
=\(a^{m+1}+\sum^{m-1}_{i=0}C_m^ia^{i+1}b^{m-i}+b^{m+1}+\sum^{m}_{j=1}C_m^ja^{j}b^{m-j+1}\)
//当\(i=m,C_m^ma^{m+1}b^0=a^{m+1},j=0,C_m^0a^0b^{m+1}=b^{m+1}\)
=\(a^{m+1}+\sum^{m}_{j=1}C_m^{j-1}a^{j}b^{m-j+1}+b^{m+1}+\sum^{m}_{j=1}C_m^ja^{j}b^{m-j+1}\)
//用j表示i
=\(a^{m+1}\sum^{m}_{j=1}(C_m^{j-1}+C_m^j)a^jb^{m-j+1}+b^{m+1}\)
=\(a^{m+1}\sum^{m}_{j=1}(C_{m+1}^j)a^jb^{m-j+1}+b^{m+1}\)
//证明\(C_m^{j-1}+C_m^j=C_{m+1}^j\)
//\(C_m^{j-1}+C_m^j={m! \over (j-1)!(m-j+1)!}+{m! \over j!(m-j)!}\)
//\(={(m-j+1)m!+m!j \over (j)!(m-j+1)!}\)
//\(={(m+1)m!\over (j)!(m-j+1)!}\)
//\(=C_m+1^j\)
=\(\sum^{m+1}_{j=0}(C_{m+1}^j)a^jb^{m-j+1}\)
//当\(j=0,C_{m+1}^0a^0b^{m+1}=b^{m+1},j=m+1,C_{m+1}^{m+1}a^{m+1}b^0=a^{m+1}\)
显然证明得到二项式定理成立
然后我们再来推二项式反演：
二项式反演
基本形式(形式0）：
公式
\(f_n=\sum^{n}_{i=0}(-1)^iC_{n}^ig_i\)
\(\Updownarrow\)
\(g_n=\sum^{n}_{i=0}(-1)^iC_{n}^if_i\)
证明形式0：
前置知识：多步容斥
多步容斥一般形式：
\(|A_1 \cap A_2 \cap A_3 \cap …\cap A_n|\)
\(=\sum^{n}_{i=1} |A_i|-\sum^{n}_{i=1,j=1} |A_i \cap A_j|+…+(-1)^{n-1}*|A_1 \cap A_2 \cap … \cap A_n|\)
我们设\(A_i^c\)表示\(A_i\)的补集，将多步容斥一般形式变形，可得：
\(|A_i^c \cap A_2^c \cap … \cap A_n^c|=\)
\(|S|-\sum^n_{i=1} |A_i| +\sum^n_{i=1,j=1} |A_i \cap A_j|-…+(-1)^n*|A_1 \cap A_2 \cap … \cap A_n|\)
由于补集的补集就是原集，所以又有了
\(|A_i \cap A_2 \cap … \cap A_n|=\)
\(|S|-\sum^n_{i=1} |A_i^c| +\sum^n_{i=1,j=1} |A_i^c \cap A_j^c|-…+(-1)^n*|A_1^c \cap A_2^c \cap … \cap A_n^c|\)
那么我们\(f_n\)表示n个补集的交际大小，\(g_n\)表示n个原集的大小，两个公式分别可以写成：
\(f_n=\sum^{n}_{i=0}(-1)^iC_{n}^i g_i\)
\(g_n=\sum^{n}_{i=0}(-1)^iC_{n}^if_i\)
两公式是相互推导的关系，所以这就是二项式反演的形式0
常见形式（形式1）：
公式
\(f_n=\sum^{n}_{i=0}C_{n}^ig_i\)
\(\Updownarrow\)
\(g_n=\sum^{n}_{i=0}(-1)^{n-i}C_{n}^if_i\)
证明形式1：
已知\(f_n=\sum^{n}_{i=0}C_n^ig_i\)
我们使\(g_i\)是\(g_j\),\(n\)就是\(i\)
那么
\(\sum^{n}_{i=0}(-1)^{n-i}C_n^if_i=\)
\(\sum^{n}_{i=0}(-1)^{n-i}C_n^i\sum^{i}_{j=0}C_i^jg_j\)
=\(\sum^{n}_{i=0}\sum^{i}_{j=0}(-1)^{n-i}C_n^iC_i^jg_j\)
=\(\sum^{n}_{i=0}\sum^{i}_{j=0}(-1)^{n-i}C_n^jC_{n-j}^{i-j}g_j\)
//\(C_n^m\)X\(C_m^s\)=\(C_n^s\) X \(C_{n-s}^{n-m}\)
//再将\(n\)和\(i\)该替换的替换
=\(\sum^{n}_{j=0}\sum^{n}_{i=j}(-1)^{n-i}C_n^jC_{n-j}^{i-j}g_j\)
//我们把j放在前面
//对于两个大sigma\(\sum^{n}_{i=0}\sum^{i}_{j=0}\)来说，他代表\(i \in [0,n],i>=j\)的情况。
//其实和\(j \in [0,n],i>=j\)的所有情况。
//呃呃其实到这里的时候我也是有点懵，建议在这里琢磨琢磨。
//其实\(i 和 j\)的范围都没变对吧。
对于\(j=n\)时\(\sum^{n}_{i=j}(-1)^{n-i}C_n^jC_{n-j}^{i-j}g_j\)的值时\(g_n\)
对于\(j!=n\)时，考虑\(g_j\)的系数
我们先固定一个\(j\)，那么\(C_n^j\)作为一个常数，删去
\(\sum^{n}_{i=j}(-1)^{n-i}C_{n-j}^{i-j}\)
然后n-j也是常数,设m=n-j
并将i向左平移，使得范围\(\in [j,n]\)变为$ \in[0,m]$ ,或者理解成\(i\)代表\(i-j\)
那么系数就是
\(\sum^{m}_{i=0}(-1)^{m-i}C_{m}^{i}\)
啊啊啊，这个式子……
是……是不能忘记的式子！
刚刚我们推导的二项式定理：
\((a+b)^n=\sum^{n}_{i=0}C_n^ia^ib^{n-i}\)
我们让\(a=1,b=-1,n=m\)
就有了
\(0=\sum^{m}_{i=0}C_m^i(-1)^{m-i}\)
\(g_j\)的系数就等于0啊！
那么仅\(j=n\)时\(g_j\)系数和为1
那么对于：
\(\sum^{n}_{j=0}\sum^{n}_{i=j}(-1)^{n-i}C_n^jC_{n-j}^{i-j}g_j=g_n\)
我们就有了
\(\sum^{n}_{i=0}(-1)^{n-i}C_n^if_j=g_n\)