形式陈述

集合 $A$$A$ 的排列是双射 $\sigma:A\to A$$\sigma :A\to A$。当 $A=\{1,\ldots,n\}$$A=\{1,\dots ,n\}$ 时，可用有序表

$$ (\sigma(1),\ldots,\sigma(n)) $$$$(\sigma (1),\dots ,\sigma (n))$$

表示，它恰好一次包含每个元素。有限 $n$$n$ 元集合的排列数为

$$ n(n-1)\cdots2\cdot1=n!, $$$$n(n-1)\cdots 2\cdot 1=n!,$$

并约定空集有一个空排列，即 $0!=1$$0!=1$。

直觉

排列既可看成“重新排座位”，也可看成把每个旧位置映到唯一新位置的可逆变换。顺序改变通常产生不同排列。

例子与边界

$\{a,b,c\}$$\{a,b,c\}$ 有 $3!=6$$3!=6$ 个排列。映射 $1\mapsto2,2\mapsto3,3\mapsto1$$1\mapsto 2,2\mapsto 3,3\mapsto 1$ 是一个三循环。含重复符号的字符串排列不是集合排列：交换两个不可区分副本不会产生新结果；只选取部分元素则属于 $k$$k$-排列而非全排列。

推论与应用

排列在复合下形成对称群。它们用于排序、调度、随机洗牌、置换检验以及通过“先有序选择、再消除顺序”推导组合数。

参考资料

• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, rev. 2018, Chapter 15.
• Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019, §6.3.