Foata 基本变换

循环书写原来没有起点，也没有块间顺序。我们先用最大元素作起点，再排序循环，这才消除了书写自由。括号擦掉后并非丢失信息：每当遇到一个比此前所有元素都大的新纪录，就知道新循环从这里开始。

逆变换为什么唯一 ​

标准循环的每个首位大于自己块内所有元素，也大于前面各块的最大元素，所以它是纪录。块内非首位小于本块首位，不可能是纪录。于是首位集合恰等于纪录集合。

反过来，给任意列表，在每个纪录前切开。每块首位必是本块最大值：若后面首次出现更大的值，它本身就会是新纪录而被切到下一块。各块首位递增，所以加括号后已经处于标准形式。切开与擦括号互为逆，完成双射证明。

下降与亏位的逐边核对 ​

同一循环内相邻两项 $a,b$ 满足 $\sigma (a)=b$，它们形成下降恰当 $\sigma (a)<a$。每块末项回到块首最大元的闭合箭头不是亏位；单元素块是相等。两块之间的接缝也必上升，因为后块首位比整个前块都大。故没有额外下降或漏掉亏位。

最后，若 $\pi (i)>i$，令 $j=\pi (i)$，则 ${\pi }^{-1}(j)=i<j$。$i\mapsto j$ 给超越位置与逆排列亏位的一一对应，所以 $\mathrm{exc}(\pi )=\mathrm{def}({\pi }^{-1})$。

取 $\sigma =(123)(45)$。标准形式是 $(312)(54)$，所以 $F(\sigma )=31254$。纪录是 $3,5$，恰有两个循环；下降位置为一、四，下降数二。原映射的亏位是 $3\mapsto 1$ 与 $5\mapsto 4$，也为二。

从 $31254$ 反向开始，纪录切口给 $312|54$，恢复 $(312)(54)$。这份原排列的超越数却是三，分别来自 $1\mapsto 2,2\mapsto 3,4\mapsto 5$。因此 $F(\sigma )$ 并不直接将超越送到下降；必须按本页约定先取逆。

例如 $\pi ={\sigma }^{-1}$ 的单行表示为 $31254$，其超越位置为一、四，数量二；$F({\pi }^{-1})=31254$ 的下降数也为二。在一般输入中输出不必恰好等于输入，这里只是一个便于核验的小例。

若随便擦括号，例如先把循环写成 $(12)(3)$ 得 $123$，逆向纪录切开会变成 $(1)(2)(3)$，丢失原排列。标准化不是格式装饰，而是可逆性的必要部分。不同作者使用最小元、逆序排列循环等约定时，会对应另一组统计恒等式，不能混用结论。

第一类 Stirling 数理路第一类 Stirling 数Unsigned Stirling number of the first kind · Signed Stirling number of the first kind · 循环数以可逆的循环插入证明第一类Stirling递推，区分有符号和无符号约定，复算四阶全表与循环型。 $c(n,k)$ 也数恰有 $k$ 个从左到右纪录的列表。$n=4$ 时纪录数为一、二、三、四的排列分别有 $6,11,6,1$ 份。这个同分布不是因为“循环看起来像纪录”，而是由已构造的双射保证。

Eulerian 数理路Eulerian 数与排列下降Eulerian number · Eulerian polynomial · 排列下降数以插入最大元素证明下降数递推，推导Eulerian多项式并用n=4分位置核验十一项。 $A(n,k)$ 同时数恰有 $k$ 个超越的排列。$n=4$ 时分布为 $1,11,11,1$。下降与超越是不同的单个对象统计，即使分布相同也不能逐个替换。

这个方法在新问题里的可迁移部分是：先为有书写自由的结构选择一个可识别的标准表示，再找出擦除标点后仍能恢复它们的局部标记。如果限制只对某些循环长度成立，变换后的合法列表条件可能很复杂；双射并不保证每个额外条件也变成简单条件。

本页的标准循环变换与Foata 第二基本变换理路主指标与逆序数的构造性等分布Major index equidistribution · Foata second fundamental transformation · Mahonian statistics · Foata 第二基本变换以逐字分块旋转及显式逆操作证明主指标等于像的逆序数，处理重复符号，并证明逆下降集合保持。应区分：后者逐字按阈值切块、把块末字母移到块首，并保持最后一个字母，以此把主指标送到逆序数。这里的纪录切口逆变换则恢复循环括号；两种变换有不同的输入解释、逆算法与统计不变量，不可仅凭名字互换。