杨氏矩阵

引入

杨氏矩阵(Young tableau)，又名杨表，是一种常用于表示论和舒伯特演算中的组合对象。

杨表是一种特殊的矩阵。它便于对称群和一般线性群的群表示和性质研究。杨表由剑桥大学数学家阿尔弗雷德·杨（Alfred Young）于 1900 年首次提出，于 1903 年被德国数学家弗罗贝尼乌斯（Ferdinand Georg Frobenius）应用于对称群的研究。

定义

杨图

杨图（Young diagram，使用点表示时又称 Ferrers 图，在

分拆数 一节中有相关介绍）是一个有限的框或单元格集合，左对齐排列，行长按非递增顺序排列。如果把杨图每行的方格数列出，我们得到了一个非负整数 （总方格数）的 整数分拆(integer partition)。因此，我们可以将杨图的形状看作 ，因为它携带与其整数拆分相同的信息。

杨图之间的包含关系定义了整数分拆上的一个偏序关系，此关系拥有格的结构，被称为 杨格(Young's lattice)。如果把杨图各列的方格数列出，则会得到整数分拆 的「共轭分拆」，或「转置分拆」，它所对应到的杨图可由原本的杨图沿主对角线作镜射对称而得。

杨图每个方格的位置由分别代表 行数 与 列数 的两个座标点决定。列的顺序由左向右，行的顺序则按方格数的由多向少的方向。此处需要注意，根据习惯不同存在着两种不同的杨图画法：第一个将方格数较少的行排在方格数较多的行的下方，第二种画法将各行由大到小一层一层往上叠。由于前一种画法主要由英语国家使用，而后者通常被法语国家使用，习惯上我们分别称它们为英式画法和法式画法。

以下表格中分别为整数分拆 对应的杨图不同画法：

• 英式画法：
• 法式画法：

杨表

定义

杨表(Young tableau）是通过用取自某个字母表的符号填充杨氏图的框来获得的，这通常需要是一个全序集和。填入的元素写作 ,,,。但为了方便起见，都直接填入正整数。

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

（OEIS 中的数列 A000085）

在其他应用中，杨图也可以被填入相同的数字。若填法的同列数字严格递增，且同行数字单调递增，则该杨表被称为是 半标准的（Semistandard Young Tableaux, 有时称为列严格）。杨表中个数字出现的次数记录下来得到的序列被视为杨表的 权重。因此，标准杨表的权重必然是 。因为在标准杨表中， 到 的每个正整数恰好各出现一次。

标准杨表的插入算法

排列的性质可以由杨表直观地表现出来。RSK 插入算法 就提供了一个将杨表和排列联系起来的途径。它由 Robinson, Schensted 和 Knuth 提出。

令 是一个杨表，定义 表示将 从第一行插入杨表中，具体如下：

1. 在当前行中找到最小的比 大的数 。
2. 如果找到了，用 去替换 ，移到下一行，令 重复操作 1。
3. 如果找不到，就把 放在该行末尾并退出。记 在第 行第 列， 必定是一个边角。一个格子 是边角当且仅当 和 都不存在格子。

例如，将 插入杨表 的步骤为：

变体

非完全严格标准的杨表有许多变体（Variations)。例如行严格杨表要求同行数字严格递增，且同列数字单调递增，即列严格杨表的共轭。此外，在平面分拆（plane partitions）理论中，习惯上会将上述的定义中的递增改为递减。其他变体例如带状杨表，会先将一些方块打包成群，然后要求各群的方块必须填入相同数字。

斜杨表

给定两个杨图 、，满足 包含 ，即 对所有 。定义「斜杨图」 为 中所有方格减去 中的所有方格 即 差集 。在斜杨图的各方格中填入元素就形成了 斜杨表(Skew tableaux)。

例如，下图为整数分拆 对应的一个标准斜杨表：

同理，若满足同一列中的数字严格递增，且同一行中的数字单调递增，则该斜杨表被称作 半标准斜杨表；若半标准斜杨表满足各方格不重复的填入数字 到 （方格总数），则该斜杨表被称作 标准斜杨表。注意，由不同的 和 可得到相同的 。虽然大部分斜杨表的性质都只依赖于取完差集的方格，但是仍然部分运算依赖于 和 的选取。因此， 必须被视为包含两个元素信息： 和 。当 是空分拆 ( 的唯一一种分拆）时，斜杨表 就变成杨表 。

应用

杨表常用于在组合学、表示理论和代数几何中，用各种不同计算杨表个数的方法得到舒尔函数的定义及相关的恒等式。在信息学竞赛中，常有考察杨表钩长公式的题目。

勾长

给定一个共有 个方格的杨表 ，把 到 的 个数字填入杨表中，使得每行从左到右，每列从下到上都是递增的。用 表示可以这样填的方法个数。

对于杨表中的一个方格 ，定义其 勾长 等于同行右边的方格数加上同列上面的方格数，再加 1（即方格本身）。

勾长公式

如果用 表示这样的方法个数，勾长公式 就是方法个数等于 除以所有方格的勾长的乘积。

所以对于整数分拆 的杨表，如上图所示。有

种方法。

例题

子序列问题

对于杨表 , 定义对于一个从 到 的排列 。

1. 中第一行的长度即为排列 的 最长上升子序列（LIS) 长度。注意， 的第一行并不一定是 LIS 本身，所以不能直接利用杨表性质解决「LIS 划分」之类的问题。

2. 对于一个排列 和它产生的杨表 ，若 是 的翻转，那么 产生的杨表 即为 交换行列得到。

   例如，对于排列 和 , 我们可得到如下杨表 :

   

3. 杨表 中的第一列长度即为排列 的 最长下降子序列（LDS) 长度。

定义长度不超过 的 长度为 和 , 此类问题我们同样可以用杨表来解决。对于 ，显而易见最长的 子序列就是该序列的 ，这也正是杨表的第一列；同样可得，杨表前 列的长度就是最长的 子序列的长度。证明如下：

对于一个排列 和它的 行杨表 ，令排列 为 （即将杨表从下往上每行依次写在后面）。那么 一定可以通过交换操作转化成 。

所以，最长 子序列长度可以表示成 ，即前 列的长度和。

参考资料与拓展阅读

• [1]Young Tableau - from Wolfram MathWorld
• [2]Young tableau - Wikipedia
• [3]Hook length formula - Wikipedia
• [4]袁方舟，《浅谈杨氏矩阵在信息学竞赛中的应用》IOI2019, 中国国家候选队论文集，202-229