Young 表与水平条链

一张表可以看成格子按批次出现的记录。行弱增让一行中的早批次格子总在左边；列严格增要求一个格子出现时，上方格子已经在更早的批次出现。于是每个前缀仍是左上对齐的分拆形状，同批次也不会在一列里叠放两个格子。

标准表把每批限制为一个格子。标签记录的是加入时刻，不是格子的固定名称。形状相同的两张表可以有不同的增长顺序，这就是为什么知道分拆$(4,2,1)$还远远没有指定一张表。

水平条也不要求所有新格子都在同一行。它限制的是同列重叠。下一例中，最后一批同时落在三行，仍是一条合法水平条。

一张七格表及其三步证书 ​

取$\lambda =(4,2,1)$、$m=3$，填成

内容为$(2,2,3)$。保留标签1、再保留标签1和2、最后保留全部标签，依次得到

第二步在$(1,3),(2,1)$加格，第三步在$(1,4),(2,2),(3,1)$加格。每一步的新格列号互异。反过来只给这三份行长，也能按差集填回原表，不需要额外猜测各格的标签。

图中颜色按加入批次固定。最后一批分布在三行，却没有两格处于同列。

直接用水平条链数出15张表 ​

仍取$\lambda =(4,2,1)$和$m=3$。标签不超过2的子形状只能有两行，记为$(a,b)$。它与最终形状之间满足式(3)，因此

标签1只能占一行，记长度为$c$。再用式(3)，恰好要求$b\le c\le a$。每组三元组$(a,b,c)$都唯一恢复一张表，所以

这不是靠把$3^7$份任意填数全部试完才得出的数目。水平条链已经去掉不满足行列条件的填法；后面的钩内容公式还会从另一条路线复算同一结果。

哪些改动改变了对象 ​

若把第一列填成$1,1,3$，行即使仍弱增，也违反列严格条件；它的标签1前缀会在同一列同时增加两个格子。若把一行的$1,2$颠倒为$2,1$，标签1前缀不是左对齐形状。这两种失败分别对应证书的水平条条件和形状条件。

只要求各行、各列弱增会得到另一种填数对象，不再由式(2)的水平条链描述。相反，把行也要求严格，会删掉本页允许的重复标签。因此程序中的$<$与$\le$不能互换。

非空形状有$r$行时，第一列需要$r$个互异标签，所以$m<r$时半标准表集合为空；$m\ge r$时，把第$i$行全填$i$就给出一张表，故这也是存在性的充分条件。转置一张标准表仍是标准表；转置半标准表却会交换“行弱、列严”，一般不再属于本页同一种半标准约定。

为什么链与表确实互相恢复 ​

先从半标准表出发。若$(i,j)$的标签不超过$k$，其左侧标签也不超过$k$；其上方若有格子，标签更小，也被保留。因此标签前缀向左、向上封闭，恰是一份分拆形状。列严格保证同一个$k$不会出现在同列两次，所以相邻前缀的差是水平条。

反过来，从式(2)的链按新格加入时刻填数。右侧格子进入形状时，左侧格子必须已存在，故左侧标签不大于右侧标签。同样，下方格子进入时，上方格子已经存在；水平条又禁止上下两格在同一步加入，所以其标签严格更小。这证明式(1)，两个构造显然保留每个格子的加入时刻，因而互逆。

式(3)也可逐格证明。包含关系给${\nu }_i\ge {\mu }_i$。若${\mu }_i<{\nu }_{i+1}$，第${\mu }_i+1$列在第$i$行和第$i+1$行都出现新格，违反水平条。反之，若同列$j$在两行$i<k$都出现新格，则$j>{\mu }_i$且$j\le {\nu }_k\le {\nu }_{i+1}$，违反${\mu }_i\ge {\nu }_{i+1}$。因此它准确等价于“不在同列加两格”。

角格递推提供第二类有限证书 ​

记$f^{\lambda }=|\mathrm{SYT}(\lambda )|$。标准表的最大标签$N$不能有右邻或下邻，否则那里必须填更大的数。因此$N$位于一个可删除的角格：删去它后仍是分拆图。每个角格删法都可逆，故

每次递推减少一格，必然到达空形状。对主例，三个角格给出

这些较小数也可以不借闭式核出：$f^{(2,1)}=2$，进而$f^{(3,1)}=f^{(2,1,1)}=3$、$f^{(2,2)}=2$，所以

单行与单列形状始终只有一张标准表，作为这些递推的边界。记录每个子形状及其角格前驱，就能逐项检查35的来历。

若记$g_{\lambda }(m)=|{\mathrm{SSYT}}_m(\lambda )|$，同理有

其中$g_{\varnothing }(m)=1$，非空$\lambda$满足$g_{\lambda }(0)=0$。这次删去的是全部最大标签，允许删去空条，因为某个字母未必使用过。

子形状总数记为$B_{\lambda }$。把这些形状列出后，直接检查全部候选水平条对、逐层存两份计数表，至多用$O((m+1)B_{\lambda }^2(r+1))$次行长检查及整数加法，存储$O(B_{\lambda }(r+1))$个行长和计数槽。此界明确依赖子形状数，并不声称对任意输入大小都高效；大整数位成本还要另计。

三个后续接口分别增加什么 ​

Jacobi–Trudi权计数理路Jacobi–Trudi 与表格权计数Jacobi-Trudi identity · Jacobi–Trudi formula · Tableau expansion of Schur polynomials将既有Schur交错商连接完全齐次行列式和半标准表权和，完整证明系数分解、首次相交换尾及列严格对应。将每张表的$x^T$相加，证明所得多项式正是已有的Schur多项式。钩长与钩内容公式理路钩长与有限字母计数Hook-length formula · Hook-content formula · Young tableau hook formulas · 钩长公式 · 钩内容公式从表权行列式推出标准表钩长积与有限字母半标准表钩内容积，证明行钩缺项恒等式并处理重合变量、空形和斜形边界。则把35和15这两种计数化成格子乘积。RSK词插入理路RSK 词插入与逆恢复Robinson-Schensted word correspondence · RSK word insertion · Schensted row insertion · 行插入与记录表固定严格大于的行插入与严格小于的逆撞规则，证明有限词和同形表对双射、内容保持及第一行最长弱递增长度，再计算指定形状的词纤维。把一份词可逆地编码为同形的一张半标准表与一张标准表，因此必须保留两张表各自的任务，不能只输出最终形状。