杨表钩长公式证明
zt17
·
·
算法·理论
前言
本文为钩长公式(Hook Length Formula)：杨表中的计数结论 - 陆其而的学习笔记，在此特别鸣谢。
感觉很有意思，于是写了！
一些定义：
定义 \lambda = \{\lambda_1,\lambda_2,\cdots,\lambda_m\} 为整数 n 的划分，其中需要满足 \lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_m 且 \sum\limits_{i=1}^m \lambda_i = n。
将 n 个方格在垂直方向上进行个数单调的排列，可以得到一个大小为 n 的杨图（Young diagram）。
对于一个杨图 $\lambda$，记方格 $(x,y)$ 下方的格子数量加上右边的格子数量再加上它本身为它的钩长，记作 $h_\lambda(x,y)$。
在大小为 $n$ 的杨图中填入 $1 \sim n$ 的整数，同时满足每行单调递增，每列单调递增，就可以得到一个杨表（Young tableau）。
对于往一个大小为 $n$ 的杨图 $\lambda$ 填数可以得到的杨表数量 $f(\lambda)$，有**钩长公式（Hook Length Formula）**：
$$
f(\lambda) = \frac{n!}{\prod\limits_{(x,y)\in\lambda} h_\lambda(x,y)}
$$
接下来我们将证明这个式子。
## 证明
不妨单独开一个函数 $g(\lambda) = \frac{n!}{\prod_{(x,y)\in\lambda} h_\lambda(x,y)}$，**问题转化为证明 $f(\lambda) = g(\lambda)$**。
我们不妨想想 $n$ 被填在哪个格子，不难发现它一定被填在一个角格。我们令**角格的集合**为 $L$，第 $i$ 个边界格子为 $L_i = (a_i,b_i)$。
对于 $f(\lambda)$ 而言，有递推式 $f(\lambda) = \sum_{i\in L(\lambda)} f(\lambda - L_i)$，其中 $-$ 运算符表示在杨表中去掉一个格子后得到的杨表。
由于 $f(\varnothing) = g(\varnothing) = 1$，则 $g(\lambda) = \sum_{i\in L(\lambda)} g(\lambda-L_i)$ 为 $f(\lambda) = g(\lambda)$ 的充要条件。
至此，我们把问题转化为了**证明递推式 $g(\lambda) = \sum_{i} g(\lambda-L_i)$**，其中 $g(\lambda) = \frac{n!}{\prod_{(x,y)\in\lambda} h_\lambda(x,y)}$。
---
进一步简化这个递推式，有 $\sum_{i} \frac{g(\lambda-L_i)}{g(\lambda)} = 1$。
接下来，我们将定义一个在杨表 $\lambda$ 上随机游走（称为 Hook Walk）的过程：
1. 在 $\lambda$ 中随机选择一个位置 $(x,y)$ 为起点。
2. 在 $(x,y)$ 的钩子中去掉它本身后的 $h_\lambda(x,y) - 1$ 个方格中随机选择一个方格 $nxt$。
3. 跳到下一个方格 $(x,y) \leftarrow nxt$。
4. 重复 2、3 步骤直到 $h_\lambda(x,y) = 1$，我们称 $(x,y)$ 为本次随机游走的**终止节点**。
记 $P(L_i)$ 为**终止节点为 $L_i$ 的概率**。首先显然有 $\sum_i P(L_i) = 1$。可以证明 $P(L_i) = \frac{g(\lambda-L_i)}{g(\lambda)}$，带入前面那个求和式子以后递推式得证，即定理得证。
至此，我们把问题转化为了**证明引理 $P(L_i) = \frac{g(\lambda-L_i)}{g(\lambda)}$**。
---
下面我们对于单个角格 $L_i = (a_i,b_i)$ 求证 $P(L_i) = \frac{g(\lambda-L_i)}{g(\lambda)}$，为了简化书写，下文 $(a_i,b_i) \rightarrow (a,b),h_\lambda(x,y) \rightarrow h(x,y)$；对于集合 $S$，记 $S_i$ 为 $S$ 中第 $i$ 小的数。
固定终点为 $(a,b)$，令 $p_{A,B}$ 表示随机游走中选择了起点 $(A_1,B_1)$ 后经过的横纵坐标形成的有序集合恰好为 $A,B$ 的概率，那么有动态规划式子：
$$
p_{A,B} = \frac{1}{h(A_1,B_1) - 1} (p_{A-A_1,B} + p_{A,B-B_1})
$$
下面我们将用**归纳法**证明下式：
$$
p_{A,B} = \prod_{i \in A} \frac{1}{h(i,b) - 1} \prod_{j \in B} \frac{1}{h(a,j) - 1}
$$
首先特别定义 $p_{\varnothing,\varnothing} = 1$ 表示随机起点即为 $(a,b)$ 后的概率，满足上式。
对于当前 $p_{A,B}$，我们归纳假设 $|A'| + |B'| <|A| + |B|$ 的 $p_{A',B'}$ 上式成立。
令 $R = \prod_{i \in A} \frac{1}{h(i,b) - 1} \prod_{j \in B} \frac{1}{h(a,j) - 1}$，则有：
$$
\begin{aligned}
p_{A-A_1,B} &= R \times (h(A_1,b) - 1), \\
p_{A,B-B_1} &= R \times (h(a,B_1) - 1)
\end{aligned}
$$
那么，根据上面的动态规划式子，有：
$$
p_{A,B} = R \times \frac{h(A_1,b) - 1 + h(a,B_1) - 1}{h(A_1,B_1) - 1}
$$
我们仅需证明后面那个系数等于 $1$ 即完成归纳证明。
画个图：
不难发现 $h(A_1,b) - 1 + h(a,B_1) - 1 = h(A_1,B_1) - 1$。
至此，我们证明了 $p_{A,B} = \prod_{i \in A} \frac{1}{h(i,b) - 1} \prod_{j \in B} \frac{1}{h(a,j) - 1}$。
而：
$$
\begin{aligned}
P(L_i) &= \frac{1}{n} \sum_{A,B} p_{A,B} \\
&= \frac{1}{n} \sum_{A,B} \prod_{i \in A} \frac{1}{h(i,b) - 1} \prod_{j \in B} \frac{1}{h(a,j) - 1} \\
&= \frac{1}{n} \prod_{1 \le i < a} (1 + \frac{1}{h(i,b)-1}) \prod_{1 \le j < b} (1 + \frac{1}{h(a,j) - 1}) \\
&= \frac{1}{n} \prod_{1 \le i < a} \frac{h(i,b)}{h(i,b)-1} \prod_{1 \le j < b} \frac{h(a,j)}{h(a,j) - 1} \\
\frac{g(\lambda-L_i)}{g(\lambda)} &= \frac{\frac{(n-1)!}{\prod h_{\lambda-L_i}(x,y)}}{\frac{n!}{\prod h_\lambda(x,y)}} \\
&= \frac{1}{n} \times \prod_{1 \le i < a} \frac{h(i,b)}{h(i,b)-1} \times \prod_{1 \le j < b} \frac{h(a,j)}{h(a,j) - 1} \\
&= P(L_i)
\end{aligned}
$$
（第一行的 $\frac{1}{n}$ 是选择起点的概率，第三行是经典转换，倒数第二行注意到只有一部分的方格钩长变了）
至此，我们完整证明了 $\sum_{i} \frac{g(\lambda-L_i)}{g(\lambda)} = 1$，即完整证明了 $f(\lambda) = g(\lambda)$。
## 后记
好难啊。