排列组合

排列 (Permutation)

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

排列满足以下公式：

$$

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

$$

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

组合 (Combination)

定义：对于 $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}

$$

2024-04-13 10:08:32

本页面贡献者：

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