杨氏矩阵笔记-526互联

说明

本文杨图采用英式画法。

定义

杨图

杨图（Young Diagram）是一个有限的框或单元格集合，左对齐排列，行长按非递增顺序排列。相当于从上往下杨图的行长非递增，且从左往右杨图的列长非递增（当然其实前后两者等价）。令总方格数为 $n$，那么杨图的形状对应了一个 $n$ 的整数拆分。

我们将杨图的形状记为 $\lambda$ ，它携带了与整数拆分一一对应的信息。

杨图每个方格的位置由分别代表行数与列数的两个座标点决定。列的顺序由左向右，行的顺序则按方格数的由多向少的方向。在英式画法中，行的顺序由上向下。

杨氏矩阵（杨表）

杨表最初应用于对称群的表示理论时，允许在杨图的 $n$ 的方格中任意填入 $1$ 到 $n$ 中相异的正整数。但现在的研究大多使用「标准」的杨表，即上述条件中各行与各列中方格的数字皆为严格递增的。

定理[1]

对于固定的一个 $n$，记有 $n$ 个格的杨表的填完数后形式个数为 $f_n$。

则有递推式：

\[f_0=1,f_1=1,f_n=f_{n-1}+(n-1)f_{n-2},n \ge 2 \]

证：

可以用 RSK 算法的插入和删除的互逆性。（RSK 算法后面会讲）

考虑一个元素 $x \in [1,n-1]$，其作为某一行的最后一列且下一行的长度小于这一行时，其下一行一定可以在最后插入 $n$。

因为 RSK 算法的插入和删除的互逆性：若将 $x$ 的所在格删去，得到的杨表唯一对应一个格数为 $n-2$ 的杨表；一个格数为 $n-2$ 的杨表在插入某个数后也可以得到唯一对应的与 $x$ 有上述性质的格数为 $n-1$ 的杨表。

所以满足上述要求的 $n-1$ 格杨表与 $x$ 的元组一定和 $n-2$ 格杨表与计划插入的数 $y$ 构成双射。

所以这时新杨表的形态个数为 $(n-1)f_{n-2}$，因为 $y \in [1,n-1]$。

这是 $n$ 插入进 $n-1$ 格数杨表的非第一行的情况的贡献。

$n$ 插入进 $n-1$ 格数杨表的第一行的情况的贡献为 $f_{n-1}$。

所以 $f_n = f_{n-1} + (n-1)f_{n-2}$。

证毕。

定理[2]

记一个格子的臂长为其正右方的格子数（不包含自己）。

记一个格子的腿长为其正下方的格子数（不包含自己）。

对于一个确定形状的杨图 $\lambda$ （格数为 $n$），记 $H_x$表示这个格子的勾长，即臂长+腿长+1（因为要包含自己）。

对于这个杨图 $\lambda$，记其填入 $1,2...,n$ 的方案数为 $\dim_{\lambda}$。

则有：

\[\dim_{\lambda} = \frac{n!}{\Pi_{x \in Y(\lambda)} H_x} \]

证：

网友提供的证明。其自己也认为这种证明是伪证，但实际是没问题的（大概）。

我们考虑从第一行开始逐行填数，对于每一行，从左往右逐列填数。先不考虑满足标准杨表的严格递增性，则可以任意填数，方案数为 $n !$。

现在再来满足严格递增性，对于当前考虑的以 $x$ 作为左上方的一个勾子，令其构成的排列为 $\mu$，记当前（剩余格子没有考虑严格递增性的情况下）的情况下对于一个勾子排列 $\mu'$ ，在所有方案数中，其在原位置存在的方案数为 $g(\mu')$。

则根据不满足严格递增性的随机填数性有：

\[\forall \{\mu'\} = \{\mu\}: g(\mu')=g(\mu) \]

但是对于所有的这些排列 $\mu'$ 若要求当前格满足严格递增性，$x$ 必须填入 $\min\{\mu\}$。

而因为填数的随机性，所以 $x$ 填入 $\min\{\mu\}$ 的概率为 $\frac{1}{|\mu|}$，即为 $\frac{1}{H(x)}$。

且因为我们特殊的填数顺序，所以每次我们考虑的勾子一定都是还未填数的，所以概率一定正确。

（似乎这位网友没有考虑可以用特殊的填数顺序去规避掉位置与位置之间的影响）

其实还可以想象为当前满足条件的方案数只占填 $x$ 之前满足条件的方案数的 $\frac{1}{H(x)}$。

然后把这些概率（或者说是方案占比）乘以总方案数，即有：

\[\dim_{\lambda} = \frac{n!}{\Pi_{x \in Y(\lambda)} H_x} \]

证毕。

RSK 算法

RSK 算法（Robinson-Schensted-Knuth insertion algorithm），提供了一个将杨表和排列联系起来的途径。

插入操作如下：

令 $S$ 为一个杨表，若我们要插入一个数 $x$，那么从第一行开始：

在当前行找到最小的比 $x$ 大的数。
若找到了则记其为 $y$，然后 $x,y$ 交换，即将 $x$ 填入原本 $y$ 所在的位置，然后把 $y$ 当作 $x$ ，然后进入下一行循环执行 1. 2. ；否则将 $x$ 置入当前行作为当前行的最后一个。

注意，此处的插入与上文的 RSK 算法有所出入，这是定理[1] 证明中的插入操作：

对于每个大小为 $ n-2$ 的杨表，我们选择一个数 $j \in [1,n-1]$，将矩阵中 $\ge j$ 的数都 $+1$，然后将 $j$ “插入”到这个矩阵中，

插入从第一行开始，每一行执行以下步骤：

检查当前行中是否有大于 $j$ 的元素，如果没有，将 $j$ 加入到这一行的末尾，结束这一过程。
否则用 $j$ 替换掉当前行中第一个大于 $j$ 的元素 $k$，并将元素 $k$ 按照一样的步骤从下一行开始插入。

这样之后，对于最后将 $j$ 加入末尾的那一行，这一行的长度一定大于下一行的长度，所以可以将 $n$ 放在下一行的末尾，对应了上文定理[1] 的证明。

RSK 算法还额外寻求了插入操作对应的逆操作，即删除操作。

删除操作如下：

令 $S$ 为一个杨表，若我们要删除一个位置 $x$ （$x$ 位置一定可删除），记 $y$ 为当前数，初始等于 $x$ 内的数：

找到上一行中最大的小于等于 $y$ 的数 $z$，显然一定存在。
将 $y$ 和 $z$ 交换，若上一行为第一行，退出；否则跳到上一行。

这两种操作完成后一定会获得杨表。

同时真正的 RSK 算法会同时维护两个杨表分别为 $P_X$ 和 $Q_X$，其中 $X$ 是一个排列。

显然对于固定的杨表，插入和删除的逆操作总是固定一一对应的。

而且可知的是，因为通过 $Q_X$ 确定了顺序，所以插入和删除不管是单次还是全局都互为逆算法。

记 $P_X \leftarrow x$ 为将 $x$ 插入杨表 $P_X$ 的操作。

故按照 $X$ 顺序插入 $x_i$，在插入时将每次新增的格子在 $Q_X$ 中赋值为 $i$。显然 $Q_X$ 也为杨表。

此时 $X$ 的 LIS 长度就是 $P_X$ 第一行的行长。（但不一定是那些元素）

此时 $X$ 的 LDS 长度就是 $P_X$ 第一列的列长。（同样，不一定是那些元素）

LIS 结论推到 LDS 结论其实很好证，因为 $Q_X$ 中存储的每行似乎都是前面行的数删完后的 LIS，根据 Dilworth 引理可证。

Robinson-Schensted correspondence

$\{(P_X,Q_X)\}$ 与 $\{X\}$ 构成双射，即有一一对应关系。

更加简便但不完全地：

\[n!= \sum_{\lambda \vdash n} \dim_{\lambda}^2 \]

其中 $\dim_{\lambda}$ 是对于一个形状为 $\lambda$ 的杨图，填数使其成为杨表的方案数。

证：

对于一个排列 $X$，通过插入算法可以唯一找到对应的杨表对 $(P_X,Q_X)$；对于一组杨表对 $(P_X,Q_X)$ 可以通过删除算法还原出一个排列 $X$：每次将 $Q_X$ 中最大数所在位置从 $P_X$ 中使用删除算法删除，同时在 $Q_X$ 中直接将这个位置删除。由于 RSK 算法的插入和删除操作互为逆操作（逆算法），所以可以得到一一对应关系。

证毕。