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

多重集的排列和组合

6.4 多重集的排列和组合

在第 1 章介绍集合的概念时曾经指出：所谓多重集是一些对象（可重复出现）的全体，多重集中对象 $a_i$ 的出现的次数 $n_i$ 称为元素 $a_i$ 的重数。若多重集中不同元素个数为 $k$ 时，称该多重集为 $k$ 元多重集。如果多重集的元素个数是有限的，则称为有限多重集。若有限多重集 $S$ 有 $a_1, a_2, \cdots, a_k$ 共 $k$ 个不同元素，且 $a_i$ 的重数为 $n_i$ ，则可记为

$$
\left\{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\right\}
$$

例6．8 有限 3 元多重集 $\{a, a, a, a, b, b, c\}$ 可简记为 $\{4 \cdot a, 2 \cdot b, 1 \cdot c\}$ 。
如果 $k$ 元多重集的不同元素重复出现任意多数次时，可记为

$$
\left\{\infty \cdot a_1, \quad \infty \cdot a_2, \quad \cdots \infty \cdot a_k\right\}
$$

本节讨论多重集的排列和组合。
多重集的排列
定义6．4 设有限多重集 $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$ ，从 $S$ 中有序选取 $r$ 个元素称为 $S$ 的一个 $r$－排列 $(r \leqslant|S|=n)$ 。当 $r=n$ 时，称为 $S$ 的一个全排列。从 $k$ 元多重集 $S=\left\{\infty \cdot a_1, \infty \cdot a_2, \cdots, \infty \cdot a_k\right\}$ 中有序选取 $r$ 个元素我们也称为 $S$ 的一个 $r$－排列。

定理6．9 设 $k$ 元多重集 $S=\left\{\infty \cdot a_1, \infty \cdot a_2, \cdots, \infty \cdot a_k\right\}$ ，则 $S$ 的 $r$－排列数是 $k^r$ 。
证明：在构造 $S$ 的一个 $r$－排列时，每一位都有 $k$ 种选法。由于 $S$ 中的每种元素可任意次重复，因此每位的选择是相互独立的，由乘法原理得不同的排列数为 $k^r$ 。

例 6.9 求 4 位二进制字符串的个数。
解：此问题相当于求多重集 $\{\infty \cdot 0, \infty \cdot 1\}$ 的 4 －排列数，故为 $2^4=16$ 。

定理 6.10 设有限多重集 $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=|S|$ ，则 $S$的全排列数为

$$
\frac{n!}{n_1 \unrhd n_2 \rrbracket \cdots n_{k}!}
$$

证明：$S$ 的一个排列就是它的 $n$ 个元素的一个全排列，但 $S$ 中有 $n_1$ 个 $a_1$ ，在排列时要占据 $n_1$个位置，故对 $n_1$ 个 $a_1$ 的排列就是从 $n$ 个位置中无序选取 $n_1$ 个位置，其方法数为 $C\left(n, n_1\right)$ 。对 $n_2$ 个 $a_2$ 的排列则是从剩下的 $n-n_1$ 中无序选取 $n_2$ 个位置，其方法数为 $C\left(n-n_1, n_2\right)$ 。对 $S$ 中其他元素的排列可类似地得到方法数。由乘法原理得 $S$ 的排列数为

$$
N=C\left(n, n_1\right) \cdot C\left(n-n_1, n_2\right) \cdot \cdots \cdot C\left(n-n_1-\cdots-n_{k-1}, n_k\right)=\frac{n!}{n_1 \square n_2 \square \cdot \square n_{k}!}
$$

例 6.10 用 2 面红旗， 3 面黄旗和 3 面绿旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志？

解：所求计数相当于有限多重集\｛2•红旗，3•黄旗， $3 \cdot$ 绿旗 $\}$ 的排列数 $N$ ，由定理 6.10 有

$$
N=\frac{8!}{2 \llbracket \sqrt{3} 3!}=560
$$

关于有限多重集的排列问题小结如下。
设 $S=\left\{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\right\}$ ，且 $n=n_1+n_2+\cdots+n_k$ ，则 $S$ 的 $r$ 一排列数 $N$ 满足：
（1）若 $r>n$ ，则 $N=0$ 。
（2）若 $r=n$ ，则

$$
N=\frac{n!}{n_{2}!\square n_{2}!\cdots n_{k}!}
$$

（3）若 $r<n$ ，且对一切 $i=1,2 \cdots, k$ 有 $n_i \geqslant r$ ，则 $N=k^r$ 。
（4）若 $r<n$ ，且存在着某个 $n_i<r$ ，则对 $N$ 没有一般的求解方法，可利用生成函数的方法予以解决。这将在第 12 章中介绍。

多重集的组合
定义6．5 设多重集 $S=\left\{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\right\}$（这里 $n_i$ 可以是有限的也可以是无限的）。 $S$ 的含有 $r$ 个元素的子多重集称为 $S$ 的 $r$－组合。

当 $|S|=n$ ，显然 $S$ 的 $n$－组合只有一个，就是 $S$ 自己。而 $S$ 的 1－组合数有 $k$ 个。
定理6．11 设 $k$ 元多重集 $S=\left\{\infty \square a_1, \infty \square a_2, \cdots, \infty \sqcap a_k\right\}$ ，则 $S$ 的 $r$－组合数是 $C(k+r-1, r)$ 。
证明：$S$ 的任一个 $r$－组合数为 $S$ 的子集，它的形式可写为

$$
\left\{x_1 \cdot a_1, x_2 \cdot a_2, \cdots, x_k \cdot a_k\right\}
$$

其中 $x_i$ 为非负整数，且满足方程 $\sum_{i=1}^k x_i=r$ 。因此，一个 $r$－组合就对应了上述方程的非负整数解。反之，由满足 $\sum_{i=1}^k x_i=r$ 方程的一组非负整数解，也可得到 $S$ 的一个 $r$－组合。所以求 $S$ 的 $r$－组合数就是确定方程 $\sum_{i=1}^k x_i=r$ 的非负整数解的组数。下面将证明这种解的组数就等于多重集 $T=\{(k-1) \cdot 0, r \cdot 1\}$ 的排列数。

给定 $T$ 的一个排列，在此排列中 $k-1$ 个 0 把 $r$ 个 1 分成 $k$ 组。从左数起，第一个 0 的左边的
1 的个数记为 $x_1$ ，介于第一个 0 和第二个 0 之间的 1 的个数记为 $x_2, \cdots$ ，最后一个 0 的右边的 1 的个数记为 $x_k$ ，则所得到的 $x_1, ~ x_2, \cdots, x_k$ 都是非负整数，且其和等于 $r$ 。反之，给定方程 $\sum_{i=1}^k x_i=r$ 的一组非负整数解 $x_1, ~ x_2, ~ \cdots, ~ x_k$ ，可以如下构造排列。

$$
\underbrace{1 \cdots 1}_{x_1} \quad 0 \underbrace{1 \cdots 1}_{x_2} 0 \quad \cdots \quad 0 \underbrace{1 \cdots 1}_{x_k}
$$

它就是多重集 $T$ 的一个排列，根据定理 6．10，$T$ 的排列数为

$$
\frac{(k-1+r)!}{(k-1)!r!}=C(k+r-1, r)
$$

例 6.11 掷 3 粒骰子出现的不同情况有多少种？
解：这相当于从多重集 $\{\infty \cdot 1, \infty \cdot 2, \infty \cdot 3, \infty \cdot 4, \infty \cdot 5, \infty \cdot 6$,$\} 中无序选取 3$个数，由定理 6.11 得，其不同的结果数为 $C(6+3-1,3)=C(8,3)=56$ 。

由定理6．11 可得到两个推论。
推论6．5 设有限多重集 $S=\left\{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\right\}$ ，且 $n_i \geqslant r(1 \leqslant i \leqslant k)$ ，则 $S$ 的 $r$－组合数是 $C(k+r-1, r)$ 。

推论 6.6 设 $k$ 元多重集 $S=\left\{\infty \cdot a_1, \infty \cdot a_2, \cdots, \infty \cdot a_k\right\}, r \geqslant k$ ，若要求 $S$ 的 $k$ 个不同元素的每一个至少在组合中出现一次，则 $S$ 的这种 $r$－组合数是 $C(r-1, k-r)$ 。

证明留作习题。
例 6.12 一个棋手要在相继的 7 天内下 12 盘棋，问有多少种安排法？如果要求每天至少下一盘棋，又有多少种安排法？

解：将这相继的 7 天记为 $a_1, ~ a_2, ~ a_3, ~ a_4, ~ a_5, ~ a_6, ~ a_7$ ，则第一种安排相当于多重集 $S =\left\{\infty \square a_1, \infty \square a_2, \infty \square a_3, \infty \square a_4, \infty \square a_5, \infty \square a_6, \infty \square a_7\right\}$ 的 12－组合问题。由定理6．11 即得 $C$ $(7+12-1,12)=C(18,12)=C(18,6)$ 。而第二种安排相当于 $S$ 的每种元素至少取 1 个的 $12-$ 组合问题，由推论 6.6 得 $C(12-1,7-1)=C(11,6)$ 。

关于有限多重集的组合问题小结如下。
关于有限多重集的组合问题小结如下。
设 $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$ ，则 $S$ 的 $r$－组合数 $N$ 满足：
（1）若 $r>n$ ，则 $N=0$ 。
（2）若 $r=n$ ，则 $N=1$ 。
（3）若 $r<n$ ，且对一切 $i=1,2, \cdots, k$ 有 $n_i \geqslant r$ ，则 $N=C(k+r-1, r)$ 。
（4）若 $r<n$ ，且存在着某个 $n_i<r$ ，则对 $N$ 没有一般的求解方法，可利用容斥原理予以解决，这将在下一节中介绍。

上一篇：牛顿二项式定理

下一篇：容斥原理

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