容斥原理
info
若无特殊说明，本章涉及的变量皆为正整数.
简介 #
容斥原理是一种不重不漏的计数原理.
例，$A,B,C$ 三人竞选扫黄队长：
- $15$ 人投给 $A$
- $16$ 人投给 $B$
- $17$ 人投给 $C$
- $2$ 人同时投给 $A,B,C$
- $4$ 人同时投给 $A,B$
- $5$ 人同时投给 $A,C$
- $6$ 人同时投给 $B,C$
问共有多少人参与投票.
$A,B,C$ 三人的得票情况以用韦恩图描述：
- $|A|=15$
- $|B|=16$
- $|C|=17$
- $|A∩B∩C|=2$
- $|A∩B|=4$
- $|A∩C|=5$
- $|B∩C|=6$
求的是投票人数，即 $|A∪B∪C|$.
$$|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|$$
将上述问题推广到普遍情况，就是容斥原理.
公式 #
并集 #
对于 $n$ 个集合 $S_1,S_2\cdots S_n$，$|S|$ 表示集合 $S$ 的元素数，则：
$$\left|\bigcup_{i=1}^nS_i\right|=\sum_i|S_i|-\sum_{i < j}|S_i∩S_j|+\sum_{i < j < k}|S_i∩S_j∩S_k|-\cdots+(-1)^{n+1}\left|\bigcap_{i=1}^nS_i\right|$$
证明
设 $x\in S_{a_1},S_{a_2},\cdots,S_{a_m}$，根据公式，$\left|\bigcup_{i=1}^nS_i\right|$ 中包含元素 $x$ 的个数为：
$$cnt(x)=m-{m\choose 2}+{m\choose 3}-\cdots+(-1)^{n+1}{m\choose m}={m\choose 0}-\sum_{i=0}^m(-1)^i{m\choose i}$$
根据
二项式定理
有：
$$(1-1)^m=\sum_{i=0}^m{m\choose i}1^{m-i}\cdot(-1^i)=\sum_{i=0}^m(-1)^i{m\choose i}$$
$$∴cnt(x)={m\choose 0}-(1-1)^m=1$$
每个元素只出现一次，等价于并集，证毕.
交集 #
对于 $n$ 个集合 $S_1,S_2\cdots S_n$，已知全集为 $U$：
$$\left|\bigcap_{i=1}^nS_i\right|=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right|$$
其中 $\left|\bigcup_{i=1}^n\overline{S_i}\right|$ 套用 并集 的公式计算即可.
多重集的排列数 #
info
普通集合：不允许有相同的元素.
多重集：相同的元素可以出现多次.
设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$ 是由 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$，$\cdots$，$n_k$ 个 $a_k$ 组成的多重集. 设 $ n=\sum_{i=1}^kn_i$. $S$ 的全排列个数为：
$$\frac{n!}{n_1!n_2!\cdots n_k!}$$
证明
$n$ 个不同元素的全排列有 $n!$ 种.
若有 $j$ 个元素相同，则 $n!$ 种排列中有 $j!$ 种排列应算作同一种. 排列数为：
$$\dfrac{n}{j!}$$
根据
乘法原理，多重集的全排列个数为：
$$\frac{n!}{n_1!n_2!\cdots n_k!}$$
多重集的组合数 1 #
设 $S=\{∞\cdot a_1,∞\cdot a_2,\cdots,∞\cdot a_k\}$，从 $S$ 中任取 $λ$ 个元素的方案数为：
$${k+λ-1\choose k-1}$$
证明
原问题等价于求以下方程非负整数解的个数：
$$x_1+x_2+\cdots+x_k=λ$$
解的个数用插板法计算：
在 $λ$ 个 $1$ 之间插 $k-1$ 块板，使其分为 $k$ 个区间. 第 $i$ 个区间的和代表 $x_i$. 这样就构造出了一组解.
需要注意，板插在两端或同一个空隙中是允许的.
最初有 $λ+1$ 个空隙. 插第一块板有 $λ+1$ 种方法，第二块有 $λ+2$ 种，第三块有 $λ+3$ 种 $\cdots$ 第 $k-1$ 块有 $λ+k-1$ 种. 根据
乘法原理，总的方案数为：
$$(λ+1)(λ+2)(λ+3)\cdots(λ+k-1)=A_{λ+k-1}^{k-1}$$
但是插板的顺序与答案无关. 这么算显然会包含一些重复情况：
每一个方案都有 $(k-1)!$ 种不同的插板顺序，故答案为：
$$\dfrac{A_{λ+k-1}^{k-1}}{(k-1)!}={k+λ-1\choose k-1}$$
多重集的组合数 2 #
设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$，从 $S$ 中任取 $λ(λ≤\sum_in_i)$ 个元素的方案数为：
$${k+λ-1\choose k-1}-\sum_i{k+λ-n_i-2\choose k-1}+\sum_{i < j}{k+λ-n_i-n_j-3\choose k-1}-\cdots+(-1)^k{k+λ-\sum_in_i-k-1\choose k-1}$$
证明
考虑容斥原理：
总方案数 $={k+λ-1\choose k-1}$，详见 多重集的组合数 1.
于是问题转化为求不合法方案数.
-
设 $T_i$ 为 $a_i$ 超标的多重集. 先取 $n_i+1$ 个 $a_i$，再任取 $λ-n_i-1$ 个元素，加入 $T_i$. 不同 $T_i$ 的数量为 ${k+λ-n_i-2\choose k-1}$.
-
设 $T_{ij}$ 为 $a_i,a_j$ 超标的多重集. 先取 $n_i+1$ 个 $a_i$ 和 $n_j+1$ 个 $a_j$，再任取 $λ-n_i-n_j-2$ 个元素，加入 $T_{ij}$. 不同 $T_{ij}$ 的数量为 ${k+λ-n_i-n_j-3\choose k-1}$.
依次类推，由容斥原理可得，不合法的方案数为：
$$\left|\bigcup\{T\}\right|=\sum_i{k+λ-n_i-2\choose k-1}-\sum_{i < j}{k+λ-n_i-n_j-3\choose k-1}+\cdots+(-1)^{k+1}{k+λ-\sum_in_i-k-1\choose k-1}$$
于是合法的方案数为：
$${k+λ-1\choose k-1}-\left|\bigcup\{T\}\right|$$