排列

贡献者： jingyuan; addis

预备知识　映射，阶乘

1. 定义

　　¹我们讨论含有 $N$ 个元素的任意集合，由于集合中元素的名称不重要，我们以下将它记为 ${1, 2, \dots, N}$ 。注意集合的是没有顺序的，例如 ${1, 2, 3}$ 和 ${1, 3, 2}$ 是同一个集合。当我们把集合 $S$ 中的的元素按照某种顺序排列成一个序列时，就称为它是集合 $S$ 的一种排列（permutation）。每个排列可以看作一个映射 $f : {1, \dots, N} \to {1, \dots, N}$ 。

　　一般地，从 $n$ 个不同元素中任取 $m$ （ $m \leq n$ ）个元素，按照一定顺序排列成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列（arrangement）

　　那么 $N$ 个元素的集合一共有几种不同的排列呢？第 1 个位置有 $N$ 种不同的可能，确定之后第 2 个位置有 $N - 1$ 种不同的可能，第 3 个位置有 $N - 2$ 种……最后一个位置只有 1 种。所以可能性的种数可以用阶乘表示，记为 $A_{N}$

\begin{matrix} (1) & A_{N} = N! = N (N - 1) (N - 2) \dots 1 . \end{matrix}

　　我们可以把第 $i$ 种排列记为 $p_{i}$ ，该排列的元素按照顺序分别记为 $p_{i, 1}, p_{i, 2}, \dots, p_{i, N}$ 。

　　根据一个排列的定义，两个排列相同的含义为：组成排列的元素相同，并且元素的排列顺序也相同。

　　从 $n$ 个不同元素中取出 $m$ （ $m \leq n$ ）个元素所有排列的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列数（number of arrangement），用符号 $A_{n}^{m}$ 表示。

　　根据分布乘法计数原理可得排列数公式

\begin{matrix} (2) & A_{n}^{m} = n (n - 1) (n - 2) \dots (n - m + 1) . \end{matrix}

未完成：分布乘法计数原理是什么

2. 变形

　　我们对式 2 进行变形，

\begin{matrix} (3) & \begin{aligned} A_{n}^{m} & = \frac{n (n - 1) (n - 2) \dots 2 \cdot 1}{(n - m) (n - m - 1) \dots 2 \cdot 1} \\ = \frac{n!}{(n - m)!} . \end{aligned} \end{matrix}

　　式 3 为排列数的另一种表达形式

未完成：例题，补充更多内容

1. ^ 参考 Wikipedia 相关页面。