排列

列表视角回答每个位置放什么，函数视角回答每个元素被送到哪里。后一视角允许反复作用：从元素 $a$ 出发，依次追踪 $a,\sigma (a),{\sigma }^2(a),\dots$。有限性保证出现重复。设第一次重复是 ${\sigma }^j(a)={\sigma }^i(a)$，其中 $0\le i<j$；若 $i>0$，单射性会推出前一步也相等，与“第一次”矛盾。所以 $i=0$，轨迹确实回到起点，形成循环。

从尚未出现的元素继续追踪，就把全体元素拆成互不相交的循环。循环分解除循环书写顺序、以及每个循环从哪里起笔外是唯一的；这两种书写自由不改变置换本身。

$\{a,b,c\}$ 的六个有序重排是 $abc,acb,bac,bca,cab,cba$。在数字集合上，若 $1\mapsto 3,3\mapsto 2,2\mapsto 1,4\mapsto 4$，则单行记号为 $(3,1,2,4)$，循环记号为 $(132)(4)$。通常省略固定点，写作 $(132)$。

同一循环可写为 $(321)$，因为映射箭头相同；$(123)$ 则反转了箭头，是它的逆。循环记号与单行记号因此必须按上下文区分，不能把括号内同样的数字顺序一律解释为列表。

复合也需明确方向。约定 $(\sigma \circ \tau )(x)=\sigma (\tau (x))$，即先作用右边的置换。取 $\sigma =(12)$、$\tau =(23)$，追踪得到 $1\mapsto 2$、$2\mapsto 3$、$3\mapsto 1$，所以 $\sigma \circ \tau =(123)$；交换作用顺序则得到 $(132)$。置换复合一般不交换。互不相交的循环可以交换，是因为每个元素至多被其中一个循环移动，另一个循环不会改变它的轨道。

从 $n$ 个元素中只选并排列 $k$ 个，属于 $k$-排列，数量为 $n!/(n-k)!$；它对应位置集到候选集的单射，$k<n$ 时并非候选集到自身的置换。

含重复符号的字符串重排也不同。暂把两个 $a$ 标为 $a_1,a_2$，六个带标号排列中，$a_1{a}_{2}b$ 与 $a_2{a}_{1}b$ 擦去标号后都成为 $aab$；其他两种可见结果也各有两条记录。因此 $aab$ 只有 $3!/2!=3$ 种可见重排：$aab,aba,baa$。除法成立，是因为每个结果都恰有 $2!$ 个带标号版本。

全体置换在函数复合下构成对称群，单位元是恒等置换，逆元将每个循环反向。其阶为阶乘理路阶乘Factorial前 n 个正整数的乘积 n!，并约定 0!=1。；不含固定点的置换由错排理路错排Derangement没有任何元素停留在原位置的置换及其计数问题。计数。

循环结构说明一个群作用理路群作用Group action群元素以保持单位元与乘法的方式作用于集合。如何在有限位置间搬动对象，是 Burnside 与 Pólya 对称计数的基础。随机洗牌研究的是置换上的概率分布；能生成全部置换不等于生成得均匀。排序则可在互异元素的前提下，把输入编码成置换并通过消除逆序恢复规定次序。

一份排列还可保留不同统计：第一类Stirling数理路第一类 Stirling 数Unsigned Stirling number of the first kind · Signed Stirling number of the first kind · 循环数以可逆的循环插入证明第一类Stirling递推，区分有符号和无符号约定，复算四阶全表与循环型。按循环个数分组，Eulerian数理路Eulerian 数与排列下降Eulerian number · Eulerian polynomial · 排列下降数以插入最大元素证明下降数递推，推导Eulerian多项式并用n=4分位置核验十一项。按相邻下降个数分组，Lehmer码理路排列逆序编码与字典序编号Lehmer code · Permutation ranking and unranking · Inversion code用右侧较小元素数构造排列的混合进位码，证明确定性编解码和字典序rank/unrank，再复用逆序生成乘积。则保存每位右侧较小元素的数量并可逐步恢复整个列表。比如 $3142$ 的循环是 $(1342)$，只有一个循环；下降有两个，逆序有三个。这些数回答不同的问题。若要禁止某些 $(i,\pi (i))$，由车多项式理路车多项式与禁位排列Rook polynomial · 禁位棋盘计数把兼容的禁位交集编码为非攻击车，证明删占递推、独立分块乘积和禁位排列的容斥公式。处理位置兼容性，而非仅限制循环数。