Skip to main content

__debug's Home Keep it simple, stupid

Young Tableau & Hook length formula

挺有意思的一个东西, 虽然貌似在 OI 里没有什么用…

引入

我们先来看 yyt 爷出的一道题:

给定 \(n\) 和 \(a_i\), 满足 \(a_0 \ge a_1 \ge \cdots \ge a_{n-1} \ge 0\), 求出在 \(n\) 维空间中从 \((0, 0, ..., 0)\) 走到 \((a_0, a_1, ..., a_{n-1})\), 每一步使某一维坐标增加 \(1\) 的方案中随机选出一种, 满足经过的所有点 \((x_0, x_1, ..., x_{n-1})\) 都满足 \(x_0 \ge x_1 \ge \cdots \ge x_{n-1}\) 的概率.

答案模 \(1004535809\) 输出.

\(n = 2\) 的情况就是经典的反射法, 用组合数搞一下就行了.

这样是不是给人一种经典问题的感觉? 事实上的确是一个经典问题.

Young Tableau

Young_tableaux_for_541_partition.svg

如上图就是一个 \((5, 4, 1)\) 的标准杨氏矩阵. 我们发现, 那道题实际上就是要求将 \(1..n\) 这 \(n\) 个数字填入这个图中, 使得每行从左到右都是递增的,每列从下到上也是递增的.

Hook length formula

上面的方案数等于 $$\frac{n!}{\prod h_{ij}}$$

其中 \(n\) 为格子数, \(h_{ij}\) 为满足 \(a = i, b \ge j\) 或 \(a \ge i, b = j\) 的格子 \((a, b)\) 的数量. 下面这张图的 \(n = 9\), 格子上的数字就是 \(h_{ij}\).

Hook-length_tableau_December_8_2013_3.jpg

证明思路

详细证明参见 Greene, C., Nijenhuis, A. and Wilf, H. S. (1979). A probabilistic proof of a formula for the number of Young tableaux of a given shape. Adv. in Math. 这里只说一些大体的思路.

首先引入边角的概念:

Corners_of_young.png

记 \(F\) 表示总方案数, \(F_{\alpha\beta}\) 表示去掉 \((\alpha,\beta)\) 这个边角后的方案数. 显然有 $$F = \sum_{(\alpha,\beta)} F_{\alpha\beta}$$

也就是 $$\sum_{(\alpha,\beta)} \frac{F_{\alpha\beta}}{F} = 1$$

我们需要证明, 如果 \(F = \frac{n!}{\prod h_{ij}}\), 这个递推式可以满足 (边界显然满足).

显然

\begin{align*} \frac{F_{\alpha\beta}}{F} &= \frac{1}{n} \prod_{1 \le i < \alpha} \frac{h_{i\beta}}{h_{i\beta}-1} \prod_{1 \le j < \beta} \frac{h_{\alpha j}}{h_{\alpha j}-1} \\ &= \frac{1}{n} \prod_{1 \le i < \alpha} \left(1 + \frac{1}{h_{i\beta}-1}\right) \prod_{1 \le j < \beta} \left( 1 + \frac{1}{h_{\alpha j}-1} \right) \end{align*}

通过一些巧妙的转化, 我们可以证明 $$\frac{F_{\alpha\beta}}{F} = p(\alpha, \beta)$$

其中 \(p(\alpha, \beta)\) 表示等概率任选一个格子出发, 每次等概率选择一个同一行或同一列的后继格子 (对于 \((i, j)\) 而言有 \(h_{ij}-1\) 种选择), 最终走到边角 \((\alpha, \beta)\) 的概率.

证明还需要一个技巧: 按路径按经过的行和列进行分类, 同一种路径在一起考虑; 又根据 $$h_{ab} - 1 = (h_{a_1 \beta} - 1) + (h_{\alpha b_1} - 1)$$

然后大力归纳一下就好了… 这一部分还是看论文比较好…

做法

回到那道题.

用 Hook length formula 直接计算的复杂度是 \(O(na_0)\) 的, 考虑优化.

不难发现

\begin{align*} \prod_{i, j} h_{ij} &= \prod_{i} \frac{(a_i + n - i - 1)!}{\prod_{j \ge i} (a_i - a_j + j - i)} \\ &= \left(\prod_{i} (a_i + n - i - 1)!\right) \frac{1}{\prod_{i \le j} \left[(a_i - i) - (a_j - j)\right]} \end{align*}

考虑如何快速计算 \(\prod_{i \le j} \left[(a_i - i) - (a_j - j)\right]\). 容易发现右边很像一个卷积的形式… 我们只需求出 \(cnt(x)\) 表示在所有 \(i \le j\) 中, \(x\) 贡献了多少次, 最后将 \(x^{cnt(x)}\) 加入答案即可. FFT 即可.

Comments

Comments powered by Disqus