笔记汇总

排列数

从 $n$ 个不同元素中取 $m$ 个元素排成一列，产生的不同排列数量为：
$A_n^m / P_n^m = \frac{n!}{(n-m)!}$

$A_n^n / P_n^n = n!$

全排列证明：

$A_n^n / P_n^n = n!$

第 $1$ 个元素有 $n$ 种选择，第 $2$ 个元素有 $n - 1$ 种选择…第 $n$ 个元素只有 $1$ 种选择。

由 乘法原理 可知，不同的排列为 $n!$

扩展证明：

$A_n^m / P_n^m = \frac{n!}{(n-m)!}$

第 $1$ 个元素有 $n$ 种选择，第 $2$ 个元素有 $n - 1$ 种选择…第 $m$ 个元素只有 $n - m + 1$ 种选择。

由 乘法原理 可知，不同的排列为 $\displaystyle\prod_{i = n - m}^{n}$

组合数

从 $n$ 个不同元素中取 $m$ 个元素的集合，产生的不同集合数量为：
$C_n^m = \frac{n!}{m!(n-m)!}$

$C_n^n = 1$

$C_n^0 = 1$

$C_0^0 =1$

关系式 $C_n^m = \frac{P_n^m}{P_m^m}$

因为 组合数 不分元素顺序，所以 排列数 比 组合数 的值多乘了一个 $m!$

$C_n^m = C_n^{n-m}$

从 $n$ 个不同元素中取 $m$ 个元素的集合，产生的 不同子集数量 等于 其产生的补集数量。

$C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$

从 $n - 1$ 个不同元素中取 $m$ 个元素的集合， 若再增加一个元素，会增加 $C_{n-1}^{m-1}$ 个集合。

因为在之前的 $n - 1$ 个数里，只有其中一个集合里的数被 替代，方案才会增加。

相当于内定了一个名额，又因为不能重复选，所以原集合也少了一个位置。