序多项式与严格计数互反

形式陈述

设 $P$ 是 $n$ 元有限偏序。对整数 $m\ge0$ ，令 $\Omega_P(m)$ 数保序映射 $f:P\to[m]$ ，即 $x<_P y$ 时 $f(x)\le f(y)$ ；令 $\Omega_P^\circ(m)$ 数严格保序映射，即对同样的可比对要求 $f(x)<f(y)$ 。不可比元素可以取相同值，严格保序并不等于单射。

两者分别由有理系数多项式唯一延拓到任意输入 $z$ ，满足

\Omega_P^\circ(z)=(-1)^n\Omega_P(-z).

$n>0$ 时二者次数均为 $n$ ，首项系数都是 $e(P)/n!$ ，其中 $e(P)$ 是线性扩张数。空偏序有唯一空映射，两个多项式都等于一。

更精确地，选任一自然标号 $\omega:P\to[n]$ ，满足 $x<_P y\Rightarrow\omega(x)<\omega(y)$ 。沿标号偏序分拆的线性扩张集合 $\mathcal L(P,\omega)$ ，有

\Omega_P(z)=\sum_{w\in\mathcal L(P,\omega)} \binom{z+n-1-\operatorname{des}(w)}n,

\Omega_P^\circ(z)=\sum_{w\in\mathcal L(P,\omega)} \binom{z+\operatorname{des}(w)}n.

这里使用二项式多项式 $\binom zn=z(z-1)\cdots(z-n+1)/n!$ ，不能在负整数上把它按“组合越界”直接置零。计数解释只在 $m\ge0$ ，负值由多项式延拓解释。

直觉

若要求一条链的值弱增加，允许相邻元素同值；严格增加则把这些等号全部排除。一个一般偏序有许多线性扩张。稳定排序把赋值唯一放进其中一份，而扩张的下降告诉我们，需要多少次强制增加才能避免重复。

有限上限的扩张计数

以下证明取 $n\ge1$ ；空偏序已由唯一空映射单独处理。先把保序 $f$ 转为反序 $\sigma(x)=m+1-f(x)$ ，其值仍在 $[m]$ 。自然标号不添加严格关系，所以它正是值受限的 $(P,\omega)$ -分拆。固定扩张 $w$ ，写 $d=\operatorname{des}(w)$ ，沿扩张的值序列满足

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

令 $h_i$ 为从位置 $i$ 起到 $n-1$ 的下降数，置 $b_i=a_i-h_i$ 。得到

m-d\ge b_1\ge\cdots\ge b_n\ge1.

这是从 $m-d$ 个值中取 $n$ 项的可重复无序选取，数量为 $\binom{m-d+n-1}{n}$ ；反向加回 $h_i$ 恢复原序列。若 $m\le d$ 没有解，这时上参数在 $0,\ldots,n-1$ ，多项式的值也为零。对全部扩张求和证明第一式在所有非负整数上的计数解释。

互补标号交换严格与弱条件

用互补标号 $\bar\omega(x)=n+1-\omega(x)$ 。它在每个可比对上逆序，因此 $(P,\bar\omega)$ -分拆要求所有可比关系严格。每份原扩张词 $w$ 变为逐字取补的 $\bar w$ ；原上升变下降，所以

\operatorname{des}(\bar w)=n-1-\operatorname{des}(w).

用上一段相同的受限序列计数，得到第二个展开式。严格关系只施于偏序里的可比对，并没有把不可比元素变成必须不同。

两个展开式本来就是多项式，故给出存在性；任何两个候选多项式在无限多个非负整数上一致，差多项式只能为零，故延拓唯一。各项次数为 $n$ 、首系数为 $1/n!$ ，共有 $e(P)>0$ 项，于是度数及首项系数也确定。

最后逐项使用因子反号恒等式

(-1)^n\binom{-z+n-1-d}{n}=\binom{z+d}{n},

便得互反。这里的负输入把“允许等号”换成“可比对严格”，不是在数负数个可选时段。

例子与边界

取菱形偏序 $a<b<d$ 、 $a<c<d$ ， $b,c$ 不可比。自然标号为 $a,b,c,d\mapsto1,2,3,4$ ，两份扩张词为 $1234,1324$ ，下降数分别为零、一。所以

\begin{aligned} \Omega_P(z)&=\binom{z+3}{4}+\binom{z+2}{4} =\frac{z(z+1)^2(z+2)}{12},\\ \Omega_P^\circ(z)&=\binom z4+\binom{z+1}{4} =\frac{z(z-1)^2(z-2)}{12}. \end{aligned}

首系数 $1/12=2/4!$ 恢复两条线性扩张，但多项式同时数允许不同元素同值的更多赋值。

$m=2$ 时弱计数为六。独立按 $f(a),f(d)$ 分类：端点同为一或同为二，各一份；端点为一、二时，两个中间元素分别可取一或二，共四份，合计六。

$m=4$ 时严格计数也为六：端点 $(1,3)$ 或 $(2,4)$ 各给一份；端点 $(1,4)$ 时，中间 $b,c$ 独立取二或三，给四份。特别是 $f(b)=f(c)$ 允许。代数检查 $\Omega_P(-4)=6$ 与 $(-1)^4=1$ 一致。

奇数大小可见符号：三元素偏序 $a<b,a<c$ 给

\Omega(z)=\frac{z(z+1)(2z+1)}6,\qquad \Omega^\circ(z)=\frac{z(z-1)(2z-1)}6.

$\Omega(-3)=-5$ ，故严格三值赋值数为 $-\Omega(-3)=5$ 。直接枚举： $f(a)=1$ 时 $b,c$ 各可取二或三，给四份； $f(a)=2$ 时都只能取三，给一份。

对 $n$ 元链，两个多项式为 $\binom{z+n-1}n$ 与 $\binom zn$ ；对反链，二者都为 $z^n$ ，因为没有可比对需要严格。非空 $P$ 在 $m=0$ 时没有映射，空 $P$ 则始终有一份，不能把所有情形的常数项都设零。

推论与应用

有限容量调度与首项检查

把 $m$ 看作可用时段， $f(x)\le f(y)$ 容许依赖任务同一时段完成；严格版本要求真正分开，但不可比任务仍可并行。模型必须说明哪种约束符合应用。反序分拆只是把数值方向反过来的等价计数工具，不改变偏序依赖。

设最长链有 $h$ 个元素。严格映射存在当且仅当 $m\ge h$ ：必要性是链上需要 $h$ 个不同值；充分性可给每个元素赋“以它结尾的最长链长度”，沿严格比较至少增加一且最大值为 $h$ 。所以 $\Omega_P^\circ(0),\ldots,\Omega_P^\circ(h-1)$ 全为零，互反又给 $\Omega_P(0),\Omega_P(-1),\ldots,\Omega_P(-(h-1))$ 的零点。菱形 $h=3$ ，上面的因式 $z(z+1)^2(z+2)$ 正好包含这些根；根的额外重数不能只从高度读出。

不要把证明误当高效枚举承诺

扩张和最多有 $n!$ 项，正确并不表示对任意大偏序都易算。小偏序可枚举扩张后汇总下降数；若只有一个具体 $m$ ，也可直接对赋值或向下闭集作动态规划。只有给出明确状态空间和转移，才可比较成本。

多项式一般不是整系数，却对非负整数取整数；这是组合解释给出的整值性。更重要的是，计数多项式的恒等关系并不使两类对象逐个相同：菱形的 $m=2$ 弱计数和 $m=4$ 严格计数恰好都为六，而 $m=2$ 严格计数为零。互反联系的是同一多项式在相反输入处的值，不是一条“把所有赋值统一加一”的双射。

参考资料

Richard P. Stanley，“Combinatorial Reciprocity Theorems”，Advances in Mathematics 14 (1974), 194–253，§2，Proposition 2.1，印页197–200：弱、严格序多项式与互反。
Richard P. Stanley，Enumerative Combinatorics, Vol. 1，作者第二版书稿，§3.15.2–3.15.3，Theorem 3.15.8、Corollary 3.15.12，印页345–347：有界标号分拆和互补标号。本文改以二项式展开逐项反号给出完整有限证明。

形式陈述 ​

有限上限的扩张计数 ​

互补标号交换严格与弱条件 ​

有限容量调度与首项检查 ​

不要把证明误当高效枚举承诺 ​

反向链接

形式陈述

有限上限的扩张计数

互补标号交换严格与弱条件

有限容量调度与首项检查

不要把证明误当高效枚举承诺