可重组合

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

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

证明

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

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

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

即

不相邻组合

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

得证