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

集合元素的组合

本节讨论集合元素的组合问题，并介绍 $n$ 个元素集合上的 $k$ 组合个数 $C(n, k)$ 之有关性质及各种恒等式。

集合的组合
定义 6.3 从 $n$ 个元素的集合 $A$ 中无序选取 $r$ 个元素组成 $S$ 的子集称为 $S$ 的一个 $r$－组合，不同的组合总数记为 $C(n, r)$ 。当 $n \geqslant 0$ ，规定 $C(n, 0)=1$ 。

显然当 $r>n$ 时，$C(n, r)=0$ 。
定理 6.5 对于一切 $r \leqslant n$ ，有

$$
C(n, r)=\binom{n}{r}=\frac{p(n, r)}{r!}
$$

即

$$
C(n, r)=\frac{n!}{r!(n-r)!}
$$

证明：$C(n, r)$ 表示从 $n$ 个元素中选取 $r$ 个元素的选法数，与前面集合的排列相比，主要差别在于后者还对所选出的 $r$ 个元素进行有序排位，这有 $r!$ 种。由乘法原理得，$n$ 个元素的 $r$种元素的排列数是

$$
p(n, r)=C(n, r) r!
$$

即 $C(n, r)=n!/(r!(n-r)!)$
由定理 6.5 可得到以下的推论。
推论 6.1 对于一切 $r \leqslant n$ ，有 $C(n, r)=C(n, n-r)$ 。
证明：

$$
C(n, \quad r)=n!/(r!(n-r)!)=n!/((n-(n-r))!(n-r)!)=C(n, \quad n-r)
$$

例 6.6 在 100 件产品中，有 2 件次品。
（1）从其中任意抽出 3 件，方式数是多少？
（2）抽出的 3 件产品中恰有 2 件为次品的方式数是多少？
（3）抽出的 3 件产品中恰有 1 件次品的方式数是多少？
（4）抽出的 3 件产品中至少有 1 件为次品的方式数是多少？
（5）抽出的 3 件产品中没有次品的方式数是多少？
解：（1）这是组合问题，故有 $C(100,3)=161700$ 。

（2）从次品中选取 2 件，有 $C(2,2)$ 种，另外从正品中选 1 件，有 $C(98,1)$ 种；由乘法原理得，共有 $C(2,2) \times C(98,1)=98$ 种。
（3）从次品中选取 1 件，有 $C(2,1)$ 种，另外从正品中选 2 件，则有 $C(98,2)$ 种；故共有 $C \quad(2,1) \times C(98,2)=9506$ 种。
（4）抽出的 3 件产品中至少有 1 件为次品，有两种情况，即恰有 1 件次品和恰有 2 件次品，故共有 $9506+98=9604$ 种。
（5）没有次品即意味着是从正品中选取，有 $C(98, ~ 3)=152096$ 种。
例 6.7 从 $1,2, \cdots, 300$ 之中任取 3 个数，使得它们的和能被 3 整除，问有多少种选取方法？

解：把 $1,2, \cdots, 300$ 分成 $A, B, C$ 三个组。

$$
\begin{aligned}
& A=\{x \mid x \equiv 1(\bmod 3)\} \\
& B=\{x \mid x \equiv 2(\bmod 3)\} \\
& C=\{x \mid x \equiv 0(\bmod 3)\}
\end{aligned}
$$

设任取的 3 个数为 $i, j, k$ ，则选取是无序的且满足 $i+j+k \equiv 0(\bmod 3)$ ，选法可分成两类：
$i, j, k$ 都取自同一组，共有三个组，方法数为 $3 C(100,3)$ ；
$i, j, k$ 分别取自 $A, B, C$ 这 3 个集合，由乘法原理知，方法数为 $(C(100,1))^3$ 。
由加法原理，总取法数为 $3 C(100,3)+(C(100,1))^3$ 。
二项式系数及组合恒等式
表示 $n$ 个元素集合上的 $k$ 组合个数 $C(n, k)$ 有不少性质及相关恒等式，由于它们出现在二项式定理之中，故称它们为二项式系数。在计算机科学的算法分析中的不少公式里，二项式系数经常出现，接下来讨论其有关性质。

上一篇：集合的排列

下一篇：牛顿二项式定理

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