前置知识
- 容斥原理
- 组合数
约定
\(A'_i\)表示集合\(A_i\)的补集。
反演形式
形式一
\[f(n)=\sum_{i=0}^{n}(-1)^iC^i_ng(i)\Leftrightarrow g(n)=\sum_{i=0}^{n}(-1)^iC^i_nf(i) \]
证明
设\(A_1,A_2,A_3,A_4\dots\)是分别具有性质\(P_1,P_2,P_3,P_4\dots\)的集合。
\[A_1\bigcap A_2\bigcap A_3\dots A_n=S-\sum_{i=1}^{n}A_i'+(\sum_{1<=i<j<=n}A_i'\bigcap A_j')-\dots+(-1)^n*(A_1'\bigcap A_2'\bigcap \dots A_n') \]
\[A_1'\bigcap A_2'\bigcap A_3'\dots A_n'=S-\sum_{i=1}^{n}A_i+(\sum_{1<=i<j<=n}A_i\bigcap A_j)-\dots+(-1)^n*(A_1\bigcap A_2\bigcap \dots A_n) \]
那么设\(g(i)\)等于上述任意\(i\)个集合的交集大小，\(f(i)\)等于上述任意\(i\)个集合的补集的交集大小，\(g(0)=S,f(0)=S\),则有
\[g(n)=\sum_{i=0}^{n}(-1)^iC^i_nf(i) \]
\[f(n)=\sum_{i=0}^{n}(-1)^iC^i_ng(i) \]
发现这两个表达式是对称的，所以就代表\(f\)，和\(g\)可以互相推导。事实上，这两个函数的关系是一个下三角矩阵。
然后就证完了。在上面的推导中，我们其实默认了任意\(i\)个集合的交集的大小是一定的。也就是说每个集合中不同的元素做出的贡献是相同的，不会出现元素个数相同的集合做出的贡献不同的情况，比如一些组合类问题就符合这个特征。这是一个要注意的地方。但是哪里要注意我也不知道。
形式二
\[g(n)=\sum_{i=0}^{n}C_n^if(i)\Leftrightarrow f(n)=\sum_{i=0}^{n}(-1)^{n-i}C_n^ig(i) \]
\[f(n)=\sum_{i=0}^{n}C_n^ig(i)\Leftrightarrow g(n)=\sum_{i=0}^{n}(-1)^{n-i}C_n^if(i) \]
证明
设\(d(i)=(-1)^ig(i)\),有：
\[f(n)=\sum_{i=0}^nC^i_nd(i) \]
\[\frac{d(n)}{(-1)^n}=\sum_{i=0}^{n}(-1)^iC_n^if(i) \]
下面那个式子变形可得：
\[d(n)=\sum_{i=0}^{n}(-1)^{i+n}C^i_nf(i) \]
显然和这个式子等价：
\[d(n)=\sum_{i=0}^{n}(-1)^{n-i}C^i_nf(i) \]
把\(d(i)\)看成\(g(i)\)就证完了。
事实上，第二个形式在\(i\)不从\(0\)开始的时候也是正确的，具体看这篇博客。
作用
在一些题目中用来放宽条件来进行求解。
习题
待填。
京公网安备 11010502036488号