Gaussian 二项式与多重集加权计数

形式陈述

令 $q$ 为形式变量， $n\ge0$ 、 $0\le k\le n$ 。Gaussian 二项式系数定义为有限加权计数多项式

{n\brack k}_q=\sum_wq^{\operatorname{inv}(w)},

其中 $w$ 取遍含 $k$ 个零、 $n-k$ 个一的不同词，逆序是一个一出现在一个零前的 位置对。规定越界 $k$ 时为零。设 $[j]_q=1+q+\cdots+q^{j-1}$ （ $j\ge1$ ）、 $[0]_q!=1$ 、 $[n]_q!=\prod_{j=1}^n[j]_q$ ，则

{n\brack k}_q={n-1\brack k}_q+q^{n-k}{n-1\brack k-1}_q, \qquad {n\brack k}_q=\frac{[n]_q!}{[k]_q![n-k]_q!}.

递推用于 $n\ge1$ ，边界 ${n\brack0}_q={n\brack n}_q=1$ 。商式先在 $\mathbb Q(q)$ 中读，定义则已经保证结果属于 $\mathbb Z_{\ge0}[q]$ 。 $q=1$ 时恢复普通二项式系数。

更一般地，字母 $1<\cdots<r$ 分别出现 $a_1,\ldots,a_r$ 次，总长 $n$ ，则

\sum_{w\in R(a_1,\ldots,a_r)}q^{\operatorname{inv}(w)} ={n\brack a_1,\ldots,a_r}_q :=\frac{[n]_q!}{\prod_i[a_i]_q!}.

零重数允许，空词贡献一。这里逆序只使用严格大于；把相等位置也计入会改变权重。

直觉

普通二项式只问零出现在哪些位置。加上 $q$ 后，每份词还携带“一在零前”的对数，因而同一个总数被分解为一张精细分布。它不是把普通阶乘任意替换成带 $q$ 的式子后再猜组合含义。

最后一个字母给出递推

最后是一，删去它不改变逆序，留下 $n-1$ 位、 $k$ 个零。最后是零，删去它恰减少 $n-k$ 个逆序，因为每个一都在它前面。两类不交且删字可逆，给出递推。

验证商式时记 $Q_{n,k}=[n]_q!/([k]_q![n-k]_q!)$ 。对内部下标，用共同因子 $[n-1]_q!/([k]_q![n-k]_q!)$ 提出后，递推右边剩下

[n-k]_q+q^{n-k}[k]_q=[n]_q.

因此 $Q$ 满足同一递推与边界，归纳即等于定义的多项式。分母整除性是证明的结论，不是未说明的前提。

零左边的一变成分拆行长

从左到右编号第 $j$ 个零，记它左边的一的数量为 $b_j$ 。则

0\le b_1\le\cdots\le b_k\le n-k,\qquad \operatorname{inv}(w)=\sum_jb_j.

反向知道这些数，就在第一个零前放 $b_1$ 个一，相邻零之间放 $b_{j+1}-b_j$ 个一，最后放 $n-k-b_k$ 个一，唯一恢复词。把 $b$ 倒序得到分拆 $\lambda=(b_k,\ldots,b_1)$ ，删去尾零后，其 Ferrers 图装在 $k\times(n-k)$ 矩形中。图的格子数恰等于逆序数。这一可逆对应证明

{n\brack k}_q=\sum_{\lambda\subseteq k\times(n-k)}q^{|\lambda|}.

矩形限制同时控制部分数和最大部分，不能用无限制分拆生成乘积替代。

例子与边界

$n=4,k=2$ 的六份词依次为

\begin{array}{c|rrrrrr} w&0011&0101&0110&1001&1010&1100\\\hline \operatorname{inv}(w)&0&1&2&2&3&4 \end{array}

所以 ${4\brack2}_q=1+q+2q^2+q^3+q^4$ 。对应分拆为 $\varnothing,(1),(2),(1,1),(2,1),(2,2)$ ；中间系数二来自两个不同形状。

六个二乘二矩形内分拆按面积零至四排列，中间两种形状均为面积二 — 同一面积可以有不同分拆

重数 $(2,1,1)$ 的词则有

{4\brack2,1,1}_q=[3]_q[4]_q =1+2q+3q^2+3q^3+2q^4+q^5.

例如最高项对应 $3211$ ，五个逆序分别来自三与两个一、二，以及二与两个一。总系数十二恢复 $4!/2!$ 。这不是直接将互异排列的每个逆序频数都除以 $2!$ ；重复字母的标号顺序可能贡献不同逆序，不能逐系数作普通除法。

在 $q=1$ 时应对多项式求值；若把 $[j]_q$ 写成 $(1-q^j)/(1-q)$ ，原样代一会得到人为的 $0/0$ 。其他单位根也可能使商式的分子分母同时为零，仍须先约为多项式或用递推求值。例如 ${4\brack2}_{-1}=2$ 。 $q=0$ 时常数项为一，对应唯一非降词；负或复 $q$ 可以代数求值，却不能直接解释为非负概率权重。

推论与应用

重数分解与加权对称性

给一般重排词 $w$ ，保留全部最小字母的位置，将其余字母统一改记为一、最小字母记为零；另删去最小字母，得到词 $v$ 。这两份数据唯一恢复 $w$ 。前一二元词统计所有涉及最小字母的逆序， $v$ 统计其余逆序，所以权重相乘。反复执行得到

{n\brack a_1}_q{n-a_1\brack a_2}_q\cdots {a_r\brack a_r}_q,

阶乘约去后便是主公式。 $q=1$ 的结果是既有多项式系数，本页新增的是逐逆序权重的分解证书。

反转一个二元词，把每个零一异类对的先后交换，故

{n\brack k}_q=q^{k(n-k)}{n\brack k}_{q^{-1}}.

这证明次数、首末系数与系数回文性。再结合“反转并交换零一”，得到 ${n\brack k}_q={n\brack n-k}_q$ 。多重集相应的最高次数为 $\sum_{i<j}a_i a_j$ ，因为相同字母永不形成逆序。

有限 $q$ 二项式定理

从有限乘积每项选择 $1$ 或 $zq^i$ ，得到

\prod_{i=0}^{n-1}(1+zq^i) =\sum_{k=0}^nq^{k(k-1)/2}{n\brack k}_qz^k.

证明那个额外指数：选出零起点位置 $0\le i_1<\cdots<i_k<n$ ，把选中位置记为零，其余为一。这份词的逆序数为 $\sum_{j=1}^k(i_j-(j-1))$ ，而选项乘积指数为 $\sum_ji_j$ ，恰多出 $k(k-1)/2$ 。这是有限多项式恒等式，不涉及无限乘积收敛。

对 $n=3$ ， $z^2$ 系数为 $q+q^2+q^3=q{3\brack2}_q$ ；漏掉 $q^{\binom k2}$ 会把最低次幂错误移到零。

Foata 第二变换保持每个字母重数，所以主公式也等于同一重排类的 $\sum_wq^{\operatorname{maj}(w)}$ 。但进一步限制下降总数时，不能凭这个单变量结论交换主指标和逆序；联合分布需要额外论证。

参考资料

Richard P. Stanley，Enumerative Combinatorics, Vol. 1，作者第二版书稿，§1.7，式1.66–1.70、Proposition 1.7.1，印页62–64： $q$ 多项式系数与多重集逆序分解；§1.7，Proposition 1.7.3，印页65–67：矩形内分拆与 $q$ 二项式。
NIST DLMF，§26.9：有限矩形分拆与 Gaussian 多项式；§26.16：多重集排列的对象约定。有限乘积、分拆编码及全部小例在正文另作可逆证明。

形式陈述 ​

最后一个字母给出递推 ​

零左边的一变成分拆行长 ​

重数分解与加权对称性 ​

有限 q 二项式定理 ​

反向链接

形式陈述

最后一个字母给出递推

零左边的一变成分拆行长

重数分解与加权对称性

有限 $q$ 二项式定理