最后更新: 2025-02-12 07:03 查看: 115 次反馈刷题

重复组合

## 重复组合
从 $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\right)$ 那么, 不同元素不允许重复的组合 $\left\{j_1, i_2, \ldots, i_m\right\}$ 与$\left\{j_1^{\prime}, j_2^{\prime}, \ldots, j_m^{\prime}\right\}$ 也不同, 这里 $\left\{j_1=i_1+0, j_2=i_2+1, \ldots, j_m=i_m+m-1, j_1^{\prime}=\right.$ $\left.i_1^{\prime}+0, j_2^{\prime}=i_2^{\prime}+1, \ldots, j_m^{\prime}=i_m^{\prime}+m-1\right\}$.

事实上, 如果后者相同, 即有 $j_k=j_k(k=1,2, \ldots, m)$ 即

$$
i_k+k-1=i_k^{\prime}+k-1(k=1,2, \ldots, m)
$$

所以 $i_k=i_k^{\prime}(k=1,2, \ldots, m)$ ，也就是说 $\left\{i_1, i_2, \ldots, i_m\right\}$ 也与 $\left\{i_1^{\prime}, i_2^{\prime}, \ldots, i_m^{\prime}\right\}$ 相同了。这就证明了上述的对应为一一对应.

再证明这是到上的一一对应，即当 $\left\{i_1, i_2, \ldots, i_m\right\}$ 取遍 $n$ 个数 $1,2, \ldots, n$的一切 $m$ 个数的允许重复组合时， $\left\{j_i, j_2, \ldots, j_m\right\}$ 也取遍 $n+m-1$ 个数 $1,2, \ldots, n+m-1$ 一切的 $m$ 个数的不允许重复的组合.

事实上，对任一个组合 $\left\{j_1, j_2, \ldots, j_m\right\}$ ，其中 $1 \leq j_1<j_2<\cdots<j_m \leq$ $n+m-1$. 有 $1 \leq j_1, 2 \leq j_2, 3 \leq j_3, \ldots, m \leq j_m$. 故 $1 \leq i_1=j_1-0,1 \leq i_2=$ $j_2-1,1 \leq i_3=j_3-2, \ldots, 1 \leq i_m=j_m-(m-1)$ 。即 $i_1, i_2, \ldots, i_m$ 都是自然数, 且由 $j_k>j_{k-1}$, 可知 $j_k-j_{k-1} \geq 1$, 故有
$$
i_k-i_{k-1}=\left[j_k-(k-1)\right]-\left[j_{k-1}-(k-2)\right]=j_k-j_{k-1}-1 \geq 0
$$

再者 $i_m=j_m-(m-1) \leq(n+m-1)-(m-1)=n$. 总之有 $1 \leq i_1 \leq i_2 \leq$ $\cdots \leq i_m \leq n$. 所以, $\left\{i_1, i_2, \ldots, i_m\right\}$ 是 $n$ 个数 $12, \ldots, n$ 中取 $m$ 个数的允许重复的组合，这证明了对应是到上的一一对应。

`例`从 $3,5,7,9,11$ 中取出 3 个数（可以重复选取）相乘，问有多少个不同的乘积?

解：因为是乘积，与元素取出的先后顺序无关，同时是可以重复选取的，即是重复组合问题. 所以

$$
\mathrm{H}_5^3=\mathrm{C}_{5+(3-1)}^3=\mathrm{C}_7^3=35
$$

答：有 35 个不同的乘积.

`例`从三个不同的质数 $a_1, a_2, a_3$ 中取出 4 个数相乘（可以重复选取），问有多少个不同的乘积?
解：同例 2.16 是重复组合问题. 所以

$$
\mathrm{H}_3^4=\mathrm{C}_{3+(4-1)}^4=\mathrm{C}_6^4=\mathrm{C}_6^2=15
$$

答：有 15 个不同的乘积。

`例`用七种不同的颜色给一个四面体的四个面涂上颜色, 规定每个面上只能涂一种颜色, 如果四个面的颜色容许相同, 问有几种不同的着色方法?

解: 因为只研究对四个面所着的颜色, 对那个面先着色并无先后顺序之分, 故是组合问题. 又因为对四个面所着的色是允许相同的, 所以又是重复组合问题.所以

$$
\mathrm{H}_7^4=\mathrm{C}_{7+(4-1)}^4=\mathrm{C}_{10}^4=210
$$

答：共有 210 种不同的着色方法。

开VIP会员

非会员每天6篇，会员每天16篇，VIP会员无限制访问

题库训练自我测评投稿

上一篇：重复排列

下一篇：二项式定理

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