从容斥开始谈起：
\(|A\cup B|=|A|+|B|-|A\cap B|\)
更一般的：
\(|A_1\cup A_2\cup...\cup A_n|=\sum_{i=1}^n|A_i|-\sum_{1\le i<j\le n}|A_i\cap A_j|+...+(-1)^{n-1}|A_1\cap A_2\cap...\cap A_n|\)
证明：设\(a\)在\(M\)个集合出现，对左侧的贡献为1。对右侧的贡献为\(\sum_{i=1}^M(-1)^{i-1}C(M,i)=-\sum_{i=1}^M(-1)^iC(M,i)=1-\sum_{i=0}^M(-1)^iC(M,i)=1-(1-1)^M=1\)
证毕。
设\(A^c\)为\(A\)的补集
则有\(|A_1^c\cap A_2^c\cap ...\cap A_n^c|=|S|-\sum\limits_{1\le i\le n}|A_i|+\sum\limits_{1\le i<j\le n}|A_i\cap A_j|-...+(-1)^n\times |A_1\cap A_2\cap ...\cap A_n|\)
考虑其对偶形式。
又有\(|A_1\cap A_2\cap ...\cap A_n|=|S|-\sum\limits_{1\le i\le n}|A_i^c|+\sum\limits_{1\le i<j\le n}|A_i^c\cap A_j^c|-...+(-1)^n\times |A_1^c\cap A_2^c\cap ...\cap A_n^c|\)
考虑一种特殊情况：多个集合的交集大小只和集合的数目有关。
设\(f(n)\)表示\(n\)个补集之和，\(g(n)\)表示\(n\)个原集之和，定义\(f(0),g(0)\)为全集。
上述两个形式可以利用\(f(n),g(n)\)表示为
\(f(n)=\sum_{i=0}^{n}(-1)^iC(n,i)g(i)\)
\(g(n)=\sum_{i=0}^{n}(-1)^nC(n,i)f(i)\)
有了这两个式子开始推导二项式反演。
形式1：
\(f(n)=\sum_{i=0}^nC(n,i)g(i)\Leftrightarrow g(n)=\sum_{i=0}^n(-1)^{n-i}C(n,i)f(i)\)
证明1：
设\((-1)^ih(i)=g(i)\)则\(f(n)=\sum_{i=0}^{n}(-1)^iC(n,i)h(i)\)
则有\(h(n)=\sum_{i=0}^{n}(-1)^iC(n,i)f(i)\)又\(\frac{g(n)}{(-1)^n}=\sum_{i=0}^{n}(-1)^iC(n,i)f(i)\)可得\(g(n)=\sum_{i=0}^{n}(-1)^{n-i}C(n,i)f(i)\)
证明2：
\(f(n)=\sum_{i=0}^nC(n,i)\sum_{j=0}^i(-1)^{i-j}C(i,j)f(j)=\sum_{j=0}^n\sum_{i=j}^nC(n,i)C(i,j)(-1)^{i-j}f(j)=\sum_{j=0}^nf(j)\sum_{i=j}^nC(n,j)C(n-j,i-j)(-1)^{i-j}=\sum_{j=0}^nf(j)C(n,j)\sum_{i=0}^{n-j}C(n-j,i)(-1)^{i}=\sum_{j=0}^nf(j)C(n,j)(1-1)^{n-j}\)
当\(n-j\neq 0\)时显然值为0
当\(n-j=0\)时考虑这一点特殊的值为\(f(n)C(n,n)=f(n)\)
故等式成立。
进一步的有\(f(n)=\sum\limits_{i=m}^n{n\choose i}g(i)\Leftrightarrow g(n)=\sum\limits_{i=m}^n(-1)^{n-i}{n\choose i}f(i)\)
形式2：
\(f(n)=\sum\limits_{i=n}^m{i\choose n}g(i)\Leftrightarrow g(n)=\sum\limits_{i=n}^m(-1)^{i-n}{i\choose n}f(i)\)
证明：\(f(n)=\sum_{i=n}^mC(i,n)g(i)=\sum_{i=n}^m\sum_{j=i}^m(-1)^{j-i}C(j,i)C(i,n)f(j)=\sum_{j=n}^m\sum_{i=n}^j(-1)^{j-i}C(j,i)C(i,n)f(j)=\sum_{j=n}^m\sum_{i=n}^j(-1)^{(j-n)-(i-n)}C(j,n)C(j-n,i-n)f(j)=\sum_{j=n}^mC(j,n)f(j)\sum_{i=0}^{j-n}(-1)^{(j-n)-i}C(j-n,i)=\sum_{j=n}^mC(j,n)f(j)(1-1)^{n-j}\)
当\(j=n\)时值为\(f(n)\)证毕。