参考资料:论文集2019《浅谈杨氏矩阵在信息学竞赛中的应用》袁方舟,《对称群笔记》Wenchao Zhang。
杨图(记为 )大概就是一个长成这样的东西:
每行的列数称为 。 单调不增,和为 ,称为 。
你要往里面填 的排列,使得行单调增列单调增,这样的一种填充称为标准杨表。杨表数量由下面的勾长公式给出。
设 是杨图中格子 的勾长,等于其下方格子个数+右方格子个数+1。
标准杨表总数为
也可以完全只用 表达:
即行不严格递增,列严格递增的杨表。
设值域为 ,半标准杨表数为
即从一个杨图 中扣掉另一个杨图 。不连通也没关系。
一个兴奋图(写出这个东西的英文名可能导致寿命减少)是指, 经过一系列的兴奋运动形成的 的某个子集。对 的兴奋运动是指,将一个下方右方右下方都属于 的属于 的方格移动到其右下方。
如图是 的所有可能的兴奋图。记为 。如下是勾长公式。
下面我们将揭示杨图和排列的深刻联系。先引入 算法。
行插入
定义 是把 从第一行行插入进近似标准杨表(即填入的元素不必是 ) 中。流程如下:
- 找到本行最小的比 大的数 。如果找不到这样的 ,则把 放在本行末尾并结束算法。
- 交换 。将 行插入下一行。
如下演示了一个行插入过程。
显然最后新增的格子一定在边角,即其下方和右方都没有格子。
对于对 的第 插入,在另一个杨表 中在新增的格子上写上 (注意不是插入)。显然 是标准杨表。我们称 为插入表, 为记录表。
删除
下面定义从 中删除格子 。尽管看起来不必要,我们还是规定 必须是边角。记 中填的数是 。流程如下:
- 如果这是第一行,结束算法。
- 找到上一行最大的比 小的数 (显然一定存在)
- 交换 ,移到上一行继续算法。
结束算法后删掉已经没有数的格子 。
如下演示了一个删除过程。
很明显删除就是行插入的逆操作。
考虑一个 的排列,依次插入即可得到两个杨表 ;给定 ,显然 中最大元素一定在边角,于是我们可以按 的指导去删除 来还原原来的排列。
于是也就得到了以下的Robinson–Schensted correspondence:
上述算法构成了 到 的一一映射。也就是说,
不禁让人联想到 prüfer 序列。
同时对于置换(当然也是排列),我们有 ,从而每一个标准杨表 对应一个对合,即逆等于自身的置换。对对合计数,我们得到:
其中双阶乘 定义为 。
一个广义置换大概可以理解为可重集上的置换,比如
它对应一个广义置换矩阵,这个矩阵的第 行 列表示 到 的个数。
我们有
一个广义置换和一个半标准杨表对一一对应。具体来讲就是运行 RSK 算法,把第二行的元素插入 , 中记录第一行的元素。
而如果有广义置换矩阵 ,则 。
LIS 即最长上升子序列,LDS 即最长下降子序列。
显然有如下结论:
根据 Dilworth 定理,一个序列的 LIS 的长度等于将其分为若干个不上升子序列所需数量的最小值。那么最长的 就是 对应的“ 杨表”的前 行长度之和。
不幸的是直接暴力实现杨表插入是 的。考虑根号分治,分别维护前 行和前 列。对于前 列,它就是对应的“ 杨表”(标准杨表)的前 行。
明明和杨表没有深入关系,但是不会杨表就做不了的屑题
爆枚杨表形态即可。整数拆分 渐进意义上等于
顺瑇一提这个公式是拉马努金发现的(
记 是点 到点 的路线的集合,每一步只能往右边走或者往上方走。两条路径相交即有公共点。显然 。
卡塔兰数的组合意义即从 走到 ,任何时刻横坐标不能小于纵坐标。考虑 为横坐标到达 的时间, 亦然,那么它就对应如下的一个杨表。
显然一个 的标准杨表和路径一一对应。从而 的标准杨表数即卡塔兰数。
显然题目要求的路径对应一个 的杨表。式子化出来是
FFT 统计有多少对 满足 ,然后就好了。
给出平面上的 个点对 ,记 。则从 中各取一条路径,使得它们互不相交的方案数为
事实上该引理适用于所有有向无环图。
考虑容斥掉所有存在相交的方案。对于一个相交的方案,我们找到一个最大(这个最大可以任意定义,只要唯一即可)的相交点,则我们可以交换相交后的这条路径。
为了让它们相互抵消,交换后容斥系数应当乘以 -1。我们发现这正是置换的符号 的定义。(-1 的逆序对个数次方)写出式子:
这正是行列式的定义。
和卡塔兰数类似,不相交路径集合也和杨表有对应。
一个元素在 的半标准斜杨表 和一个 的不相交路径集合对应。
比较显然。
1-Dyck Path 就是卡塔兰路径。k-Dyck Path 是 条卡塔兰路径,但第二条必须完全在第一条“内部”,第三条必须完全在第二条内部……
一元素在 的 均为偶数的半标准杨表和 阶的 k-Dyck Path 对应,且公式如下
记录下每条 Dyck_Path 的由上方向转为右方向的拐角即可证明。
完结撒花。
因为我学不动了。