可重组合与不相邻组合

可重组合

从 ${1, 2, 3 \cdots, n – 1, n}$ 中选出 $m$ 个元素,可以重复,有多少个不同的组合?

答案 $C_{n + m – 1}^{m}$

证明

显然,问题可以转换为 $m$ 个球放入 $n$ 个盒子,可以放无数个或者不放

即插入 $n – 1$ 个隔板,然后求全排列 $(m + n – 1)!$

但是隔板和球的顺序是无效的所以除去 $m! \times (n-1)!$


$$
\frac{(m + n – 1)!}{m! \times (n – 1)!} = C_{n + m -1}^m
$$

不相邻组合

从 $A = {1, 2, 3 \cdots, n – 1, n}$ 中选取 $m$ 个不相邻的数,有多少个不同的组合

答案 $C_{n – m + 1}^{m}$

证明

设 $B={b_1, b_2, b_3 \cdots b_{m – 1}, b_m}$ 是一个不相邻组合,假设 $b_1 < b_2 < b_3 < \cdots < b_{m – 1} < b_m$

令 $c_1 = b_1, c_2 = b_2 + 1, c_3 = b_3 + 2 \cdots c_m = b_m + m – 1$

$c_m \leq n + m – 1$

即 $c$ 为 $1$ 到 $ n + m – 1 $ 的全排列

得证

发表评论

电子邮件地址不会被公开。 必填项已用*标注