杨氏矩阵与钩子定理
* Young Tableau & Hook Length Formula *
这两天在群里偶然看到了有人提起杨氏矩阵与钩子定理, 于是心血来潮学习了一下这方面的有关知识(主要是在比赛中的应用).
Def: 杨表
- 由有限多个方格组成
- 给定一个整数的分拆 λ (如 10 = 1 + 4 + 5, 后一项大于等于前一项), 则对应一个杨表 $\pi_\lambda$. 即, 杨表与整数分拆 λ 一一对应.
n个格子组成杨表的个数由递推式得到:
- f(1) = 1;
- f(2) = 2;
- f(n) = f(n-1) + (n-1) * f(n-2);
Def: 勾长 (hook(i, j))
- 勾长是一个计数
- 对于一个杨表 $\pi_\lambda$, 设其分拆为 $\lambda = y_0 + y_1 + … + y_x$, 则 $hook(i, y_i) = x - i + 1$
- 否则 $hook(i, j) = hook(i, j+1) + 1$ 即. 对于杨表中的一个方格(i, j), 其勾长 hook(i, j)等于同行右边的方格数加上同列上面的方格数, 再加上1(也就是他自己).
Def: $dim_{\pi_\lambda}$
给定一个杨表 $\pi_\lambda$ , 将 1 - n 共 n 个数字填到杨表之中, 使得每一行以及每一列的元素大小都满足单调性. 用 $dim_{\pi_\lambda}$ 表示这样的方法数.
$dim_{\pi_\lambda} = \frac{n!}{\Pi_{p \in Y(\lambda)} * hook(p)}$
即: 方法个数 = n! / (所有方格勾长乘积)
ps: markdwon 好难用..
在给定的m行n列大小的杨表中查找指定的元素时间复杂度为O(m+n).
2018-04-19
参考:
