杨氏矩阵简介

本文大多在介绍关于杨氏矩阵([Young tableau](https://en.wikipedia.org/wiki/Young_tableau))的组合计数相关。 （本文内容大量搬运自维基百科） 定义：杨氏矩阵由$1\sim n$的$n$个不同的数构成，要求矩阵中要么这个点没有元素，要么这个元素的左方和上方都有元素，且元素的值都小于这个数。 如图是一个杨氏矩阵的例子  下面讨论两个问题： 给定杨氏矩阵的形状（即告诉你矩阵的每一行有多少个元素），求这样的杨氏矩阵一共有多少种。 这个问题由[钩子公式](https://en.wikipedia.org/wiki/Hook_length_formula)完美解决。 定义钩子$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](https://en.wikipedia.org/wiki/Telephone_number_(mathematics))"，其模型是$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](https://en.wikipedia.org/wiki/Robinson%E2%80%93Schensted_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](https://en.wikipedia.org/wiki/Viennot%27s_geometric_construction) 计数说完了，下面来说一些杨氏矩阵的应用。 由于他的单调性，我们可以拿它来做数据结构使用。