概述

$f_n = \sum_{i=0}^n (-1)^i(^n_i)g_i \Leftrightarrow g_n = \sum_{i=0}^n(-1)^i(^n_i)f_i$

更常见的形式

$f_n = \sum_{i=0}^n (^n_i)g_i \Leftrightarrow g_n = \sum_{i=0}^n(-1)^{n-i}(^n_i)f_i$

原理

其实这玩意儿就是容斥
设集合$S$中具有性质$P_1,P_2,\dots,P_n$的对象集合为$A_1,A_2,\dots,A_n$
那么不具有这些性质的集合大小为

$\begin{eqnarray}
|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}|=
|S| - \sum |A_i| + \sum |A_i \cap A_j| + \cdots + (-1)^n \sum |A_1 \cap A_2 \cap \cdots \cap A_n|
\end{eqnarray}$
那么考虑一种特殊情况,对于$\mathcal{U} = {A_1, A_2, \cdots, A_n}$中任意$i$个集合的并集大小都为$g_i$,不妨设
$g_i = |A_1 \cap A_2 \cap \cdots \cap A_n|$
显然,在$\mathcal{U}$中一共有$(^n_i)$个这样的不同交集。另外我们定义$g_0 = |S|$,这样容斥的结果就是

$\begin{eqnarray}
|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}|
= g_0 - {n \choose 1} g_1 + {n \choose 2} g_2 + \cdots + (-1)^n {n \choose n} g_n
\end{eqnarray}$
我们设
$f_i = |\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_i}|$
同样令$f_0 = |S|$,那么同样使用容斥原理

$\begin{align}
&|A_1 \cap A_2 \cap \cdots \cap A_n| \\
=&|S| - \sum |\overline{A_i}| + \sum |\overline{A_i} \cap \overline{A_j}|
+\cdots + (-1)^n \sum |\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}| \\
=&f_0 - {n \choose 1} f_1 + {n \choose 2} f_2 + \cdots + (-1)^n {n \choose n} f_n
\end{align}$

这即$g_n$的表达式

应用

错位排列

求长度为n的排列$a$,满足对于所有的$1 \leq i \leq n$,使得$i \neq a_i$
首先我们不考虑 $i \neq a_i$ 这个条件,问题是很简单的,长度为$n$的排列一共有$n!$个
这些排列由恰好有$k(k=0,1,2,\dots,n)$个位置改变排列组成,我们设$f_i$为恰好有$i$个位置改变的排列个数
$n! = \sum_{i=0}^n (^n_{n-i})f_i = \sum_{i=0}^n (^n_i)f_i$

令$g_i = i!$,运用二项式反演得到
$\begin{align}
f_n
&= \sum_{i=0}^n(-1)^{n-i}(^n_i)i! \\
&= \sum_{i=0}^n(-1)^{n-i}\frac{n!}{(n-i)!} \\
&= n!\sum_{i=0}^n\frac{(-1)^i}{i!}
\end{align}$

球染色问题

$n$个球排成一行,有$k$种颜色,求给每一个球染色,相邻两个球颜色不可以相同,并且每种 颜色至少使用一次
若不考虑每种颜色至少一次,那么答案就是$k(k-1)^{n-1}$
这些方案由恰好使用了$i(i=0,1,2,\dots,k)$种颜色的方案组成,
设$f_i$为恰好使用了i种颜色的方案数
$k(k-1)^{n-1} = \sum_{i=0}^k(^k_i)f_i$
运用二项式反演
$f_n = \sum_{i=0}^k (-1)^{k-i}(^k_i)i(i-1)^{n-1}$

参考