可重组合

从 ${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 $ 的全排列

得证