排列组合

排列 (Permutation)

定义：对于 $n$ 个不同元素中取出 $m$ 个元素，按照一定的顺序排成一排，叫做一个排列。排列的方案数记作 $\mathrm{A}^n_m$ 或者 $\mathrm{P}^n_m$ 。

排列满足以下公式：

$$ \mathrm{A}^n_m = \frac{n!}{(n - m)!} $$

特别地，$n=m$ 时称作“全排列”。

定义：对于 $n$ 个不同元素中取出 $m$ 个元素，按照任意的顺序排成一排，叫做一个组合。组合的方案数记作 $\mathrm{C}^n_m$ 或者 $\binom{n}{m}$ 。其中其满足：

$$ \binom{n}{m} = \frac{n!}{m!(n - m!)} $$

因为排列与组合的关系，所以也满足：

$$ \binom{n}{m} = \frac{\mathrm{A}^n_m}{m!} $$

杨辉三角与组合也有紧密的联系。以下是杨辉三角的一部分：

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

我们可以发现，对于杨辉三角第 $n$ 行 $m$ 列的值 $Y_{nm}$ 满足：

$$ Y_{nm}=\binom{n}{m} $$

杨辉三角也是由前面的值代推出来的，因为其满足性质 $Y_{nm}=Y_{n-1m}+Y_{n-1m-1}$，所以对于组合，相同的结论也有效，得：

$$ \binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1} $$

同时，杨辉三角每一行呈轴对称，所以发现其也满足

$$ \binom{n}{m} = \binom{n-m}{m} $$

对于任意的二项式 $(a+b)^n$，展开后可以发现满足以下定理：

$$ (a+b)^n=\sum_{i=0}^n \binom{n}{i}a^ib^{n-i} $$

本页面贡献者：本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用