主指标与逆序数的构造性等分布

主指标把每次下降的位置全部加起来，逆序数则比较所有远近位置。把一个新字母 $x$ 接到长为 $m$ 的前缀 $w$ 后，主指标只可能增加零或 $m$。分块旋转的任务正是把像的逆序增量也精确做成这两个数。

每一步只重新排列已有字母，最后再添 $x$，所以重数与末字母保持。特别是 $\mathrm{\Phi }(w)$ 的末字母就是 $w$ 的末字母，构造采用的分支确实知道原词是否出现新下降。

两个分支都要核算 ​

设 $r=\mathrm{\Phi }(w)$，$|w|=m$。若末字母 $\le x$，各块 $U_j{y}_j$ 中 $U_j$ 的每项都 $>x\ge y_j$。把 $y_j$ 搬到前面恰删去 $|U_j|$ 个逆序。追加 $x$ 又产生一个与每个 $>x$ 的旧字母配对的逆序，共 $\sum _j|U_j|$ 个，净增零。

若末字母 $>x$，各块中 $U_j$ 的每项都 $\le x<y_j$。旋转恰增加 $|U_j|$ 个逆序；追加 $x$ 又与每块唯一的 $>x$ 字母 $y_j$ 产生逆序。若块数为 $b$，净增

不同块之间的字母没有互换块序，跨块逆序总数不变。以上正好匹配

从空词归纳便证明统计不变量。

从首字母判定逆分支 ​

给输出 $vx$，先取走末字母 $x$。若 $v$ 空，前缀也空。否则看 $v$ 的首字母：首字母 $\le x$ 时，在每个 $\le x$ 字母前切开；首字母 $>x$ 时，在每个 $>x$ 字母前切开。各块必为 $y_j{U}_j$，把首字母移到末尾，恢复 $r$。继续求 ${\mathrm{\Phi }}^{-1}(r)$，最后接回 $x$。

这两个分支的输出首项分别属于 $\le x$ 与 $>x$ 两个不交类别，因而可识别。块内其余字母全部属于另一类，切口也唯一。每次递归长度减一，所以逆算法终止；左右旋转和追加、移除互相抵消，证明双射，不只是证明“算出的逆序数正确”。

取 $w=314265$。它在位置 $1,3,5$ 下降，故主指标为九，而原逆序数只有四。逐字状态为

其中追加 $2$ 时，$314$ 的末项 $4>2$，切为 $3|14$，旋转成 $3|41$，接二得到 $3412$。最后追加 $5$ 时，$34126$ 的末项 $6>5$，整段 $34126$ 只有末项大于五，所以是一块，右旋并接五得到 $634125$。

输出的逐位右侧较小数为 $(5,2,2,0,0,0)$，和为九。用Lehmer 逆序码理路排列逆序编码与字典序编号Lehmer code · Permutation ranking and unranking · Inversion code用右侧较小元素数构造排列的混合进位码，证明确定性编解码和字典序rank/unrank，再复用逆序生成乘积。作这个独立检查，不把统计相等误当逐字相等。

完整逆算从 $634125$ 开始：

• 取末项五，$63412$ 首项六大于五；左旋唯一块得到 $34126$
• 取末项六，$3412$ 首项三不大于六；各字母单独一块，保持 $3412$
• 取末项二，$341$ 首项三大于二；在三、四前切为 $3|41$，左旋得到 $314$
• 取末项四，$31$ 分成两个单块；再取末项一，单块三保持；最后取三

取出的末项依次为 $5,6,2,4,1,3$，反读恢复 $314265$。

重复符号也能处理：$2121$ 的主指标为四，状态 $2,21,212,2211$ 给出四个逆序。另一个必要的等号测试是 $2112$：追加第二个一时须把 $21$ 作为一块，得到 $121$，最终 $\mathrm{\Phi }(2112)=1212$，逆序数一等于原主指标。若把分支的 $\le$ 偷换成 $<$，相等末项可能没有合法尾块，整个算法就不再是上述双射。

空词、单字词、全相同词均固定，两个统计都为零。$\mathrm{\Phi }$ 一般不是对合：$\mathrm{\Phi }(314265)=634125$，逆向应执行明确的左旋算法，不能假定再应用一次前向变换即可。

对互异标签的排列，既有逆序码已证明

本页的新增结论是同一个多项式也等于 $\sum _w{q}^{\mathrm{maj}(w)}$。由此主指标分布满足

越界下标取零。四阶系数 $1,3,5,6,5,3,1$ 复用旧逆序分布；它不是新的 Eulerian 下降总数表。固定重复字母的闭式则由Gaussian 多项式与多重集加权计数理路Gaussian 二项式与多重集加权计数Gaussian binomial coefficient · q-binomial coefficient · q-multinomial coefficient · Gaussian polynomial以二元词逆序和矩形内分拆定义q二项式，证明递推、乘积及有限q二项式定理，再推导重复字母的逆序多项式。给出。

还有一个可精确保留的条件。对 $w\in S_n$，定义逆下降集合

$\mathrm{\Phi }$ 保持这个集合。逐步考察一对连续数值 $i,i+1$：若新字母就是其中之一，它在原词与像中都追加于所有旧字母之后；若两者都已经出现，新字母 $x$ 与它们不同，不可能严格夹在连续数值之间。它们便同属 $\le x$ 或 $>x$ 一侧，而每块旋转只让一个异侧端点穿过另一侧的一段，不改变任一侧内部的相对次序。两者的左右先后保持，归纳即得。

直接实现可迭代维护当前词，每次扫描并复制一个长至 $m$ 的前缀，前向与逆向总计 $1+2+\cdots +(n-1)=O(n^2)$ 次比较和字母移动。只保留当前词、下一词及逆向取出的末项列表时，额外工作空间为 $O(n)$；若保存全部中间状态供展示，则要 $O(n^2)$ 空间。递归且每层保留整份词的实现也可能占用二次空间，不能沿用迭代版本的空间界。

因此在任意固定逆下降集合的排列子类中，主指标与逆序仍等分布。它 不 保持原下降集合：$314265$ 有三次下降，像 $634125$ 只有两次。对任意禁位、固定原下降集合或其他受限子类，必须先证明该类在变换下封闭，才可转移分布。下降数与主指标的联合计数理路Carlitz q-Eulerian 联合多项式Carlitz q-Eulerian polynomial · Euler–Mahonian distribution · Descent major-index polynomial按插入缝的主指标增量推导下降与主指标联合递推，并由稳定排序与差分参数给出加权Worpitzky生成函数。另需自己的加权插入证明。