二项式反演

对于某些问题，比较容易计算

钦定 \(k\) 个位置的可能性

而比较难计算

有 \(k\) 个位置的可能性

这个时候可以用二项式反演对问题进行转化

形式2

一共有 \(n\) 个元素，设 \(f(k)\) 是钦定 \(k\) 个元素的方法数，\(g(k)\) 是恰好选 \(k\) 个元素的方法数，那么有如下关系 \[ f(k) =\sum_{i=k}^n\left(\begin{array}{l}i \\k\end{array}\right) g(i) \Leftrightarrow g(k) = \sum_{i=k}^n (-1)^{i-k}\left(\begin{array}{l}i \\k\end{array}\right) f(i) \]

每个 \(g(i)\) 有 \(\left(\begin{array}{l}i \\k\end{array}\right)\) 种钦定方法

例子

\((a,b,c,d)\) 中求 \(f(2)\) 和 \(g(2)\)

钦定 \((a,b)\) , \((a,c)\), \((a,d)\) , \((b,c)\) , \((b,d)\) , \((c,d)\)

\((a,b),(a,b,c),(a,b,d),(a,b,c,d)\) 四种
\((a,c),(a,c,b),(a,c,d),(a,b,c,d)\)

一共 \(f(2) = 6*4=24\)

恰好 \(2\) 个

\((a,b),(a,c),(a,d),(b,c),(b,d),(c,d)\)

\((a,b,c),(a,b,d),(a,c,d),(b,c,d)\)

\(g(2) = 6,g(3)=4,g(4)=1\) \[ f(2) = \left(\begin{array}{l}2 \\ 2\end{array}\right)g(2)+ \left(\begin{array}{l}3 \\2\end{array}\right)g(3)+\left(\begin{array}{l}4 \\2\end{array}\right)g(4) \\ =1*6+3*4+6*1=6+12+6=24 \]

钦定 \(k\) 个不是选大于等于 \(k\) 个

\((a,b),(a,c),(a,d),(b,c),(b,d),(c,d)\)

\((a,b,c),(a,b,d),(a,c,d),(b,c,d)\)

\((a,b,c,d)\)

大于等于 \(2\) 个的是 \(6+4+1=11\)

证明

我们把 \(g(i)\) 代入左边的式子, 展开 \(g(i)\) \[ f(k) = \sum_{i=k}^n\left(\begin{array}{l}i \\k\end{array}\right) \sum_{j=i}^n (-1)^{j-i}\left(\begin{array}{l}j \\i\end{array}\right) f(j) \] 整理一下 \[ f(k) = \sum_{i=k}^n \sum_{j=i}^n (-1)^{j-i}\left(\begin{array}{l}i \\k\end{array}\right)\left(\begin{array}{l}j \\i\end{array}\right) f(j) \] 先枚举 \(j\) 再枚举 \(i\) \[ f(k) = \sum_{j=k}^n \sum_{i=k}^j (-1)^{j-i}\left(\begin{array}{l}i \\k\end{array}\right)\left(\begin{array}{l}j \\i\end{array}\right) f(j) \] 然后变换公式 \[ f(k) = \sum_{j=k}^n \sum_{i=k}^j (-1)^{j-i}\left(\begin{array}{l}j \\k\end{array}\right)\left(\begin{array}{l}j-k \\i-k\end{array}\right) f(j) \] 然后把 \(i\) 从 \(0\) 开始枚举，设 \(t = i-k\) \[ f(k) = \sum_{j=k}^n \sum_{t=0}^{j-k} (-1)^{j-t+k}\left(\begin{array}{l}j \\k\end{array}\right)\left(\begin{array}{c}j-k \\ t\end{array}\right) f(j) \] 根据 \((1-1)^{j-k}= \sum_{t=0}^{j-k} (-1)^{t}\left(\begin{array}{c}j-k \\t\end{array}\right)\) ，其中 \((-1)^t=(-1)^{-t}\) 所以我们可以 \[ f(k) = \sum_{j=k}^n (1-1)^{j-k} (-1)^{j+k}\left(\begin{array}{l}j \\k\end{array}\right) f(j) \] 然后 \((1-1)^{j-k} = [j=k]\) 于是 \[ f(k) = \sum_{j=k}^n [j=k] (-1)^{j+k}\left(\begin{array}{l}j \\k\end{array}\right) f(j) \] 所以和的项只有 \(j=k\) 是，才有贡献，所以直接算第 \(k\) 项 \[ f(k)=(-1)^{k+k}\left(\begin{array}{l}k \\k\end{array}\right) f(k) =f(k) \]

形式1

\(f(k)\) 是 \(k\) 个性质中, 至多\(k\) 个性质满足的个数，\(g(k)\) 是 \(k\) 个性质中恰好 \(k\) 个满足的个数。 \[ f(n)=\sum_{i=0}^k\left(\begin{array}{c} k \\ i \end{array}\right) g(i) \Leftrightarrow g(k)=\sum_{i=0}^k(-1)^{k-i}\left(\begin{array}{c} k \\ i \end{array}\right) f(i) \]

例子

若是 \(k\) 个数中选至多 \(k\) 个数

计算 \(f(2)\)

\((a,b),(a),(b),()\)

\(g(i)=1\) 因为 \(i\) 个数中选恰好 \(i\) 个数就是 \(1\)

然后可以演算 \[ f(2) = \left(\begin{array}{l}2 \\ 0\end{array}\right)g(0)+ \left(\begin{array}{l}2 \\1\end{array}\right)g(1)+\left(\begin{array}{l}2 \\2\end{array}\right)g(2) \\ =1*1+2*1+1*1=1+2+1=4 \]