计数组合学7.20（平面分拆与RSK算法)

7.20 平面分拆与RSK算法

我们现在已经发展了足够多的对称函数理论，可以给出一些计数应用。本节和接下来的两节将致力于讨论整数分拆的一个引人入胜的推广，称为“平面分拆”。一个平面分拆（plane partition）是一个非负整数数组 $\pi =({\pi }_{ij}{)}_{i,j\ge 1}$，满足 $\pi$ 具有有限支集（即只有有限多个非零项）且在行和列上弱递减。如果 $\sum {\pi }_{ij}=n$，那么我们记 $|\pi |=n$ 并称 $\pi$ 是 $n$ 的一个平面分拆。在书写平面分拆的例子时，0（或除有限个以外的所有0）被省略。因此，整数 $0\le n\le 3$ 的平面分拆由下式给出：

一个普通分拆 $\lambda ⊢n$ 可以看作是一个具有有限支集的非负整数的弱递减一维数组 $({\lambda }_1,{\lambda }_2,\dots )$。因此平面分拆是普通分拆在二维的自然推广。现在似乎很自然地可以为任意 $r\ge 1$ 定义 $r$ 维分拆。然而，对于 $r\ge 3$ 几乎没有任何重要结果。平面分拆与半标准杨表有明显的相似之处。实际上，一个反半标准杨表（reverse SSYT）就是一种特殊的平面分拆（移除了无关的0），事实上，在我们定义反半标准杨表时，我们提到了另一个术语“列严格平面分拆”。由于半标准杨表与平面分拆之间的相似性，对称函数在平面分拆的计数中扮演重要角色也就不足为奇了。

平面分拆 $\pi =({\pi }_{ij})$ 的一个部分（part）是一个正的项 ${\pi }_{ij}>0$。$\pi$ 的形状（shape）是一个普通分拆 $\lambda$，其中 $\pi$ 在第 $i$ 行有 ${\lambda }_i$ 个非零部分（所以 ${\pi }_{i{\lambda }_i}>0,{\pi }_{i,{\lambda }_i+1}=0$）。如果 $r=\ell (\lambda )$，我们说 $\pi$ 有 $r$ 行（rows）。类似地，如果 $s=\ell ({\lambda }^{\prime })={\lambda }_1$，则 $\pi$ 有 $s$ 列（columns）。记 ${\ell }_1(\pi )$ 为 $\pi$ 的行数，${\ell }_2(\pi )$ 为列数。最后用通常的公式 $\mathrm{tr}(\pi )=\sum {\pi }_{ii}$ 定义 $\pi$ 的迹（trace）。例如，平面分拆：

具有形状 (8, 6, 4)，18个部分，3行，8列，迹为14。

令 $\mathcal{P}(r,c)$ 为所有最多 $r$ 行和最多 $c$ 列的平面分拆的集合。例如，如果 $\pi \in \mathcal{P}(1,c)$，那么 $\pi$ 就是一个普通分拆，且 $\text{tr}(\pi )$ 是 $\pi$ 的最大部分。通过“观察”（观察共轭分拆 ${\pi }^{\prime }$ 而不是 $\pi$）可以清楚地看出：

$$\sum _{\pi \in \mathcal{P}(1,c)}{q}^{\text{tr}(\pi )}{x}^{|\pi |}=\frac{1}{(1-qx)(1-q{x}^2)\cdots (1-q{x}^c)}.\text{\hspace{1em}(7.98)}$$

本节的主要结果是以下方程 (7.98) 的推广。

7.20.1 定理

固定 $r,c\in \mathbb{P}$。则
$$\sum _{\pi \in \mathcal{P}(r,c)}{q}^{\text{tr}(\pi )}{x}^{|\pi |}=\prod _{i=1}^r\prod _{j=1}^c{\left(1-q{x}^{i+j-1}\right)}^{-1}.$$

证明. 我们将基于 RSK 算法以及一种将一对同形状的反半标准杨表合并成单个平面分拆的简单方法，给出一个优雅的双射证明。首先我们描述如何将两个具有互异部分且部分数相同的分拆 $\lambda$ 和 $\mu$ 合并成一个分拆 $\rho =\rho (\lambda ,\mu )$。画出 $\lambda$ 的 Ferrers 图，但每一行都从前一行的开头向右缩进一个空格。这样的图称为 $\lambda$ 的移位 Ferrers 图（shifted Ferrers diagram）。例如，如果 $\lambda =(5,3,2)$，那么我们得到移位图：

对 $\mu$ 做同样操作，然后转置该图。例如，如果 $\mu =(6,3,1)$，那么我们得到转置移位图：
外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
现在通过识别它们的主对角线将两个图合并成一个图。对于上面的 $\lambda$ 和 $\mu$，我们得到图（为清晰起见画出主对角线）：

定义 $\rho (\lambda ,\mu )$ 为一个分拆，使得这个合并图是其 Ferrers 图。上面的例子表明：
$$\rho (532,631)=544211.$$

映射 $(\lambda ,\mu )\mapsto \rho (\lambda ,\mu )$ 显然是具有 $k$ 个互异部分的分拆对 $(\lambda ,\mu )$ 与秩为 $k$ 的分拆 $\rho$（如 1.8 节和 7.2 节所定义）之间的双射。注意：
$$|\rho |=|\lambda |+|\mu |-\ell (\lambda ).$$

我们现在将上述双射扩展到同形状的反半标准杨表对 $(P,Q)$。如果 ${\lambda }^i$ 表示 $P$ 的第 $i$ 列，${\mu }^i$ 表示 $Q$ 的第 $i$ 列，那么令 $\pi (P,Q)$ 为一个数组，其第 $i$ 列是 $\rho ({\lambda }^i,{\mu }^i)$。例如，如果

容易看出 $\pi (P,Q)$ 是一个平面分拆。将 $\pi (P,Q)$ 的每一行取其共轭，得到另一个平面分拆 ${\pi }^{\prime }(P,Q)$。对于上面的 $\pi (P,Q)$，我们得到：

可以很容易地验证，映射 $(P,Q)\mapsto {\pi }^{\prime }(P,Q)$ 是同形状的反半标准杨表对 $(P,Q)$ 与平面分拆 ${\pi }^{\prime }$ 之间的双射。记 $\text{diag}({\pi }^{\prime })$ 为 ${\pi }^{\prime }$ 的主对角线 $({\pi }_{11}^{\prime },{\pi }_{22}^{\prime },\dots )$，$\max (P)$ 为反半标准杨表 $P$ 的最大部分 $P_{11}$，等等。回忆 $\text{sh}(P)$ 表示 $P$ 的形状，所以 $\text{sh}(P)=\text{sh}(Q)$，其中 $P,Q$ 如上所述。容易看出：
$$|{\pi }^{\prime }|=|P|+|Q|-|\text{sh}(P)|\text{\hspace{1em}(7.99)}$$
$$\text{diag}({\pi }^{\prime })=\text{sh}(P)=\text{sh}(Q),\text{所以}\text{tr}({\pi }^{\prime })=|\text{sh}(P)|$$
$${\ell }_1({\pi }^{\prime })=\max (Q)$$
$${\ell }_2({\pi }^{\prime })=\max (P).$$

现在令 $A=(a_{ij})$ 是一个具有有限支集的 $\mathbb{N}$-矩阵。我们希望将 $A$ 与一对同形状的反半标准杨表相关联。这可以通过 RSK 算法的一个明显变体来完成，其中我们在定义行插入时反转了 $\le$ 和 $\ge$ 的角色。等价地，如果 $w_A=\left(\genfrac{}{}{0ex}{}{u_1\cdots u_n}{v_1\cdots v_n}\right)$ 是与 $A$ 关联的双行数组，那么将普通的 RSK 算法应用于双行数组 $\left(\genfrac{}{}{0ex}{}{-u_n\cdots -u_1}{-v_n\cdots -v_1}\right)$（其条目现在是负整数），然后将这对半标准杨表的所有条目的符号改回正号。我们将得到一对反半标准杨表 $(P,Q)$，满足：
$$|P|=\sum _{i,j}j{a}_{ij}\text{\hspace{1em}(7.100)}$$
$$|Q|=\sum _{i,j}i{a}_{ij}$$
max⁡(P)=max⁡{j:aij≠0}\max(P) = \max\{j : a_{ij} \neq 0\}max(P)=max{j:aij​=0}
max⁡(Q)=max⁡{i:aij≠0}\max(Q) = \max\{i : a_{ij} \neq 0\}max(Q)=max{i:aij​=0}
$$|\text{sh}(P)|=|\text{sh}(Q)|=\sum a_{ij}.$$

由以 (7.99) 和 (7.100) 开始的方程组可知，如果 ${\mathcal{M}}_{rc}$ 是所有 $r\times c$ $\mathbb{N}$-矩阵的集合，那么：
$$\sum _{\pi \in \mathcal{P}(r,c)}{q}^{\text{tr}(\pi )}{x}^{|\pi |}=\sum _{A=(a_{ij})\in {\mathcal{M}}_{rc}}{q}^{\sum a_{ij}}{x}^{\sum (i+j)a_{ij}-\sum a_{ij}}$$
$$=\prod _{i=1}^r\prod _{j=1}^c\left(\sum _{a_{ij}\ge 0}{q}^{a_{ij}}{x}^{(i+j-1)a_{ij}}\right)$$
$$=\prod _{i=1}^r\prod _{j=1}^c{\left(1-q{x}^{i+j-1}\right)}^{-1}.$$

现在令 $\mathcal{P}(r)$ 表示所有最多 $r$ 行的平面分拆的集合。如果在定理 7.20.1 中令 $q=1$ 且 $c\to \infty$，那么我们得到 $\mathcal{P}(r)$ 中元素的以下优雅计数。

7.20.2 推论

固定 $r\in \mathbb{P}$。则
$$\sum _{\pi \in \mathcal{P}(r)}{x}^{|\pi |}=\prod _{i\ge 1}{\left(1-x^i\right)}^{-\min \left(i,r\right)}.\text{\hspace{1em}(7.101)}$$

证明. 定理 7.20.1 给出：
$$\sum _{\pi \in \mathcal{P}(r)}{x}^{|\pi |}=\prod _{i=1}^r\prod _{j\ge 1}{\left(1-x^{i+j-1}\right)}^{-1},$$
容易看出这与 (7.101) 的右侧一致。 □

最后令 $\mathcal{P}$ 表示所有平面分拆的集合，并在推论 7.20.2 中令 $r\to \infty$，得到平面分拆理论中的原型结果：

7.20.3 推论

我们有
$$\sum _{\pi \in \mathcal{P}}{x}^{|\pi |}=\prod _{i\ge 1}{\left(1-x^i\right)}^{-i}.$$

当我们考虑 RSK 算法的对称性结果定理 7.13.1 时，定理 7.20.1 的一个很好的变体就出现了。定义一个平面分拆 $\sigma =({\sigma }_{ij})$ 是对称的（symmetric），如果对所有 $i,j$ 有 ${\sigma }_{ij}={\sigma }_{ji}$。令 $\mathcal{S}(r)$ 表示所有最多 $r$ 行（因此也最多 $r$ 列）的对称平面分拆的集合。

7.20.4 定理

固定 $r\in \mathbb{P}$。则
$$\sum _{\sigma \in \mathcal{S}(r)}{q}^{\mathrm{tr}(\sigma )}{x}^{|\sigma |}=\prod _{i=1}^r{\left(1-q{x}^{2i-1}\right)}^{-1}\cdot \prod _{1\le i<j\le r}{\left(1-q^2{x}^{2(i+j-1)}\right)}^{-1}.$$

第一个证明. 令 ${\pi }^{\prime }(P,Q)$ 是定理 7.20.1 证明中描述的平面分拆。容易看出 ${\pi }^{\prime }$ 是对称的当且仅当 $P=Q$。此外，假设 $A\stackrel{{\text{RSK}}^{\prime }}{\to }(P,Q)$，其中 ${\text{RSK}}^{\prime }$ 也是在定理 7.20.1 证明中描述的“反向”RSK 算法（所以 $P$ 和 $Q$ 是反半标准杨表）。定理 7.13.1 同样适用于 ${\text{RSK}}^{\prime }$，所以 $A\stackrel{{\text{RSK}}^{\prime }}{\to }(P,P)$ 当且仅当 $A=A^{\prime }$。令 ${\mathcal{M}}_r^{\prime }$ 是所有 $r\times r$ 对称 $\mathbb{N}$-矩阵的集合。然后我们完全类似于定理 7.20.1 的证明，得到：

第二个证明. 有一个巧妙的替代证明避免了使用定理 7.13.1。假设 $\pi$ 是一个只有奇数部分的反半标准杨表。因此 $\pi$ 的每一列都是互异奇数部分的分拆。命题 1.8.4 的证明给出了 $n$ 的具有互异奇数部分的分拆与 $n$ 的自共轭分拆之间的双射。将此双射应用于 $\pi$ 的每一列，然后取每一行的共轭，产生一个对称平面分拆 $\sigma$。一个例子由下式给出：

可以容易地验证 $|\pi |=|\sigma |$，$\text{sh}(\pi )=\text{diag}(\sigma )$，$|\text{sh}(\pi )|=\text{tr}(\sigma )$，以及 ${\ell }_1(\sigma )=\frac{1}{2}(1+\max (\pi ))$。因此由推论 7.13.8 可得：
$$\sum _{\sigma \in \mathcal{S}(r)}{q}^{\text{tr}(\sigma )}{x}^{|\sigma |}=\prod _{\begin{array}{c}i=1\\ i\text{ odd}\end{array}}^{2r-1}(1-x_i{)}^{-1}\cdot \prod _{\begin{array}{c}1\le i<j\le 2r-1\\ ij\text{ odd}\end{array}}(1-x_i{x}_j{)}^{-1}{|}_{x_i=q{x}^i}$$
$$=\prod _{i=1}^r{\left(1-q{x}^{2i-1}\right)}^{-1}\cdot \prod _{1\le i<j\le r}{\left(1-q^2{x}^{2(i+j-1)}\right)}^{-1}.\square$$

令 $q=1$ 且 $r\to \infty$，得到所有 $n$ 的对称平面分拆的以下优雅计数。

7.20.5 推论

令 $\mathcal{S}$ 为所有对称平面分拆的集合。则
$$\sum _{\sigma \in \mathcal{S}}{x}^{|\sigma |}=\prod _{i\ge 1}\frac{1}{\left(1-x^{2i-1}\right){\left(1-x^{2i}\right)}^{[i/2]}}.$$