杨表学习笔记

rui_er · 2023-01-24 16:17:32 · 算法·理论

杨表学习笔记

简介

更好的阅读体验（其中折叠了例题的题解和代码）。

杨表（Young tableau）是一种常用于表示论和舒伯特演算中的组合对象，在数学中被用于对称群和一般线性群的研究。阿尔弗雷德·杨（Alfred Young）于 1900 年提出了杨表。

杨图

定义

杨图（Young diagram）又称 Ferrers 图，是一个有限的单元格集合，其中每一行左对齐，且每一行的长度不严格递减（也有一种画法是不严格递增）。

设杨图的总单元格数为 n，则每一行的格数构成了 n 的一种整数分拆 \lambda。我们可以用 \lambda 表示杨图。

例如，\lambda=(5,4,1) 的杨图如下：

杨图中的每一个单元格用行数和列数唯一确定。在本文的画法中，行数、列数分别是从上往下、从左往右数；而在刚刚提到的另一种画法中，行数是从下往上数。换句话说，行数按单元格数从多到少的方向，列数从左对齐的方向。

对于 n 个单元格的杨图 \lambda 和 n-1 个单元格的杨图 \mu，若 \exists j,\textrm{s.t.}\forall i\ne j,\lambda_i=\mu_i,\lambda_j=\mu_j+1，记 \mu\uparrow\lambda。

臂长、腿长、勾长

杨图的每个单元格 (x,y) 有臂长（arm length）、腿长（leg length）、勾长（hook length）：

• 臂长为这个单元格右面的单元格个数，记作 a_\lambda(x,y)。
• 腿长为这个单元格下面的单元格个数，记作 l_\lambda(x,y)。
• 勾长为这个单元格及其右面、下面的单元格总数，记作 h_\lambda(x,y)。由定义有 h_\lambda(x,y)=a_\lambda(x,y)+l_\lambda(x,y)+1。

杨表

定义

杨表（Young tableau）是用某个字母表的符号填充杨图得到的，字母表通常需要是全序集合。为了方便，一般填入正整数。

标准杨表（standard Young tableau）是满足每列数字严格递增、每行数字严格递增的杨表。

半标准杨表（semistandard / column-strict Young tableau）是满足每列数字严格递增、每行数字非严格递增的杨表。

标准杨表的 RSK 插入算法

RSK 插入算法由 Robinson、Schensted、Knuth 提出，它可以将杨表和排列联系起来。

要将 k 插入杨表 S 中，算法流程如下：

• 移动到第一行。
• 在该行中找到比 k 大的最小数 k'。
• 如果 k' 存在，将原本是 k' 的单元格替换为 k，然后令 k\gets k'，移动到下一行并重复步骤二。
• 如果 k' 不存在，将 k 放到该行末尾。

容易证明在上述算法过后，S 仍然是标准杨表。

杨表性质

将排列 p_1,p_2,\cdots,p_n 按 RSK 插入算法依次插入得到杨表 S，有性质：

• 第一行长度 S_1 为排列的 LIS 长度（内容不一定）。
• 第一列长度为排列的 LDS 长度（内容不一定）。
• 若将排列 p_n,p_{n-1},\cdots,p_1 插入杨表 S'，则 S' 是 S 交换行列得到。
• 更换全序集合的比较方式 \prec 为 \succ，杨表 S' 的形状是 S 交换行列得到（内容不一定）。

一些结论

勾长公式（hook length formula）

设有 n 个单元格的杨图 \lambda，在其中填入 1\sim n 的排列，得到的标准杨表数为 d_\lambda，则有：

例如，对于杨图 \lambda=(5,4,1)，有：

证明：（参考 杨表和钩子公式）

设 c_1,\cdots,c_m 为 h_\lambda(x,y)=1 的单元格，记 \mu_i=\lambda/\{c_i\}，则 \{\mu_1,\cdots,\mu_m\}=\{\mu\mid\mu\uparrow\lambda\}。

显然 d_\lambda=\sum\limits_{\mu\uparrow\lambda}d_\mu。设 e_\lambda=\frac{n!}{\prod h_\lambda(i,j)}，我们规定 d_\emptyset=e_\emptyset=1，只需证明 e_\lambda=\sum\limits_{\mu\uparrow\lambda}e_\mu 即可归纳得 d_\lambda=e_\lambda。

对 e_\lambda=\sum\limits_{\mu\uparrow\lambda}e_\mu 变形得 \sum\limits_{i=1}^m\frac{e_{\mu_i}}{e_\lambda}=1。

定义勾行走（hook walk）：

• 随机选取单元格 (x,y)\in\lambda 作为起点。
• 每次从 (x,y) 等概率地走到它下面、右面的共 h_\lambda(x,y)-1 格中的一个随机格子。
• 若不能再行走（即走到某个 c_i），则行走结束。

设随机事件 A_i 表示终点为 c_i，显然有 \sum\limits_{i=1}^mP(A_i)=1，只需证 P(A_i)=\frac{e_{\mu_i}}{e_\lambda}。

注意到 h_\lambda(x,y)+h_\lambda(x+1,y+1)=h_\lambda(x+1,y)+h_\lambda(x,y+1)，构造矩阵 h：

构造矩阵 p：

引理：\sum\limits_{i=0}^x\sum\limits_{j=0}^yp_{i,j}=\prod\limits_{i=0}^x\left(1+\frac{1}{h_{i,0}}\right)\prod\limits_{j=0}^y\left(1+\frac{1}{h_{0,j}}\right)。

证明：

容易验证 x,y\in\{0,1\} 成立。

有 h_{x,y}=h_{x,0}+h_{0,y}。设 S(x,y)=\sum\limits_{i=0}^x\sum\limits_{j=0}^yp_{i,j}，可以归纳知 S(x,0) 和 S(0,y) 时上式成立。

若 S(x-1,y),S(x,y-1),S(x-1,y-1) 上式均成立，则：

引理得证。\square

对于任意 (x_0,y_0)，令 h_{x,0}=h_\lambda(x_0-x,y_0)-1,h_{0,y}=h_\lambda(x_0,y_0-y)-1，则有 h_{x,y}=h_\lambda(x_0-x,y_0-y)-1，p_{x,y} 为从 (x_0-x,y_0-y) 走到 (x_0,y_0) 的概率。

令 (x_0,y_0)=c_i，则：

Robinson–Schensted correspondence

任意两个相同形状的杨表（填数可能不同），可以与排列建立一一对应。

即：

其中 \mathcal P_n 为 n 的所有分拆数，有结论 |\mathcal P_n|\sim\frac{1}{4\sqrt{3}n}\textrm{e}^{\sqrt{\frac{2n}{3}}\pi}（A000041）。

排列到双杨表的映射：

维护插入杨表 P 和记录杨表 Q。

依次枚举排列 p 中的元素 p_i，使用 RSK 插入算法将其插入 P 中。此时 P 中多了一个单元格，在 Q 的相同位置添加一个单元格并填入 i。

例如，p=[1,5,7,2,8,6,3,4] 得到的两个杨表如下：

双杨表到排列的映射：

根据填数从大到小枚举 Q 的单元格，从后往前确定排列 p。

枚举到一个单元格，在 P 中找到对应的单元格。若在第一行则直接删除，否则在上一行找到比它小的最大数，将它放到那里并继续删除被替换的数。

其实就是 RSK 插入算法的逆过程。

题目

CF1268B Domino for Young

给定一个杨图，求最多放多少不重叠的骨牌。

当黑白不相等时，先按上述过程删成 \lambda=(k,k-1,\cdots,2,1)，我们删除顶端的格子然后继续做即可。显然顶端的格子一定是更多的那种颜色。

复杂度为 \mathcal O(n)。

代码

// Problem: CF1268B Domino for Young
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1268B
// Memory Limit: 250 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 3e5+5;

ll n, a[N], cnt[2];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

int main() {
    scanf("%lld", &n);
    rep(i, 1, n) {
        scanf("%lld", &a[i]);
        cnt[i&1] += a[i] >> 1;
        cnt[(i&1)^1] += a[i] - (a[i] >> 1);
    }
    printf("%lld\n", min(cnt[0], cnt[1]));
    return 0;
}

P4484 [BJWC2018]最长上升子序列

求长度为 n 的随机排列 LIS 长度的期望。