最后更新: 2025-01-22 09:02 ● 参与者查看: 15 次纠错分享参与项目词条搜索

容斥原理

容斥原理（也称为包含排斥原理）是一个基本的计数原理，它在概率论和数论中也经常使用。

定理 6.12 设 $A, B$ 为有限集合，则有

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

证明：因为 $A \cup B=A \cup(B-A)$ ，而 $A \cap(B-A)=\varnothing, B=(A \cap B) \cup(B-A),(A \cap B)$ $\cap(B-A)=\varnothing$ ，所以由加法原理 $|A \cup B|=|A|+|B-A| ;|B|=|A \cap B|+|B-A|$ ，后式代入前式即得 $|A \cup B|=|A|+|B|-|A \cap B|$ 。

进一步，此定理可推广到 $n$ 个有限集合。
定理 6.13 设 $A_1, A_2, \cdots, A_n$ 为有限集合，则

$$
\left|U_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right|-\sum_{i<j}\left|A_i \cap A_j\right|+(-1)^{n-1}\left|A_1 \cap A_2 \cap \cdots \cap A_n\right|
$$

证明留作习题。
推论 6.7 设 $S$ 是一个有限集，$P_1, P_2, \cdots, P_n$ 是集合 $S$ 中元素可能具有的 $n$ 种性质，$A_1$ ， $A_2, \cdots, A_n$ 分别是 $S$ 中具有性质 $P_1, P_2, \cdots, P_n$ 的元素全体构成的集合，即 $A_i \subseteq S$ ，则 $S$ 中不具有性质 $P_1, P_2, \cdots, P_n$ 的元素个数为

$$
\begin{aligned}
& \left|\bar{A}_1 \cap \bar{A}_2 \cap \cdots \cap \bar{A}_n\right| \\
& =|S|-\sum_{i=1}^n\left|A_i\right|+\sum_{i<j}\left|A_i \cap A_j\right|-\cdots+(-1)^n\left|A_1 \cap A_2 \cap \cdots \cap A_n\right|
\end{aligned}
$$

例6．13 某系有 100 个学生至少要学法，德，英 3 种语言中的一种。现在这 100 个学生中有 42 人学法语， 45 人学德语， 65 人学英语， 15 人学法语和德语， 20 人学法语和英语， 25 人学德语和英语。问同时学 3 种语言的有多少？仅学英语的有多少？

解：令 $A, B, C$ 分别表示学法语，德语，英语学生的集合。则 $|A|=42,|B|=45,|C|=65, \mid A$ $\cap B|=15,|A \cap C|=20,|B \cap C|=25,|A \cup B \cup C|=100$ 。由容斥原理得

$$
|A \cap B \cap C|=|A \cup B \cup C|-(|A|+|B|+|C|)+|A \cap B|+|A \cap C|+|B \cap C|=8
$$

仅学英语的人数为

$$
|C|-|A \cap C|-|B \cap C|+|A \cap B \cap C|=28
$$

有限多重集的 $r$－组合数
设多重集 $S=\left\{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\right\}, n=n_1+n_2+n_k$ ，在上节我们叙述了当 $r<n$ ，且存在着某个 $n_i<r$ 时，$S$ 的 $r$－组合数没有一般的求解方法，但可利用容斥原理予以解决。

例 6.15 求 $S=\{3 \cdot a, 4 \cdot b, 5 \cdot c\}$ 的 10 －组合数。
解：把容斥原理应用到多重集 $D=\{\infty \cdot a, \infty \cdot b, \infty \cdot c\}$ 的所有 10 －组合的集合 $Y$ 上，则 $S$的 10 －组合全体即为 $Y$ 的子集。令 $P_1$ 表示 $D$ 的 10 －组合中有多于 3 个 $a$ 这一性质，$P_2$ 表示 $D$ 的 $10-$组合中有多于 4 个 $b$ 这一性质，$P_3$ 表示 $D$ 的 10 －组合中有多于 5 个 $c$ 这一性质，令 $A_i(i=1,2,3)$表示 $D$ 的具有性质 $P_i(i=1,2,3)$ 的 10 －组合全体，则 $S$ 的 10 －组合数等于 $\left|\bar{A}_1 \cap \bar{A}_2 \cap \bar{A}_3\right|$ 。故由容
斥原理得

$$
\begin{aligned}
& \left|\bar{A}_1 \cap \bar{A}_2 \cap \bar{A}_3\right|=|Y|-\left|A_1 \cup A_2 \cup A_3\right| \\
& =|Y|-\left(\left|A_1+A_2+A_3\right|\right)+\left(\left|A_1 \cap A_2\right|+\left|A_1 \cap A_3\right|+\left|A_2 \cap A_3\right|\right)-\left|A_1 \cap A_2 \cap A_3\right|
\end{aligned}
$$

由定理 6.11 及其推论易求得

$$
=C(3,1),\left|A_1 \cap A_3\right|=1,\left|A_2 \cap A_3\right|=\left|A_1 \cap A_2 \cap A_3\right|=0 \text { 。 }
$$

因此 $\left|\bar{A}_1 \cap \bar{A}_2 \cap \bar{A}_3\right|=C(12,2)-C(8,2)-C(7,2)-C(6,2)+C(3,1)+1=6$ 。
例 6.16 求 $x_1+x_2+x_3=5\left(0 \leqslant x_1 \leqslant 2,0 \leqslant x_2 \leqslant 2,1 \leqslant x_3 \leqslant 5\right)$ 的整数解个数。
解：令 $x_3^{\prime}=x_3-1$ ，则原问题即为求在约束条件下，

$$
0 \leqslant x_1 \leqslant 2, \quad 0 \leqslant x_2 \leqslant 2, \quad 0 \leqslant x_3^{\prime} \leqslant 4
$$

$x_1+x_2+x_3^{\prime}=4$ 的整数解个数。此问题与多重集 $\{2 \cdot a, 2 \cdot b, 4 \cdot c\}$ 的 $4-$ 组合数相同。因此把容斥原理应用到多重集 $D=\{\infty \cdot a, \infty \cdot b, \infty \cdot c\}$ 的所有 4－组合的集合 $Y$ 上，则 4 －组合全体即为 $Y$ 的子集。令 $P_1$ 表示 $D$ 的 4－组合中有多于 2 个 $a$ 这一性质，$P_2$ 表示 $D$ 的 4－组合中有多于 2 个 $b$ 这一性质， $P_3$ 表示 $D$ 的 4－组合中有多于 4 个 $c$ 这一性质，令 $A_i(i=1,2,3)$ 表示 $D$ 的具有性质 $P_i(i=1,2,3)$ 的 4－组合全体。则 4－组合数等于 $\left|\bar{A}_1 \cap \bar{A}_2 \cap \bar{A}_3\right|$ 。故由容斥原理得

由定理 6.11 及其推论易求得

$$
\begin{aligned}
|Y| & =C \quad(6,4)=C(6,2), \quad\left|A_1\right|=\left|A_2\right|=C(3,1), \quad\left|A_3\right|=0, \quad\left|A_1 \cap A_2\right|=\left|A_1 \cap A_3\right|=\left|A_2 \cap A_3\right|=\mid A_1 \cap \\
A_2 \cap A_3 \mid & =0
\end{aligned}
$$

所以 $\left|\bar{A}_1 \cap \bar{A}_2 \cap \bar{A}_3\right|=C(6,2)-C(3,1)-C(3,1)=9 \text { 。 }$

上一篇：多重集的排列和组合

下一篇：幂级数型生成函数

本文对您是否有用？有用 (0) 无用 (0)