前置知识

  • 容斥原理
  • 组合数

约定

\(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\)开始的时候也是正确的,具体看这篇博客

作用

在一些题目中用来放宽条件来进行求解。

习题

待填。