从排列主指标到偏序赋值 ​

本页把“两个数表碰巧一样”换成可重算的结构证据：一份可逆的词变换、一张加权递推表、一份偏序赋值分解。所有逆序和下降都使用严格大于，下降不含末位置，也不环接首尾。

一条短主线，三条可选出口 ​

短主线是下降数理路Eulerian 数与排列下降Eulerian number · Eulerian polynomial · 排列下降数以插入最大元素证明下降数递推，推导Eulerian多项式并用n=4分位置核验十一项。 → 主指标与 Foata 第二变换理路主指标与逆序数的构造性等分布Major index equidistribution · Foata second fundamental transformation · Mahonian statistics · Foata 第二基本变换以逐字分块旋转及显式逆操作证明主指标等于像的逆序数，处理重复符号，并证明逆下降集合保持。 → 下降—主指标联合递推理路Carlitz q-Eulerian 联合多项式Carlitz q-Eulerian polynomial · Euler–Mahonian distribution · Descent major-index polynomial按插入缝的主指标增量推导下降与主指标联合递推，并由稳定排序与差分参数给出加权Worpitzky生成函数。。完成任务一、二和四，即可交出双射、不变量与生成函数证书；不必先学习偏序或对称函数。

• 符号会重复：加读Gaussian 与多重集权重理路Gaussian 二项式与多重集加权计数Gaussian binomial coefficient · q-binomial coefficient · q-multinomial coefficient · Gaussian polynomial以二元词逆序和矩形内分拆定义q二项式，证明递推、乘积及有限q二项式定理，再推导重复字母的逆序多项式。，完成任务三。需要二项式系数和有限生成多项式
• 输入有先后限制：加读偏序理路偏序Partial order · Partially ordered set满足自反、反对称和传递性的关系。与标号偏序分拆理路标号偏序分拆与主指标生成函数Labeled P-partition · (P, omega)-partition · P-partition fundamental theorem · Major-index shuffle theorem以相等值的标签顺序唯一分解偏序分拆，推导线性扩张的主指标分子，并对任意互异标签的两条词证明洗牌公式。，完成任务五、六。洗牌公式用到任务三的 Gaussian 多项式
• 要数有限时段赋值：继续序多项式互反理路序多项式与严格计数互反Order polynomial · Order polynomial reciprocity · Strict order polynomial · Stanley order reciprocity以线性扩张的下降展开计算有限偏序保序映射，证明次数及首系数，再用互补标号和负二项式得到弱严格互反。，完成任务七。它用二项式多项式的负输入，不能把负上标一概视为零

旧标准循环变换理路Foata 基本变换Foata fundamental transformation · Fundamental bijection on permutations通过标准循环书写与纪录位置切分构造互逆双射，证明循环数对应纪录数、下降数对应亏位并迁移到超越统计。处理的是纪录、循环和亏位。这里的第二变换不擦循环括号；旧Lehmer 码理路排列逆序编码与字典序编号Lehmer code · Permutation ranking and unranking · Inversion code用右侧较小元素数构造排列的混合进位码，证明确定性编解码和字典序rank/unrank，再复用逆序生成乘积。作为逐位逆序检查工具复用。

任务一：把六字排列送到九个逆序 ​

输入 $w=314265$。先独立求

$$\mathrm{Des}(w)=\{1,3,5\},\mathrm{maj}(w)=9,\mathrm{inv}(w)=4.$$

然后对每个新字母 $x$，检查当前像的末项：末项 $\le x$ 就在每个 $\le x$ 字母后切；否则在每个 $>x$ 字母后切。各块末项移到块首，再追加 $x$。六个状态是

$$3,31,314,3412,34126,634125.$$

两处真正变化必须会解释：追加二时 $314=3|14$ 变成 $3|41$，再接二；追加五时 $34126$ 只有末项大于五，所以整个词右旋为 $63412$，再接五。

输出 $634125$ 的右侧较小数是 $(5,2,2,0,0,0)$，所以确有九个逆序。输出只有两个下降，已经提醒我们：变换保持主指标到逆序的等式，却不保持下降总数。

任务二：恢复原词，并解释为什么对所有输入成立 ​

从 $634125$ 取走末项五。剩余首项六大于五，所以在每个大于五的字母前切，这次只有一块 $63412$；左旋得到 $34126$。反复操作，取出的末项依次为

$$5,6,2,4,1,3.$$

反读就是原词 $314265$。中间一步取走二后，$341$ 在三、四前切为 $3|41$，左旋恢复 $314$。逆向分支由 首项 决定，不能仍看末项。

证明要交出两个增量分支。旧前缀长为 $m$，块为 $U_j{y}_j$：

• 旧末项 $\le x$ 时，$U_j>x\ge y_j$，旋转删去 $\sum |U_j|$ 个逆序；追加 $x$ 恰补回同样数量，净增零
• 旧末项 $>x$ 时，$U_j\le x<y_j$，旋转增加 $\sum |U_j|$ 个逆序；追加再增加块数，合计 $m$

跨块相对次序不变。这恰好等于新下降是否发生时主指标的增量。每步又保持末字母，所以归纳条件可继续使用；逆算法则证明映射真是一一对应。仅展示这一个九等于九的例子，还不足以证明等分布。

任务三：重复字母、矩形分拆与 $q$ 系数 ​

输入重复词 $2112$，状态为 $2,21,121,1212$，主指标一成为像的一个逆序。等号须归入 $\le$ 分支。另有 $2121\mapsto 2211$，两边分别为主指标四和逆序四。

含两个零、两个一的六词 $0011,0101,0110,1001,1010,1100$，逆序数依次为 $0,1,2,2,3,4$，故

$${[\genfrac{}{}{0ex}{}{4}{2}]}_q=1+q+2q^2+q^3+q^4.$$

对每个零记录左边有几个一，再倒序作为分拆行长，得到二乘二矩形内的六种形状。比如 $1010$ 给 $(b_1,b_2)=(1,2)$，反向分拆 $(2,1)$ 面积三；用行长差恢复两零之间的一，编码可逆。

重数为 $(2,1,1)$ 时，先记录两个最小字母的位置，再在余下两种字母中选择次序：

$${[\genfrac{}{}{0ex}{}{4}{2,1,1}]}_q={[\genfrac{}{}{0ex}{}{4}{2}]}_q{[\genfrac{}{}{0ex}{}{2}{1}]}_q=1+2q+3q^2+3q^3+2q^4+q^5.$$

这是十二个不同词的逆序分布，也因 Foata 保持重数而是主指标分布。首项对应 $1123$，末项对应 $3211$；代 $q=1$ 得十二，代 $q=-1$ 得零。中间频数不能从互异排列频数逐项除以二获得。

有限乘积还要求正确的移位：$\prod _{i=0}^2(1+z{q}^i)$ 的 $z^2$ 系数为 $q+q^2+q^3=q{[\genfrac{}{}{0ex}{}{3}{2}]}_q$。最低幂一来自两个被选位置的最小和，不能丢掉 $q^{(\genfrac{}{}{0ex}{}{2}{2})}$。

任务四：同分布不能代替联合递推 ​

对 $u=3142$ 插入最大元五。末尾和两条下降缝保持下降数二，主指标增量为 $0,1,2$；最前和唯一本来上升的缝增加一个下降，增量为 $3,4$。因此这份旧词的贡献是

$$t^2{q}^4(1+q+q^2)+t^3{q}^4(q^3+q^4).$$

一般地，目标为 $k$ 个下降时得到

$$A_{n,k}(q)=[k+1{]}_q{A}_{n-1,k}(q)+q^k[n-k{]}_q{A}_{n-1,k-1}(q).$$

从空、一元素的初值开始，第四行是

$$A_4(t,q)=1+(3q+5q^2+3q^3)t+(3q^3+5q^4+3q^5)t^2+q^6{t}^3.$$

因此 $[t^2{q}^4]A_4=5$。$q=1$ 汇总为旧 Eulerian 多项式；$t=1$ 汇总为旧逆序 $q$ 阶乘。四阶恰一个下降的逆序分布却是 $3q+4q^2+3q^3+q^4$，不能用它替换 $t$ 的主指标系数。

生成函数证书还要说明空间：

$$\sum _{m\ge 0}[m+1{]}_q^n{t}^m=\frac{A_n(t,q)}{\prod _{j=0}^n(1-t{q}^j)}\text{在 }\mathbb{Z}[q][[t]].$$

固定一份词 $w$，把值递减、下降处严格的序列写为 $a_i-a_{i+1}=b_i+{\mathbf{1}}_{i\in \mathrm{Des}(w)}$，则最大值是 $\mathrm{des}(w)+\sum b_i$，总值是 $\mathrm{maj}(w)+\sum i{b}_i$。两个量分别产生 $t$ 与 $q$ 的权重，各个非负 $b_i$ 产生一个分母因子。固定 $t^m$ 只需有限个 $b$，所以换序合法。

测试 $n=3,m=1$：分母逆的一次 $t$ 系数为 $1+q+q^2+q^3$，加上分子一次项 $2q+2q^2$，得 $(1+q{)}^3$。这比只检验 $q=1$ 更能发现错误的权重方向。

任务五：交错标签的洗牌公式 ​

输入两词 $u=31,v=42$，保留各自内部顺序。六份洗牌是

$$3142,3412,3421,4312,4321,4231,$$

主指标依次为 $4,2,5,3,6,4$。因此

$$\sum _{w\in \mathrm{Sh}(31,42)}{q}^{\mathrm{maj}(w)}=q^2(1+q+2q^2+q^3+q^4).$$

这个起始指数二来自两条短词主指标之和。把两条词看成两条互不关联的标号链，各自非负赋值的总值生成函数独立相乘；将结果按所有线性扩张分解，公共分母约掉后就是 ${[\genfrac{}{}{0ex}{}{4}{2}]}_q$。证明允许两组标签交错，不必把第一组整体放到第二组下方。

若用逆序统计同样六词，得到 $q^3+q^4+3q^5+q^6$。若让两词共享同一个可见字母，$1$ 与 $1$ 只洗出无标签词 $11$，也不会得到 $1+q$。两个反例分别检查统计迁移和身份假设。

任务六：混合标号菱形的总值四 ​

取 $a<b<d$、$a<c<d$，$b,c$ 不可比，标号 $(a,b,c,d)=(3,1,4,2)$。反序赋值必须满足

$$\sigma (a)>\sigma (b)\ge \sigma (d),\sigma (a)\ge \sigma (c)>\sigma (d).$$

两条扩张词 $3142,3412$ 的主指标为四、二，所以

$$G(q)=\frac{q^2+q^4}{(1-q)(1-q^2)(1-q^3)(1-q^4)}.$$

总值四的三份赋值为 $(3,0,1,0),(2,0,2,0),(2,1,1,0)$。前两份属于 $3412$ 分支，最后一份属于 $3142$ 分支，稳定排序的平局规则使它们互不重复。

这说明分子的一项是每条扩张的最低总值，分母才负责可继续加入的所有差值。将 $q$ 设为四并不是“总值四”计数，必须取 $[q^4]$。

任务七：有限上限与负输入互反 ​

保持同一菱形偏序，改为数值只能取 $1,\dots ,m$ 的保序映射。使用自然标号 $(1,2,3,4)$，两份扩张下降数为零、一，于是

$$\mathrm{\Omega }(m)=(\genfrac{}{}{0ex}{}{m+3}{4})+(\genfrac{}{}{0ex}{}{m+2}{4})=\frac{m(m+1{)}^2(m+2)}{12}.$$

把自然标号逐个换成五减原标号，所有可比关系都变为严格，得到

$${\mathrm{\Omega }}^{\circ }(m)=(\genfrac{}{}{0ex}{}{m}{4})+(\genfrac{}{}{0ex}{}{m+1}{4})=\frac{m(m-1{)}^2(m-2)}{12}=\mathrm{\Omega }(-m).$$

弱两值计数是六：端点同值两份，端点为一、二时中间两个元素独立二选一，四份。严格四值计数也是六：端点 $(1,3),(2,4)$ 各一份，端点 $(1,4)$ 给四份。严格并不要求不可比的 $b,c$ 取不同值。

再做一个奇数检查：$a<b,a<c$ 的弱多项式是 $m(m+1)(2m+1)/6$，代 $-3$ 得负五，因此严格三值计数为五。负输入不是负数个时段，而是先证明多项式，再通过因子反号解释其值。

交卷边界与复算入口 ​

• $\mathrm{\Phi }$ 的逆过程先移走末字母，再看剩余首字母；一般不能再执行一次前向映射
• 相等字母归入 $\le$ 分支；空词所有统计为零，生成多项式为一
• Gaussian 商在 $q=1$ 或单位根处先化为多项式再代入，避免 $0/0$
• 主指标与逆序的边缘等分布不自动保持原下降集合、下降数或任意洗牌子类
• 偏序赋值只对可比对施加条件；平局标签顺序保证扩张分解唯一
• 有限上限计数、多项式负输入、形式总值级数是三个不同输出，须先说明所求对象

下载标准库精确检查器。它检查长度至七的全部排列及三字母词、Gaussian 递推与有限乘积、联合递推和生成函数系数、任意标签洗牌、小偏序以及旧下降集合的保权深化。脚本输出每组测试范围和本页中间结果；有限测试用于发现实现或算例错误，普遍定理仍由正文证明承担。

来源与定理位置见五个正式条目的参考资料。原有禁位、Stirling与阶乘差分路线继续在计数与基变换终点使用，不要求为了完成本页先重走它们。