二项式定理
\[(a + b)^n = \displaystyle\sum^{n}_{i=0}{\binom{n}{i}a^ib^{n-i}} \]证明：
数学方法。
\[(a + b) ^ n = a \times (a + b) ^ {n - 1} = a \times b \times (a + b) ^ {n - 2} = \dots \]假设我们选了 \(k\) 个 \(a\)，我们就需要选 \(n - k\) 个 \(b\)，根据乘法原理，可以得到 \(a^k b^{n-k}\)，由于每次是 \(n\) 选 \(k\) 个 \(a\)，故得到 \(\binom{n}{k}\)，最终加和求得。
证毕。
其中 \(\binom{n}{i}\) 为二项式系数。
特殊情况
令 \(a = -1, b = 1\)，得到：
\[(1 + (-1)) ^ n = \displaystyle\sum^{n}_{i=0}{(-1)^n\binom{n}{i}} \]当 \(n = 0\) 时：
\[\binom{0}{0}(-1)^0 = 1 \]因此得出：
\[\displaystyle\sum^{n}_{i=0}{(-1)^n\binom{n}{i}} = [n = 0] \]其中方括号为艾弗森括号。
常用的二项式推论
\[\binom{n}{m} = \binom{n}{m - 1} + \binom{n - 1}{m - 1}\\ \ \\ \binom{n}{m} = \frac{n}{m}\binom{n - 1}{m - 1} \\ \ \\ \binom{n}{i}\binom{i}{j} = \binom{n}{j}\binom{n - j}{i - j} (i,j \leq n) \\ \ \\ \displaystyle\sum^n_{i=0}{\binom{n}{i}} = 2^n \\ \ \\ \displaystyle\sum^m_{i=0}\binom{n}{i}\binom{m}{k - i} = \binom{n + m}{k} \]容斥
容斥，说人话，即为在统计方案数出现重复计数的情况时，我们需要使用容斥求解。
简单容斥
已知集合 \(\left|S_1\right|,\left|S_2\right|\)，求 \(\left| S_1 \cup S_2 \right|\)。
最简单的容斥，只需要减去它们之间重叠的部分即可。
\[\left|{S_1 \cup S_2}\right| = \left| S_1 \right| + \left| S_2 \right| - \left|{S_1 \cap S_2}\right| \]若已知集合 \(\left|S_1\right|,\left|S_2\right|, \left|S_3\right|\)，求 \(\left|{S_1 \cup S_2 \cup S_3}\right|\)
可以用韦恩图求解。
\[\left|{S_1 \cup S_2 \cup S_3}\right| = \left| S_1 \right| + \left| S_2 \right| + \left| S_3 \right| - \left| S_1 \cap S_2 \right| - \left| S_1 \cap S_3 \right| - \left| S_2 \cap S_3 \right| + \left| S_1 \cap S_2 \cap S_3 \right| \]对于更多集合的容斥：
\[\begin{aligned} \left|{\mathop{\cup}\limits^{n}_{i=1}{S_i}}\right| &= \displaystyle\sum^{n}_{i=1}{\left|{S_i}\right|} - \displaystyle\sum_{1\leq i < j \leq n}{\left|{S_i \cap S_j}\right|} + \displaystyle\sum_{1 \leq i < j < k \leq n}{\left|{S_i \cap S_j \cap S_k}\right|} - \dots + (-1)^{n-1}{\displaystyle\sum^n_{i=1}{\mathop{\cap}\limits_{i=1}^{n}{\left|{S_i}\right|}}} \\ &= \displaystyle\sum^{n}_{i=1}{(-1)^{i-1}\displaystyle\sum_{a_i < a_{i+1}}\left|{\mathop{\cap}\limits_{i=1}^{n}{S_{a_i}}}\right|} \end{aligned} \]二项式反演
在已知函数 \(f_n\) 与 \(g_n\) 存在特定关系，即 \(f_n\) 为 \(n\) 项物品构成特定结构的方案数，\(g_n\) 为从 \(n\) 中选出 \(i \geq 0\) 项物品构成特殊结构的方案数，在已知 \(f_n\) 的情况下我们很容易可以得到：
\[g_n = \displaystyle\sum^n_{i=0}{\binom{n}{i}f_n} \]那如果我们只知道 \(g_n\) 呢？
考虑递推，从 \(1\) 项物品推到 \(n\) 项物品，显然的我们会发现有情况会算重，因此需要带容斥系数。
\[f_n = \displaystyle\sum_{i=1}^{n}{(-1)^{n-i}\binom{n}{i}g_n} \]对于这种特殊关系：当题目中出现恰好需要 \(n\) 项物品构成特殊结构的方案数，可以转换成 \(f_n\) 表示恰好需要 \(n\) 项物品构成特殊结构的方案数，\(g_n\) 表示至少 / 至多需要 \(n\) 项物品构成特殊结构的方案数，题目中出现至少 / 至多需要亦可。
例题
P10596 BZOJ2839 集合计数
记 \(f_i\) 表示集合交集元素恰为 \(i\) 的方案数，\(g_i\) 表示选出 \(j\) 个子集交集元素为 \(i\) 的方案数，发现它们满足二项式反演的关系，即 \(f_i\) 是 \(i\) 个不同元素构成特定结构的方案数时 \(g_i\) 是从 \(i\) 个中选出 \(j \geq 0\) 个构成特定结构的方案数，\(f_k\) 即为我们想要的答案，得到以下柿子：
\[g_n = \displaystyle\sum_{i=0}^{n}{\binom{n}{i}f_i} \\ \downarrow \\ f_n = \displaystyle\sum_{i=0}^{n}{(-1)^{n-i}\binom{n}{i}g_i} \]所以推出 \(f_k\) 的柿子，但是在 \(n - k\) 中取会算重，所以应该是取至少 \(k\)，得到：
\[f_k = \displaystyle\sum^{n}_{i=k}{(-1)^{i-k}\binom{i}{k}g_i} \]在剩下 \(n - k\) 个中，选的方案数 \(\binom{n}{i}\)，任意选或不选，方案数是 \(2^{n-k}\)，再从这些集合中选出若干个非空集合方案数是 \(2^{2^{n-k}} - 1\)，得到 \(g_k\)：
\[g_k = \displaystyle\sum^{n}_{i=k}{\binom{n}{i} \cdot (2^{2^{n-i}} - 1)} \]答案就是 \(g_k\)。
习题
P10986 [蓝桥杯 2023 国 Python A] 2023
标签：right,sum,cap,容斥,数学,binom,二项式,displaystyle,left From： https://www.cnblogs.com/Ayaka-0928/p/18646263