排列
pái liè
排列是把一组物体按特定顺序排列的方式，顺序在其中起决定作用。
Formula
P(n, r) = \dfrac{n!}{(n-r)!}
Definition
排列是把一组事物按特定顺序排列的方式；排列数用来计算有多少种不同的有序排列方式。从 $n$ 个物品中取 $r$ 个的排列是一种有序选取：$P(n,r) = n!/(n-r)!$，$n$ 个不同物品的总排列数是 $n!$。形式上，对于含重复元素的排列（多重集排列），计数为 $n!/(n_1!n_2!\cdots n_k!)$，其中 $n_i$ 是第 $i$ 种不同物品的个数，即多项式系数；置换群（对称群 $S_n$）是抽象代数中的基础概念，其中 $S_3$（$3$ 个物体的所有排列）是最小的非阿贝尔群。
Example
在一场 $5$ 名学生参加的比赛中，有多少种方式让 $3$ 名学生获得第一、第二、第三名？$P(5,3) = 5 \times 4 \times 3 = 60$ 种方式，因为顺序很重要（第一名、第二名、第三名是不同的名次）。用数字 $1$-$9$ 且不重复创建一个 $4$ 位密码，有 $P(9,4) = 9!/5! = 3{,}024$ 种可能性。单词 MISSISSIPPI 有 $11$ 个字母（$M(1)$、$I(4)$、$S(4)$、$P(2)$），因此不同排列的数量是 $11!/(1! \cdot 4! \cdot 4! \cdot 2!) = 34{,}650$。
Key Insight
排列与组合的关键区别在于顺序是否重要：ABC 和 CBA 是相同的组合，但却是不同的排列。置换群将组合数学与群论和物理学（粒子对称性）联系起来，因为 $S_3$ 有 $6$ 个元素，是最小的非阿贝尔群。