杨表学习笔记

x义x · 2020-09-14 20:32:52 · 个人记录

参考资料：论文集2019《浅谈杨氏矩阵在信息学竞赛中的应用》袁方舟，《对称群笔记》Wenchao Zhang。

引入

杨图，杨表，勾长公式

杨图（记为 \lambda）大概就是一个长成这样的东西：

每行的列数称为 \lambda_i。\lambda_i 单调不增，和为 n，称为 \lambda\vdash n。

你要往里面填 1...|\lambda| 的排列，使得行单调增列单调增，这样的一种填充称为标准杨表。杨表数量由下面的勾长公式给出。

设 \text{hook}(p) 是杨图中格子 p 的勾长，等于其下方格子个数+右方格子个数+1。

标准杨表总数为
f_{\lambda}=\dfrac{|\lambda|!}{\prod_{p\in \lambda}\text{hook}(p)}

半标准杨表，勾长公式

即行不严格递增，列严格递增的杨表。

设值域为 r，半标准杨表数为

\prod_{p\in\lambda}\dfrac{r+p_y-p_x}{\text{hook}(p)}

斜杨图

即从一个杨图 \lambda 中扣掉另一个杨图 \mu。不连通也没关系。

一个兴奋图（~~写出这个东西的英文名可能导致寿命减少~~）是指，\mu 经过一系列的兴奋运动形成的 \lambda 的某个子集。对 \mu 的兴奋运动是指，将一个下方右方右下方都属于 \lambda/\mu 的属于 \mu 的方格移动到其右下方。

如图是 \mu 的所有可能的兴奋图。记为 \mathcal{E}(\lambda/\mu)。如下是勾长公式。

|\lambda/\mu|!\sum_{D\in\mathcal E{(\lambda/\mu)}}\prod_{p\in \lambda/D}\dfrac{1}{\text{hook}_{\lambda}(p)}

RSK 算法，杨表与 LIS 问题

下面我们将揭示杨图和排列的深刻联系。先引入 \text{RSK} 算法。

RSK 算法

行插入

定义 P\leftarrow x 是把 x 从第一行行插入进近似标准杨表（即填入的元素不必是 1...|\lambda|）P 中。流程如下：

找到本行最小的比 x 大的数 y。如果找不到这样的 y，则把 x 放在本行末尾并结束算法。

交换 x,y。将 y 行插入下一行。

如下演示了一个行插入过程。

显然最后新增的格子一定在边角，即其下方和右方都没有格子。

对于对 P 的第 i 插入，在另一个杨表 Q 中在新增的格子上写上 i（注意不是插入）。显然 Q 是标准杨表。我们称 P 为插入表，Q 为记录表。

删除

下面定义从 P 中删除格子 p。尽管看起来不必要，我们还是规定 p 必须是边角。记 p 中填的数是 x。流程如下：

如果这是第一行，结束算法。

找到上一行最大的比 x 小的数 y（显然一定存在）

交换 x,y，移到上一行继续算法。

结束算法后删掉已经没有数的格子 p。

如下演示了一个删除过程。

很明显删除就是行插入的逆操作。

考虑一个 1...n 的排列，依次插入即可得到两个杨表 (P,Q)；给定 (P,Q)，显然 Q 中最大元素一定在边角，于是我们可以按 Q 的指导去删除 P 来还原原来的排列。

于是也就得到了以下的Robinson–Schensted correspondence：

上述算法构成了 (P,Q) 到 S_n 的一一映射。也就是说，
\sum_{\lambda\vdash n}f_{\lambda}^2=n!

不禁让人联想到 prüfer 序列。

同时对于置换（当然也是排列）\pi\rightarrow (P,Q)，我们有 \pi^{-1}\rightarrow(Q,P)，从而每一个标准杨表 P 对应一个对合，即逆等于自身的置换。对对合计数，我们得到：

\sum_{\lambda\vdash n}f_{\lambda}=\sum_{k=0}^{\lfloor n/2\rfloor}{n\choose 2k}(2k-1)!!
其中双阶乘 (2k-1)!! 定义为 (2k-1)(2k-3)...3\cdot 1。

RSK 算法和半标准杨表

一个广义置换大概可以理解为可重集上的置换，比如

\begin{pmatrix}1&1&2&2&2&3\\1&3&1&2&2&2\end{pmatrix}

它对应一个广义置换矩阵，这个矩阵的第 i 行 j 列表示 i 到 j 的个数。

我们有

一个广义置换和一个半标准杨表对一一对应。具体来讲就是运行 RSK 算法，把第二行的元素插入 P，Q 中记录第一行的元素。

而如果有广义置换矩阵 M\rightarrow(P,Q)，则 M^T\rightarrow(Q,P)。

杨表和 LIS 问题

LIS 即最长上升子序列，LDS 即最长下降子序列。

显然有如下结论：

杨表第一行的长度即 s 的 LIS 的长度。但是第一行并非 s 的 LIS。
若有 s\rightarrow(P,Q)，则 s 的翻转 \text{rev}(s)\rightarrow(P^T,Q')。其中 P^T 是 P 的转置，Q' 和 Q 没什么关系。
于是我们得到杨表第一列的长度即 s 的 LDS 的长度。

「CTSC2017」最长上升子序列

根据 Dilworth 定理，一个序列的 LIS 的长度等于将其分为若干个不上升子序列所需数量的最小值。那么最长的 C 就是 B 对应的“\le 杨表”的前 k 行长度之和。

不幸的是直接暴力实现杨表插入是 n^2\log n 的。考虑根号分治，分别维护前 \sqrt n 行和前 \sqrt n 列。对于前 k 列，它就是对应的“> 杨表”（标准杨表）的前 k 行。

~~明明和杨表没有深入关系，但是不会杨表就做不了的屑题~~

[BJWC2018]最长上升子序列

爆枚杨表形态即可。整数拆分 p(n) 渐进意义上等于

p(n)\sim\dfrac{1}{4\sqrt 3 n}e^{\pi\sqrt{\frac{2n}{3}}}

顺瑇一提这个公式是拉马努金发现的（