数学概念 — 排列组合

排列组合

参考

https://oi-wiki.org/math/combinatorics/combination/

加法 & 乘法原理

加法原理

完成一个工程可以有 $n$ 类办法， $a_i(1 \le i \le n)$ 代表第 $i$ 类方法的数目。那么完成这件事共有 $S=a_1+a_2+\cdots +a_n$ 种不同的方法。

乘法原理

完成一个工程需要分 $n$ 个步骤， $a_i(1 \le i \le n)$ 代表第 $i$ 个步骤的不同方法数目。那么完成这件事共有 $S = a_1 \times a_2 \times \cdots \times a_n$ 种不同的方法。

排列基础

全排列： $n$ 个人全部来排队，队长为 $n$ 。第一个位置可以选 $n$ 个，第二位置可以选 $n-1$ 个，以此类推得：

\mathrm A_n^n = n(n-1)(n-2) \cdots 3 \times 2 \times 1 = n!

全排列是排列数的一个特殊情况。

从 $n$ 个不同元素中，任取 $m$ （ $m\leq n$ ， $m$ 与 $n$ 均为自然数，下同）个元素按照一定的顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列；从 $n$ 个不同元素中取出 $m$ ( $m\leq n$ ) 个元素的所有排列的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列数，用符号 $\mathrm A_n^m$ （或者是 $\mathrm P_n^m$ ）表示。

排列的计算公式如下：

\mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!}

$n!$ 代表 $n$ 的阶乘，即 $6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6$ 。

公式可以这样理解： $n$ 个人选 $m$ 个来排队 ( $m \le n$ )。第一个位置可以选 $n$ 个，第二位置可以选 $n-1$ 个，以此类推，第 $m$ 个（最后一个）可以选 $n-m+1$ 个，得：

\mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!}

组合基础

从 $n$ 个不同元素中，任取 $m \leq n$ 个元素组成一个集合，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；从 $n$ 个不同元素中取出 $m \leq n$ 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数，用符号 $\dbinom{n}{m}$ 来表示，读作「 $n$ 选 $m$ 」。

组合数计算公式

\dbinom{n}{m} = \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n - m)!}

如何理解上述公式？我们考虑 $n$ 个人选 $m$ 个出来（ $m \le n$ ），不排队，不在乎顺序。如果在乎顺序那么就是 $\mathrm A_n^m$ ，如果不在乎那么就要除掉重复，那么重复了多少？同样选出来的 $m$ 个人，他们还要「全排」得 $m!$ ，所以得：

\begin{aligned} \dbinom{n}{m} \times m! &= \mathrm A_n^m\\\ \dbinom{n}{m} &= \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n-m)!} \end{aligned}

组合数也常用 $\mathrm C_n^m$ 表示，即 $\displaystyle \mathrm C_n^m=\binom{n}{m}$ 。现在数学界普遍采用 $\dbinom{n}{m}$ 的记号而非 $\mathrm C_n^m$ 。

组合数也被称为「二项式系数」，下文二项式定理将会阐述其中的联系。

特别地，规定当 $m>n$ 时， $\mathrm A_n^m=\dbinom{n}{m}=0$ 。