杨氏矩阵简介

本文大多在介绍关于杨氏矩阵(Young tableau)的组合计数相关。

（本文内容大量搬运自维基百科）

定义：杨氏矩阵由1\sim n的n个不同的数构成，要求矩阵中要么这个点没有元素，要么这个元素的左方和上方都有元素，且元素的值都小于这个数。

如图是一个杨氏矩阵的例子

下面讨论两个问题：

给定杨氏矩阵的形状（即告诉你矩阵的每一行有多少个元素），求这样的杨氏矩阵一共有多少种。

这个问题由钩子公式完美解决。

定义钩子H(i,j)表示矩阵中元素(i,j)的下方以及右方(包括本身)一共有多少个元素，那么一个形状确定的杨氏矩阵共有

\frac {n!}{\prod H(i,j)}

比如由四个元素组成的两行两列的杨氏矩阵共有

\frac {4!}{3\times2\times2\times1}=2

关于这公式的证明我还不会，但是这里有一个便于记忆的伪证

由于杨氏矩阵的定义，每个位置的元素一定大于自己下方以及右方的所有元素，所以如果我们给矩阵的每一个位置任意赋值，这样总共有n!种不同的填法。而每个位置成为最小值的概率就为\frac 1{H(i,j)} (想象长度为n的总共n!个排列中，以1开头的排列有多少种) ，所以合法的杨氏矩阵就有上式那么多种。

上述伪证为错误的原因是位置与位置之间不是独立的，所以说概率不能简单相乘求得，但令人惊奇的是结论确实是正确的。

下一个问题：

由n个元素构成的杨氏矩阵总共有多少种？

这个问题与上文的区别在于没有限制矩阵的形状。

这个问题有一个很简洁的递推公式，用f_n表示n个点的杨氏矩阵的个数

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

那么有什么组合意义呢？上述递推公式能符合许多的组合模型的计数，我们来一一介绍。

在维基百科中这一个组合意义的标题是"Telephone Number"，其模型是n个点的完全图中选出一个边的子集使得形成一个合法匹配的方案数(允许空集)。

而根据这一组合意义确实很好确立组合意义递推式。考虑第n个点在不在匹配中，若不在匹配中，方案数为f_{n-1}，否则第n个点有(n-1)种方式与前(n-1)个点形成匹配，然后剩下的问题为f_{n-2}。递推式得证。

如果我们将图的匹配情况用一个排列来这样描述，若第i个点没有在匹配中则令p_i=i，否则如果第i个点的匹配点为u，则p_i=u。容易证明这个排列和之前的匹配是一一对应的。如果对置换有了解的读者可能能得出这个排列的循环小于等于2，也就是说这个排列在置换意义下的逆即为它自身。

而这几项事物中中是有着紧密的联系的，在介绍联系之前还要介绍一种通过一个排列的构造出一个杨氏矩阵的构造方式。

Robinson–Schensted correspondence

首先来证明之前的递推式是如何作用在杨氏矩阵上的。

考虑大小为n的杨氏矩阵中最大元素的位置，若其在第一行末尾，那么这种类型的矩阵共有f_{n-1}种。考虑剩下的情况，我们用一个大小为n-2的杨氏矩阵去构造。

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

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

• 检查当前行中是否有大于j的元素，如果没有，将j加入到这一行的末尾，结束这一过程。

• 否则用j替换掉当前行中第一个大于j的元素k，并将元素k按照一样的步骤从下一行开始插入

插入结束后，我们将n加入到插入结束的那一行的下一行末尾，这样能得到一个大小为n的杨氏矩阵。

举个例子，将上图大小为10的矩阵选择j=6得到一个大小为12的杨氏矩阵。

初始时矩阵为

1	2	4	8	9
3	5	7	10
11

然后在第一行找到第一个大于j=6的数8，将6插入到8的位置，然后令j=8，进入第二行。

1	2	4	6	9
3	5	7	10
11

找到第二行第一个大于j=8的数10,将8插入到10的位置，然后令j=10，进入到第三行。

1	2	4	6	9
3	5	7	8
11

然后再将10插入。

1	2	4	6	9
3	5	7	8
10

在第四行，没有数字大于11，所以将11加入到第四行末尾。

1	2	4	6	9
3	5	7	8
10
11

然后将12加入到第四行的第五行，所以将12加入到第五行

1	2	4	6	9
3	5	7	8
10
11
12

这个操作是可逆的，也就是说一个大小为n-2的杨氏矩阵和一个数j能唯一确定一个大小为n的杨氏矩阵且n所在位置不在第一行末尾。

根据以上构造就能证明递推式的正确性。

这启发我们给定一个排列，我们也能构造出一个杨氏矩阵。但这并不是双射，因为大小为n的杨氏矩阵显然没有n!那么多。不过这里倒是有个很神奇的定理。

给定一个排列，我们还是按照刚才介绍的构造方法，将排列中的每个数从前到后一一插入杨氏矩阵，同时我们记录另外一个杨氏矩阵，这个杨氏矩阵某个位置上数值的含义为第一个杨氏矩阵的这个位置第一次有值是排列中第几个数插入的时候。

还是看一个例子 排列p=3,8,1,2,4,7,5,6

• 首先将3插入到第一个位置上，并且发现第一个位置有值是在第一个数插入的时候，在第二个杨氏矩阵的对应位置写上1。

第一个杨表：

3

第二个杨表：

1

• 之后将8插入，另一个表第一行第二个位置上写上2。

第一个杨表：

3	8

第二个杨表：

1	2

• 将1插入，这时候3的位置移到了第二行的第一列，这时候第二行第一列有值了，所以在第二个杨表里写上3。

第一个杨表：

1	8
3

第二个杨表：

1	2
3

• 插入2。

第一个杨表：

1	2
3	8

第二个杨表：

1	2
3	4

• 插入4

第一个杨表：

1	2	4
3	8

第二个杨表：

1	2	5
3	4

• 插入7。

第一个杨表：

1	2	4	7
3	8

第二个杨表：

1	2	5	6
3	4

• 插入5。

第一个杨表：

1	2	4	5
3	7
8

第二个杨表：

1	2	5	6
3	4
7

• 插入6。

第一个杨表：

1	2	4	5	6
3	7
8

第二个杨表：

1	2	5	6	8
3	4
7

好了，大家应该看懂了吧。

不难发现两个杨氏矩阵的形状是一模一样的。然后接下来就有一个厉害的定理就是:

\sum_{\lambda\in \mathcal{P}_n} (t_\lambda)^2=n!

其中\mathcal P_n表示n的划分数的集合，实际上就是在枚举杨氏矩阵的形状。后面t_\lambda表示形状为\lambda的杨氏矩阵的个数。

也就是说任意两个形状相同的杨氏矩阵能还原出唯一的一个排列与其对应。

（我当然不会证明）

然后如果两个杨氏矩阵(P,Q)能确定出一个排列p，那么(Q,P)对应的排列就是p^{-1}。（不会证）

当然两个一模一样的杨氏矩阵也能还原出一个排列来。这样的排列就是前面说过的"排列的逆等于自身"那些排列。

所以这也说明了为什么这样的排列个数与杨氏矩阵相等。（好神奇）

维基百科上应该都有证明，但我太菜了看不太懂。

另外还有一个等价的另外一种方法的构造。贴个链接跑人

Viennot's geometric construction

计数说完了，下面来说一些杨氏矩阵的应用。

由于他的单调性，我们可以拿它来做数据结构使用。