最后更新: 2025-01-22 09:02 查看: 214 次纠错评论(0) 课件开VIP

容斥原理

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

定理 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 { 。 }$

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

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

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

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