排列

贡献者： 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 相关页面。

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。