容斥原理

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 \cap B \cap C | =$ $2$ ；
$| A \cap B | =$ $4$ ；
$| A \cap C | =$ $5$ ；
$| B \cap C | =$ $6$ 。

求的是投票人数，即 $| A \cup B \cup C |$ 。

| A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | A \cap C | - | B \cap C | + | A \cap B \cap C |

将上述问题推广到普遍情况，就是容斥原理。

公式

并集

对于 $n$ 个集合 $S_{1},$ $S_{2} \dots S_{n}$ ， $| S |$ 表示集合 $S$ 的元素数，则：

| ⋃_{i = 1}^{n} S_{i} | = \sum_{i} | S_{i} | - \sum_{i < j} | S_{i} \cap S_{j} | + \sum_{i < j < k} | S_{i} \cap S_{j} \cap S_{k} | - \dots + (- 1)^{n + 1} | ⋂_{i = 1}^{n} S_{i} |

证

设 $x \in S_{a_{1}},$ $S_{a_{2}},$ $\dots,$ $S_{a_{m}}$ ，根据公式， $| ⋃_{i = 1}^{n} S_{i} |$ 中包含元素 $x$ 的个数为：

cnt (x) = m - (\binom{m}{2}) + (\binom{m}{3}) - \dots + (- 1)^{n + 1} (\binom{m}{m}) = (\binom{m}{0}) - \sum_{i = 0}^{m} (- 1)^{i} (\binom{m}{i})

根据二项式定理有：

(1 - 1)^{m} = \sum_{i = 0}^{m} (\binom{m}{i}) 1^{m - i} \cdot (- 1^{i}) = \sum_{i = 0}^{m} (- 1)^{i} (\binom{m}{i})

∴ cnt (x) = (\binom{m}{0}) - (1 - 1)^{m} = 1

每个元素只出现一次，等价于并集，证毕。

交集

对于 $n$ 个集合 $S_{1},$ $S_{2} \dots S_{n}$ ，已知全集为 $U$ ：

| ⋂_{i = 1}^{n} S_{i} | = | U | - | ⋃_{i = 1}^{n} \overset{―}{S_{i}} |

其中 $| ⋃_{i = 1}^{n} \overset{―}{S_{i}} |$ 套用并集的公式计算即可。

多重集的排列数

普通集合：不允许有相同的元素；
多重集：相同的元素可以出现多次。

设 $S =$ ${n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \dots, n_{k} \cdot a_{k}}$ 是由 $n_{1}$ 个 $a_{1}$ ， $n_{2}$ 个 $a_{2}$ ， $\dots$ ， $n_{k}$ 个 $a_{k}$ 组成的多重集。

设 $n =$ $\sum_{i = 1}^{k} n_{i}$ 。

$S$ 的全排列个数为：

\frac{n!}{n_{1}! n_{2}! \dots n_{k}!}

证明

$n$ 个不同元素的全排列有 $n!$ 种。

若有 $j$ 个元素相同，则 $n!$ 种排列中有 $j!$ 种排列应算作同一种。排列数为：

\frac{n}{j!}

根据乘法原理，多重集的全排列个数为：

\frac{n!}{n_{1}! n_{2}! \dots n_{k}!}

多重集的组合数 1

设 $S =$ ${\infty \cdot a_{1}, \infty \cdot a_{2}, \dots, \infty \cdot a_{k}}$ ，从 $S$ 中任取 $λ$ 个元素的方案数为：

(\binom{k + λ - 1}{k - 1})

证明

原问题等价于求以下方程非负整数解的个数：

x_{1} + x_{2} + \dots + x_{k} = λ

解的个数用插板法计算：

在 $λ$ 个 $1$ 之间插 $k -$ $1$ 块板，使其分为 $k$ 个区间。第 $i$ 个区间的和代表 $x_{i}$ 。这样就构造出了一组解。

需要注意，板插在两端或同一个空隙中是允许的。

最初有 $λ +$ $1$ 个空隙。插第一块板有 $λ +$ $1$ 种方法，第二块有 $λ +$ $2$ 种，第三块有 $λ +$ $3$ 种 $\dots$ 第 $k -$ $1$ 块有 $λ +$ $k -$ $1$ 种。根据乘法原理，总的方案数为：

(λ + 1) (λ + 2) (λ + 3) \dots (λ + k - 1) = A_{λ + k - 1}^{k - 1}

但是插板的顺序与答案无关。这么算显然会包含一些重复情况：

每一个方案都有 $(k -$ $1)!$ 种不同的插板顺序，故答案为：

\frac{A_{λ + k - 1}^{k - 1}}{(k - 1)!} = (\binom{k + λ - 1}{k - 1})

多重集的组合数 2

设 $S =$ ${n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \dots, n_{k} \cdot a_{k}}$ ，从 $S$ 中任取 $λ (λ \leq \sum_{i} n_{i})$ 个元素的方案数为：

(\binom{k + λ - 1}{k - 1}) - \sum_{i} (\binom{k + λ - n_{i} - 2}{k - 1}) + \sum_{i < j} (\binom{k + λ - n_{i} - n_{j} - 3}{k - 1}) - \dots + (- 1)^{k} (\binom{k + λ - \sum_{i} n_{i} - k - 1}{k - 1})

证明

考虑容斥原理：合法方案数 $=$ 总方案数 $-$ 不合法方案数。

总方案数 $= (\binom{k + λ - 1}{k - 1})$ ，详见多重集的组合数 1。

于是问题转化为求不合法方案数。

设 $T_{i}$ 为 $a_{i}$ 超标的多重集。先取 $n_{i} +$ $1$ 个 $a_{i}$ ，再任取 $λ -$ $n_{i} -$ $1$ 个元素，加入 $T_{i}$ 。不同 $T_{i}$ 的数量为 $(\binom{k + λ - n_{i} - 2}{k - 1})$ ；
设 $T_{i j}$ 为 $a_{i},$ $a_{j}$ 超标的多重集。先取 $n_{i} +$ $1$ 个 $a_{i}$ 和 $n_{j} +$ $1$ 个 $a_{j}$ ，再任取 $λ -$ $n_{i} -$ $n_{j} -$ $2$ 个元素，加入 $T_{i j}$ 。不同 $T_{i j}$ 的数量为 $(\binom{k + λ - n_{i} - n_{j} - 3}{k - 1})$ ；
...

依次类推，由容斥原理可得，不合法的方案数为：

\begin{aligned} | ⋃ {T} | = & \sum_{i} (\binom{k + λ - n_{i} - 2}{k - 1}) \\ - \sum_{i < j} (\binom{k + λ - n_{i} - n_{j} - 3}{k - 1}) \\ + \dots \\ + (- 1)^{k + 1} (\binom{k + λ - \sum_{i} n_{i} - k - 1}{k - 1}) \end{aligned}

于是合法的方案数为：

(\binom{k + λ - 1}{k - 1}) - | ⋃ {T} |

同余

组合数学

数值分析

多项式

圆锥曲线

简介

公式

并集

交集

多重集的排列数

多重集的组合数 1

多重集的组合数 2

容斥原理

简介 ​

公式 ​

并集 ​

交集 ​

多重集的排列数 ​

多重集的组合数 1 ​

多重集的组合数 2 ​

简介

公式

并集

交集

多重集的排列数

多重集的组合数 1

多重集的组合数 2