最后更新: 2025-02-12 07:03 查看: 192 次反馈同步训练

重复组合

## 重复组合
从 $n$ 个不同元素中取出 $m$ 个元素组成一组, 如果允许元素在组合中重复出现, 这样的组合简称为重复组合, 这种重复组合用符号 $\mathrm{H}_n^m$ 表示.

怎样计算重复组合的组合数呢? 我们还是先从具体例子开始考虑, 假如有三个不同的元素 $a_1, a_2, a_3$, 从其中取出两个元素组成重复组合, 那么, 可以得到如下的六个不同组合:

$$
a_1 a_1, a_1 a_2, a_1 a_3, a_2 a_1, a_2 a_3, a_3 a_3
$$

如果是不允许元素重复的话, 要选两个元素得到不同的组合数是 6 的话,应是 $\mathrm{C}_4^2$, 设这四个元素为 $a_1^{\prime}, a_2^{\prime}, a_3^{\prime}, a_4^{\prime}$, 那么得到的组合为:

$$
a_1^{\prime} a_2^{\prime}, a_1^{\prime} a_3^{\prime}, a_1^{\prime} a_4^{\prime}, a_2^{\prime} a_3^{\prime}, a_2^{\prime} a_4^{\prime}, a_3^{\prime} a_4^{\prime}
$$

组合（1）与组合（2）不难建立它们之间的一一对应关系。在组合（1）的每个组合的元素下标上分别加上 0 和 1 , 就得到了下标与 (2) 完全一致的组合 (3).

$$
a_{1+0} a_{1+1}, \quad a_{1+0} a_{2+1}, \quad a_{1+0} a_{3+1}, \quad a_{2+0} a_{2+1}, \quad a_{2+0} a_{3+1}, \quad a_{3+0} a_{3+1}
$$

又例如从 4 个不同元素中取出 3 个元素的重复组合有如下的不同组合:

$$
\begin{aligned}
& a_1 a_1 a_1 \quad a_1 a_1 a_2 \quad a_1 a_1 a_3 \quad a_1 a_1 a_4 \\
& a_1 a_2 a_2 \quad a_1 a_2 a_3 \quad a_1 a_2 a_4 \\
& a_1 a_3 a_3 \quad a_1 a_3 a_4 \quad a_1 a_4 a_4 \\
& a_2 a_2 a_2 \quad a_2 a_3 a_3 \quad a_2 a_2 a_4 \\
& a_2 a_3 a_3 \quad a_2 a_3 a_4 \quad a_2 a_4 a_4 \\
& a_3 a_3 a_3 \quad a_3 a_3 a_4 \quad a_3 a_4 a_4 \\
& a_3 a_3 a_3 \quad a_3 a_3 a_4 \quad a_3 a_4 a_4 \quad a_4 a_4 a_4
\end{aligned}
$$

只要我们在每组元素的下标上分别加 $0,1,2$ ，就得到
 ![图片](/uploads/2024-09/afd4ab.jpg)
 这又正是从六个不同元素中取出 3 个元素的组合的全部。从上面的例子说明了

$$
\mathrm{H}_3^2=\mathrm{C}_{3+(2-1)}^2, \quad \mathrm{H}_4^3=\mathrm{C}_{4+(3-1)}^3
$$

按同样的方法我们可以得出: 从 $n$ 个不同元素中取出 $m$ 个的重复组合数有如下的关系:

$$
\mathrm{H}_n^m=\mathrm{C}_{n+(m-1)}^m
$$

现在我们来证明这个结论.

**定理 6**
从 $n$ 个不同元素中, 任取 $m$ 个元素的重复组合为:

$$
\mathrm{H}_n^m=\mathrm{C}_{n+(m-1)}^m
$$
证明: 为了研究问题方便,我们用 $1,2,3, \ldots, n$ 表示这 $n$ 个不同的元素。在其中任取 $m$ 个允许重复的数字作为一个组合, 并按大小顺序排成

$$
1 \leq i_2 \leq i_2 \leq \cdots \leq i_m \leq n
$$

又记 $j_1=i_1+0, j_2=i_2+1, \ldots, j_m=i_m+(m-1)$
自然, $1 \leq j_1<j_2<j_3<\cdots<j_m \leq n+(m-1)$, 所以 $\left\{j_1, j_2, \ldots, j_m\right\}$是 $n+m-1$ 个数, 并且是 $1,2, \ldots, n+m-1$ 中的 $m$ 个不同数的组合.

下面来证明：在 $n$ 个不同元素中任取 $m$ 个允许重复的元素的组合，和 $n+m-1$ 个不同元素中任取 $m$ 个不同元素的组合之间有一个到上的一一对应关系。如果这点证明了, 那么 $n$ 个不同元素的 $m$ 个允许重复元素的组合数就与 $n+m-1$ 个不同元素的 $m$ 个不同元素的组合数相等了.
证明:
为了证明这个一一对应, 要先证明当允许重复的组合 $\left\{i_1, i_2, \ldots, i_m\right\}$ 与 $\left\{i_1^{\prime}, i_2^{\prime}, \ldots, i_m^{\prime}\right\}$ 不同的时候, （这里取 $1 \leq i_1 \leq i_2 \leq \cdots \leq i_m \leq n, 1 \leq$ $\left.i_1^{\prime} \leq i_2^{\prime} \leq \cdots \leq i_m^{\prime} \leq n\rig

免费注册看余下 50%

非VIP会员每天15篇文章，开通VIP 无限制查看

上一篇：重复排列

下一篇：连加符号与连乘符号

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