首先，什么是杨表？在 OI 中，杨表经常用来刻画一些与 LIS 有关的“偏序”性质，然而杨表在其它的组合表示领域还有许许多多的应用。这里我们先从 k-LDS 问题引入标准杨表，然后讨论杨表在其它的组合领域的应用。
Part 1
定义 k-LDS 序列为最长下降子序列不超过 \(k\) 的序列，我们根据 Dilworth 定理或者自己感性理解一下，可以知道一个排列的最长的 k-LDS 子序列相当于从排列中选出 \(k\) 个不相交的 IS 的最长长度和。
如何同时维护 k 个 IS 呢？我们有一个 \(O(n^2\log)\) 的简单做法：考虑扩展求 LIS 的二分栈做法，每次我们插入排列中的后一个元素 \(x\)，找到二分栈中第一个大于 \(x\) 的位置替换成 \(x\)。此时这个被替换下来的数不要丢了，再在下面新开一个二分栈。如果这个二分栈也插入失败了又往下插入。将所有二分栈的数组排成一个斜着的三角形状物，我们就得到了一个优美的二维结构。输出这个结构，我们可以发现它满足一些更优美的性质：
-
每一行严格递增。
-
每一列严格递增。
-
每一行的长度都不超过上一行。
-
所有数组成一个 \(n\) 阶排列。
我们称这样一种结构为标准杨表。
第四个性质不用说。第一个性质由于我们插入的过程每次二分然后替换显然满足。
第三个性质这样考虑：对插入过程施加归纳，所以如果有两个长度相同的行，如果在前面那行插入没有结束，那么由于归纳条件列严格递增，后面那行的最后一个数比前面那行所有数都要大，你拿前面那行的任意一个数插入肯定不会在这一行结束。
第二个性质呢？由于每次插入之后为了找到下一行中比当前位置更大的数，当前位置肯定不会往右移动，因为由于列递增，往下移动肯定就比当前数大了。所以插入的位置只会往左下移动。容易发现这样列递增的条件就被保持了。
Part 2
Part 1 中，我们构建了一个排列到标准杨表的满射。那么标准杨表可以反过来得到排列的结构吗？
答案是可以的，但我们需要记录下每一次插入操作完后，杨表多出来的那一个格子是哪个。我们考虑直接把每次操作完后新加的那个格子中填入你刚刚进行的操作编号 \(i\)，这样我们又得到了一个二维结构 \(Q\)，我们称它为“记录表”。容易发现记录表也是标准杨表。
我们对这记录表按照值从大到小删除所有的格子，删除的时候考虑做一个插入时的逆过程，每次找出你当前要删除的上一行最后一个比它小的数，将这个位置替换成你要删掉的数，然后递归去删这个数，直到删到第一行。此时你正在删除的数就是之前排列加入的数。
这样，对于两个相同形状的标准杨表，我们建立了其到排列的双射。
Part 3
我们忽略杨表中的所有数，只考虑它的形状，称这种结构为杨图。发现杨图的结构就是 Ferrers 图的结构（只不过一个是点，一个是格子），那么杨表有没有跟 Ferrers 图一样有转置的性质呢？
杨表的结构十分对称，对于行和列是没有区别的。我们上面在排列末尾插入可以看成对行插入。我们也可以改成从列插入，这对应到原排列上就是从排列开头插入！
这是因为我们有如下结论：将排列 reverse 一下，它对应的标准杨表就是原来的杨表的转置！
具体证明可以参考袁方舟 19 年的集训队论文，我们记对杨表 \(S\) 行插入一个 \(x\) 的操作得到的结果为 \(S\leftarrow x\)，列插入的结果为 \(S\to x\)。，我们只需要考虑到引理 \((x_1\to S)\leftarrow x_2=x_1\to( S\leftarrow x_2)\)，然后对着排列两种不同的插入顺序归纳一下就可以了。事实上，也可以考虑用 Dilworth 定理疯狂感性理解。
接下来我们考虑将排列看成 \((i,p_i)\) 这种形式，那么 reverse 相当于将 \(i\to n-i+1\)，这样原本的 IS 全部变成了 DS（也就是偏序集取了个反）。所以我们也由这件事情知道了原来杨表的第一列的实际意义就是 LDS 的长度。前 \(k\) 列的长度和就是划分成 \(k\) 个 DS 的最长长度。这再一次显现出杨表关于行和列的对称性。