标号偏序分拆与主指标生成函数

形式陈述

设 $P$ 是有 $n$ 个元素的有限偏序集， $\omega:P\to[n]$ 是双射标号。一个 $(P,\omega)$ -分拆是函数 $\sigma:P\to\mathbb N$ ，这里 $\mathbb N=\{0,1,\ldots\}$ ，满足

x<_P y\Longrightarrow \sigma(x)\ge\sigma(y),

x<_P y\text{ 且 }\omega(x)>\omega(y) \Longrightarrow \sigma(x)>\sigma(y).

它是反序的数值赋值；标号只决定哪些比较必须严格，标号自身不必保序。重命名实际元素并同步搬动标号不改变对象，改变标号的相对大小则可能改变对象。

令 $\mathcal L(P,\omega)$ 为所有线性扩张的标号词：按与 $P$ 相容的先后次序列出所有元素，再读出其标号。每个词 $w$ 使用主指标。记 $|\sigma|=\sum_{x\in P}\sigma(x)$ ，则

G_{P,\omega}(q):=\sum_\sigma q^{|\sigma|} =\frac{\displaystyle\sum_{w\in\mathcal L(P,\omega)}q^{\operatorname{maj}(w)}}{\displaystyle\prod_{i=1}^n(1-q^i)}.

这是 $\mathbb Z\llbracket q\rrbracket$ 中的形式等式；固定总和只有有限多份非负整数赋值。 $P=\varnothing$ 时，空赋值、空线性扩张和空积都贡献一。

直觉

偏序只约束部分元素，尚未形成一条便于逐项求和的链。关键是根据赋值本身选择唯一的线性扩张，而不是把一份赋值重复放到每条可能的扩张里。

将元素按 $\sigma$ 值递减排列，相等值按 $\omega$ 递增，读成 $w$ 。若 $x<_P y$ ，则 $\sigma(x)\ge\sigma(y)$ ；严格大于使 $x$ 先出现，相等时严格规则迫使 $\omega(x)<\omega(y)$ ，也使 $x$ 先出现。所以得到的次序必是线性扩张。

沿此扩张，数值 $a_i=\sigma(\omega^{-1}(w_i))$ 满足

a_1\ge\cdots\ge a_n\ge0, \qquad a_i>a_{i+1}\text{ 当 }i\in\operatorname{Des}(w).

反过来，给定线性扩张 $w$ 及这种数值序列，便恢复唯一赋值。对 $x<_P y$ ，它们在扩张中位于 $i<j$ ，所以数值反序。若标签 $w_i>w_j$ ，区间 $i,\ldots,j$ 至少有一个相邻下降，否则整个标签区间会递增，矛盾；该下降处的严格数值关系便保证 $\sigma(x)>\sigma(y)$ 。相等数值段内部标签递增，所以稳定排序回去也恰是原词。

因此整个赋值集合按线性扩张 不交分解。固定一份 $w$ ，置 $a_{n+1}=0$ ，令

c_i=a_i-a_{i+1}-\mathbf1_{\{i\in\operatorname{Des}(w)\}}\ge0.

这些差值可以独立取任意非负整数，并唯一恢复 $a$ ，而

\sum_i a_i=\operatorname{maj}(w)+\sum_{i=1}^n i c_i.

于是每份扩张的生成函数为 $q^{\operatorname{maj}(w)}\prod_i(1-q^i)^{-1}$ 。相加证明主公式；分母来自非负差值，分子来自强制严格的单位差。

例子与边界

取四元素菱形偏序

a<_P b<_P d,\qquad a<_P c<_P d,

其中 $b,c$ 不可比；标号为 $\omega(a)=3,\omega(b)=1,\omega(c)=4,\omega(d)=2$ 。约束是

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

传递比较 $a<_P d$ 的严格性也已由这些不等式保证。两条线性扩张的词为 $3142,3412$ ，主指标分别为四、二，因此

G_{P,\omega}(q)=\frac{q^2+q^4}{(1-q)(1-q^2)(1-q^3)(1-q^4)}.

同一菱形偏序的混合标号、两条线性扩张，以及下降处严格导致的最小赋值 — 标号决定严格关系，两份扩张分开计数

赋值 $(\sigma(a),\sigma(b),\sigma(c),\sigma(d))=(1,0,1,0)$ 总和二，稳定排序为 $a,c,b,d$ ，词为 $3412$ 。另一份 $(2,1,1,0)$ 总和四，两个值一的标签按 $1<4$ 排列，得到 $3142$ 。两个最小赋值对应分子的两项，不是说总和四只有后一份： $q^2$ 分支也能通过增加差值到达总和四。

例如 $q^4$ 系数是三。总和四时可直接列出

(3,0,1,0),\quad(2,0,2,0),\quad(2,1,1,0).

生成式也给 $q^2$ 分支的二阶分拆数二，再加 $q^4$ 分支的一，得到三。

若所有标号顺着偏序增加，严格条件为空，得到普通反序映射；若每个可比对的标号都反向，则所有可比对必须严格。不可比元素即便标签一大一小，也没有被强加严格关系。把上例 $b,c$ 误当可比会删掉合法赋值和一条扩张。

标号必须互异，才能用相等数值时的标签顺序唯一打平。词有重复符号的重排定理不能无说明地替换这里的双射标号；若用相同标签，会丢失两份不同元素的排序证据。

推论与应用

任意互异标签的洗牌主指标公式

设 $u,v$ 是两条内部无重复且标签集合不交的词，长度分别为 $r,s$ 。它们的洗牌集合 $\operatorname{Sh}(u,v)$ 保留各词内部的先后顺序，但允许交错。则

\sum_{w\in\operatorname{Sh}(u,v)}q^{\operatorname{maj}(w)} =q^{\operatorname{maj}(u)+\operatorname{maj}(v)}{r+s\brack r}_q.

这里的Gaussian 二项式记录交错的加权分布。并不要求 $u$ 的每个标签都小于 $v$ ；只需统一的全序及互异性。若标签不是 $[r+s]$ ，先保序压成秩，不改变任何下降。

证明是把 $u$ 、 $v$ 各看作一条链，偏序为两链的不交并。链内标号依次就是词中的标签。这一偏序的线性扩张正是所有洗牌。两条链上的赋值完全独立，所以总值生成函数相乘，得到

\frac{q^{\operatorname{maj}(u)}}{\prod_{i=1}^r(1-q^i)} \frac{q^{\operatorname{maj}(v)}}{\prod_{j=1}^s(1-q^j)} =\frac{\sum_{w\in\operatorname{Sh}(u,v)}q^{\operatorname{maj}(w)}}{\prod_{k=1}^{r+s}(1-q^k)}.

乘回公共分母，剩下的商就是 Gaussian 系数，完成公式。

取 $u=31,v=42$ 。六份洗牌及主指标为

3142:4,\quad3412:2,\quad3421:5,\quad 4312:3,\quad4321:6,\quad4231:4.

总和 $q^2+q^3+2q^4+q^5+q^6=q^2{4\brack2}_q$ ，起始因子来自两条短词各有主指标一。若错误删去它，会把最小主指标从二改成零。

相同集合的逆序多项式却为 $q^3+q^4+3q^5+q^6$ ，不等于上式。Foata 双射不保证任意洗牌集合封闭；“全体排列等分布”不能用来替代这里的偏序证明。若两词共享相同可见字母，例如 $u=v=1$ ，无标签洗牌只有词 $11$ 一份，而右侧为 $1+q$ ；明确区分元素身份是不可省略的条件。

从无限总值到有限上限

主公式按总值统计所有非负赋值。若问题改为“每个值只能取 $1,\ldots,m$ ，一共有多少份”，可由序多项式与严格计数互反沿每条扩张数受限弱递减序列。上限计数与总值生成函数保存的参数不同；不能把 $q=m$ 代入本页生成函数冒充有限上限答案。

参考资料

Richard P. Stanley，Enumerative Combinatorics, Vol. 1，作者第二版书稿，§3.15.1–3.15.2，Definition 3.15.1、Lemmas 3.15.3–3.15.4、Theorems 3.15.5及3.15.7，印页341–345：不交扩张分解及主指标生成式。本页单独写出反向严格性的区间下降论证。
Richard P. Stanley，“Combinatorial Reciprocity Theorems”，Advances in Mathematics 14 (1974), 194–253，§5：标号偏序分拆与生成函数。洗牌应用在正文由两链不交并完整推出。

形式陈述 ​

任意互异标签的洗牌主指标公式 ​

从无限总值到有限上限 ​

反向链接

形式陈述

任意互异标签的洗牌主指标公式

从无限总值到有限上限