第37课 — 排列与组合（有序）

定义

阶乘

$n! = n \cdot (n-1) \cdot (n-2) \cdots 1$。约定：$0! = 1$。

增长：

斯特林近似：$n! \approx \sqrt{2\pi n}(n/e)^n$。

简单全排列

$P_n = n!$——$n$ 个不同对象排成一行的方式。

重复排列

$n$ 个对象中 $n_1$ 个 1 型，$n_2$ 个 2 型，...，$n_k$ 个 $k$ 型： $P_n^{n_1, n_2, \ldots, n_k} = \frac{n!}{n_1! \cdot n_2! \cdots n_k!}$

"ARARA"（3 A，2 R）的字谜：$5!/(3! \cdot 2!) = 10$。

简单有序选择

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

从 $n$ 个中选 $p$ 个并排序的方式。

圆排列

$n$ 物围圆：$(n-1)!$。原因："首位"是任意的。

排列与有序选择的差别

• 排列：用所有 $n$ 个对象。
• 有序选择：选 $p \leq n$ 个并排序。

当 $p = n$：有序选择与排列重合。