排列

贡献者： jingyuan; addis

预备知识　映射，阶乘

1. 定义

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

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

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

\begin{equation} A_N = N! = N(N-1)(N-2)\dots 1~. \end{equation}

　　我们可以把第 $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{equation} A_n^m = n (n - 1)(n - 2) \cdots (n - m + 1)~. \end{equation}

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

2. 变形

　　我们对式 2 进行变形，

\begin{equation} \begin{aligned} A_n^m &= \frac{n(n - 1)(n - 2) \cdots 2 \cdot 1}{(n - m)(n - m - 1) \cdots 2 \cdot 1}\\ &= \frac{n!}{(n - m)!}~. \end{aligned} \end{equation}

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

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

1. ^ 参考 Wikipedia 相关页面。