二项式反演与容斥

二项式反演

容斥原理：

$$|A_1\cup A_2 \cup \cdots \cup A_n| = \sum|A_i| - \sum|A_i\cap A_j| + \cdots + (-1)^n |A_1\cap A_2 \cap \cdots \cap A_n|$$

根据狄摩根律，可以得到

$$\begin{align} |\overline{A_1}\cap \overline{A_2} \cdots \cap \overline{A_n}| =& |\overline{A_1\cup A_2 \cup \cdots \cup A_n}| \\ =& |S| - |A_1\cup A_2 \cup \cdots \cup A_n| \\ =& |S| - \sum|A_i| + \sum|A_i\cap A_j| - \cdots - (-1)^n |A_1\cap A_2 \cap \cdots \cap A_n| \end{align}$$

代入补集，可以得到

$$|A_1\cap A_2 \cap \cdots \cap A_n|=|S|-\sum|\overline{A_i}|+\sum|\overline{A_i}\cap \overline{A_j}|-...+(-1)^n|\overline{A_1}\cap \overline{A_2}\cap ...\cap \overline{A_n}|$$

设 $ f(n) = |\overline{A_1}\cap \overline{A_2} \cdots \cap \overline{A_n}| $ ， $ g(n) = |A_1\cap A_2 \cap \cdots \cap A_n| $ 则可以得到

$$f(n)=\sum\limits_{i=0}^n(-1)^i{C_n^i}g(i)\\ g(n)=\sum\limits_{i=0}^n(-1)^i{C_n^i}f(i)$$

通过转化可以得到第一种形式：

$$f(n)=\sum\limits_{i=0}^n{C_n^i}g(i)\\ g(n)=\sum\limits_{i=0}^n(-1)^{n-i}{C_n^i}f(i)$$

同样可以得到第二种形式：

$$f(n)=\sum\limits_{i=n}^m{C_i^n}g(i)\\g(n)=\sum\limits_{i=n}^m(-1)^{i-n}{C_i^n}f(i)$$

这两种形式可以进行恰好与至多至少的转换。

恰好与至多：

设 $ f_i $ 表示至多有 $ k $ 个的方案数， $ g_i $ 表示恰好有 $ k $ 个的方案数，则可以得到：

$$f_k = \sum_{i=0}^kC_k^i g_i$$

至多有 $ k $ 个，就是包括恰好有 $ 0,1,\ldots,k $ 个。

根据反演形式一可以得到：

$$g_k=\sum\limits_{i=0}^k (-1)^{k-i} C_k^i f_i$$

当 $ f_i $ 很容易求时，就可以使用该公式求 $ g_i $

恰好与至少：

设 $ f_i $ 表示至少有 $ k $ 个的方案数， $ g_i $ 表示恰好有 $ k $ 个的方案数，则可以得到：

$$f_k = \sum_{i=k}^nC_i^k g_i$$

至少有 $ k $ 个，就是包括恰好有 $ k,k+1,\ldots,n $ 个。

根据反演形式二可以得到：

$$g_k=\sum\limits_{i=k}^n (-1)^{i-k} C_i^k f_i$$

当 $ f_i $ 很容易求时，就可以使用该公式求 $ g_i $

参考链接

浅谈容斥原理 - Quick_Kk - 博客园 (cnblogs.com)

二项式反演及其应用 - GXZlegend - 博客园 (cnblogs.com)

Miskcoo’s Space