杨氏矩阵

· · 个人记录

基础知识

大部分内容摘自 OI Wiki

杨图

杨图是一个有限的框或单元格集合，左对齐排列，按行长非递增的顺序排列。

把杨图每行的格数列出，则得到一个总格数 n 的整数分拆 \lambda，因此一个杨图对应一个整数分拆 \lambda。我们可以将杨图的形状视为 \lambda，则一个杨图 \lambda=(\lambda_1,\lambda_2,\lambda_3,\ldots)，其中 \lambda_i 为第 i 行的格数。

杨图中每个格子的位置都由行列两个坐标决定。行坐标的顺序为格数从多到少，列坐标的顺序为从左往右。习惯上，杨图存在英式和法式两种画法：英式画法中，一行的格数大于等于下一行的格数，即 \forall i<k，有 \lambda_i\ge\lambda_{i+1}；法式画法中，一行的格数小于等于下一行的格数，即 \forall i<k，有 \lambda_i\le\lambda_{i+1}。例如，\lambda=(5,4,1) 时的两种杨图画法如下：

本博客中一致使用英式画法。

杨表

用取自某个符号表的符号填充杨图的框，即可得到一个杨表。通常填入杨表的是一个全序集和。填入杨表的元素记作 x_1,x_2,x_3,\ldots，但方便起见，通常用正整数来代替。

大多数情况下，杨图中填入的数字为 1 到 n，且各行、列中的数单调递增，这样的杨表被称为标准杨表。

由杨表中每个数字出现的次数产生的序列称为杨表的权重。容易发现对于一个标准杨表，它的权重为 (1,1,1,\ldots)。

RSK 插入算法

RSK 插入算法得名于其由 Robinson、Schensted 和 Knuth 共同提出，它可以将杨表与排列联系起来，使杨表直观地表现出排列地性质。

将 x 从某一行插入一个杨表 S 中记为 S\gets x，具体过程如下：

  1. 在当前所在行中找到最小的比 x 大的 y。

  2. 如果这样的 y 存在，则交换 x,y，将 x 插入下一行。

  3. 否则将 x 放在该行末尾并结束，此时 x 的坐标 (s,t) 满足 (s+1,t) 和 (s,t+1) 在杨表中都不存在。

例如，使用 RSK 插入算法将 3 插入杨表 S=\begin{bmatrix}2&5&9\\6&7\\8\end{bmatrix} 中的步骤如下：

第一张和第六张图为算法开始前和算法结束时 S 的状态。中间四张图中，红色为此次被更改的值，蓝色为之前被更改的值。

应用

勾长

给定一个共 n 个格子的杨表 \pi_\lambda，把 1 到 n 填入杨表中，使该杨表从左到右，从下到上都是递增的，记可以这样填的方案数为 \text{dim}_{\pi_\lambda}。

对于一个格子 x\in Y_\lambda，定义其勾长 \text{hook}(v) 的值为右边的方格数加上下边的方格数再加自己本身 1。

勾长公式

勾长公式如下：

\text{dim}_{\pi_\lambda}=\dfrac{n!}{\prod\limits_{x\in Y(\lambda)}\text{hook}(x)}

其中 n 为总格数。

例如 \lambda=(5,4,1) 时，其各个格子的勾长如下图所示：

此时

\text{dim}_{\pi_\lambda}=\dfrac{10!}{7\times5\times4\times3\times1\times5\times3\times2\times1\times1}=288

即这个形状的杨表有 288 种填法。

详细证明请见 大佬的知乎。

Robinson-Schensted correspondence 定理

对于一个杨表，使用一个新杨表记录杨表中每个格子被填上数的时间，通过这两个杨表，即可还原填入数字的顺序。

对于任意一对形态相同的杨表，都可以还原出唯一一个序列，一个序列也只能产生唯一一对杨表，即总格数为 n 的杨表对与长度为 n 的序列形成双射。

Robinson-Schensted correspondence 定理还指出：

n!=\sum\limits_{\lambda\vdash n}f_\lambda^2

其中 \lambda\vdash n 是一个 n 的整数拆分，f_\lambda 是该整数拆分的填法数量。

例题

P4484 [BJWC2018] 最长上升子序列

题意

求长度为 n 的随机排列的 LIS 长度的期望。

数据范围：1\le n\le 28。

解法

思路来自 EI 大佬的题解。

由 RSK 插入算法的过程可知，一个序列顺次插入，得到的杨表的第一行格数就是该序列的 LIS 长度。对于一个 n 个数的排列 A，它的 LIS 就是 \lambda_1，那么 n 的全排列的 LIS 的期望为

\dfrac{\sum\limits_{A}\lambda_1}{n!}

Robinson-Schensted correspondence 定理指出，总格数为 n 的杨表对与长度为 n 的序列形成双射，因此我们要求的是

\dfrac{\sum\limits_{\lambda\vdash n}f_\lambda^2\lambda_1}{n!}

因此只需要暴力搜出所有 n 整数拆分，就能得到所有合法杨表的形状，再用勾长公式即可在 \Theta(n) 的时间复杂度内计算一个形状的杨表的填法数量，也即其所对应的排列数量。

时间复杂度为 \Theta(np(n))，其中 p(n)\sim\dfrac{\sqrt3}{12n}\exp\left(\dfrac{\sqrt{6n}\pi}{3}\right)。这是一个效率相当优秀的亚指数级算法，实际上能够胜任 1\le n\le 60 的数据范围。