参考资料:论文集2019《浅谈杨氏矩阵在信息学竞赛中的应用》袁方舟,《对称群笔记》Wenchao Zhang。

引入

杨图,杨表,勾长公式

杨图(记为 )大概就是一个长成这样的东西:

每行的列数称为 单调不增,和为 ,称为

你要往里面填 的排列,使得行单调增列单调增,这样的一种填充称为标准杨表。杨表数量由下面的勾长公式给出。

是杨图中格子 勾长,等于其下方格子个数+右方格子个数+1。

标准杨表总数为

也可以完全只用 表达:

半标准杨表,勾长公式

即行不严格递增,列严格递增的杨表。

设值域为 ,半标准杨表数为

斜杨图

即从一个杨图 中扣掉另一个杨图 。不连通也没关系。

一个兴奋图写出这个东西的英文名可能导致寿命减少)是指, 经过一系列的兴奋运动形成的 的某个子集。对 的兴奋运动是指,将一个下方右方右下方都属于 的属于 的方格移动到其右下方。

如图是 的所有可能的兴奋图。记为 。如下是勾长公式。

RSK 算法,杨表与 LIS 问题

下面我们将揭示杨图和排列的深刻联系。先引入 算法。

RSK 算法

行插入

定义 是把 从第一行行插入进近似标准杨表(即填入的元素不必是 中。流程如下:

如下演示了一个行插入过程。

显然最后新增的格子一定在边角,即其下方和右方都没有格子。

对于对 的第 插入,在另一个杨表 中在新增的格子上写上 (注意不是插入)。显然 是标准杨表。我们称 插入表记录表

删除

下面定义从 中删除格子 。尽管看起来不必要,我们还是规定 必须是边角。记 中填的数是 。流程如下:

结束算法后删掉已经没有数的格子

如下演示了一个删除过程。

很明显删除就是行插入的逆操作。

考虑一个 的排列,依次插入即可得到两个杨表 ;给定 ,显然 中最大元素一定在边角,于是我们可以按 的指导去删除 来还原原来的排列。

于是也就得到了以下的Robinson–Schensted correspondence

上述算法构成了 的一一映射。也就是说,

不禁让人联想到 prüfer 序列。

同时对于置换(当然也是排列),我们有 ,从而每一个标准杨表 对应一个对合,即逆等于自身的置换。对对合计数,我们得到:

其中双阶乘 定义为

RSK 算法和半标准杨表

一个广义置换大概可以理解为可重集上的置换,比如

它对应一个广义置换矩阵,这个矩阵的第 列表示 的个数。

我们有

一个广义置换和一个半标准杨表对一一对应。具体来讲就是运行 RSK 算法,把第二行的元素插入 中记录第一行的元素。

而如果有广义置换矩阵 ,则

杨表和 LIS 问题

LIS 即最长上升子序列,LDS 即最长下降子序列。

显然有如下结论:

「CTSC2017」最长上升子序列

根据 Dilworth 定理,一个序列的 LIS 的长度等于将其分为若干个不上升子序列所需数量的最小值。那么最长的 就是 对应的“ 杨表”的前 行长度之和。

不幸的是直接暴力实现杨表插入是 的。考虑根号分治,分别维护前 行和前 列。对于前 列,它就是对应的“ 杨表”(标准杨表)的前 行。

明明和杨表没有深入关系,但是不会杨表就做不了的屑题

[BJWC2018]最长上升子序列

爆枚杨表形态即可。整数拆分 渐进意义上等于

顺瑇一提这个公式是拉马努金发现的(

杨表和网格图路径数

是点 到点 的路线的集合,每一步只能往右边走或者往上方走。两条路径相交即有公共点。显然

卡塔兰数

卡塔兰数的组合意义即从 走到 ,任何时刻横坐标不能小于纵坐标。考虑 为横坐标到达 的时间, 亦然,那么它就对应如下的一个杨表。

显然一个 的标准杨表和路径一一对应。从而 的标准杨表数即卡塔兰数。

「雅礼集训 2017 Day11」PATH

显然题目要求的路径对应一个 的杨表。式子化出来是

FFT 统计有多少对 满足 ,然后就好了。

LGV 引理

给出平面上的 个点对 ,记 。则从 中各取一条路径,使得它们互不相交的方案数为

事实上该引理适用于所有有向无环图。

考虑容斥掉所有存在相交的方案。对于一个相交的方案,我们找到一个最大(这个最大可以任意定义,只要唯一即可)的相交点,则我们可以交换相交后的这条路径。

为了让它们相互抵消,交换后容斥系数应当乘以 -1。我们发现这正是置换的符号 的定义。(-1 的逆序对个数次方)写出式子:

这正是行列式的定义。

和卡塔兰数类似,不相交路径集合也和杨表有对应。

一个元素在 的半标准斜杨表 和一个 的不相交路径集合对应。

比较显然。

k-Dyck Path

1-Dyck Path 就是卡塔兰路径。k-Dyck Path 是 条卡塔兰路径,但第二条必须完全在第一条“内部”,第三条必须完全在第二条内部……

一元素在 均为偶数的半标准杨表和 阶的 k-Dyck Path 对应,且公式如下

记录下每条 Dyck_Path 的由上方向转为右方向的拐角即可证明。

后记

完结撒花。

因为我学不动了。