钩长公式（Hook Lenghth Formula）

· · 算法·理论

给定大小为 n 的杨表 \lambda=(\lambda_1,\lambda_2,\dots)。定义一个格子 (i,j) 的钩长 h_{i,j} 等于其右侧下侧以及它本身的全部格子数量。

现要求用 1\sim n 填充格子使每行每列递增。求方案数。

结论：答案等于

H(\lambda)=\frac{n!}{\prod h_{i,j}}

证明：

【学习笔记】杨表的拓扑序计数与钩长公式 - suncongbo - 博客园

钩长公式(Hook Length Formula)：杨表中的计数结论 - 知乎

设 F(\lambda) 表示标准答案。注意到 n 一定在某个“角落”，考虑简单的 dp。

枚举 n 所处的位置是第 i 个角落 (\alpha_i,\beta_i)，并设 \mu_i 表示一个杨表，其由 \lambda 抠去 (\alpha_i,\beta_i) 得到，记为 \mu_i\uparrow\lambda。

显然

F(\lambda)=\sum_{\mu\uparrow\lambda}F(\mu)

现在转为证明上面定义的 H(\lambda) 具有同样的递推式。

H(\lambda)=\sum_{\mu\uparrow\lambda}H(\mu)\Longleftrightarrow \sum_{\mu\uparrow\lambda}\frac{H(\mu)}{H(\lambda)}=1

归 1 启示我们使用概率。将 H 按定义式拆开并化简。关注求和的其中一项 \mu_i，其由 \lambda 抠去 (\alpha,\beta) 得到：

\frac{H(\mu)}{H(\lambda)}=\frac{1}{n}\prod_{i=1}^{\alpha-1}(1+\frac{1}{h_{i,\beta}-1})\prod_{j=1}^{\beta-1}(1+\frac{1}{h_{\alpha,j}-1})=\frac{1}{n}\sum_{A\subseteq\{1,\dots,\alpha-1\}\\B\subseteq\{1,\dots,\beta-1\}}\prod_{i\in A}\frac{1}{h_{i,\beta}-1}\prod_{j\in B}\frac{1}{h_{\alpha,i}-1}

定义 hook-walk：

关注求和的一个 A,B，右边的乘积是：

第一步降落 (A_1,B_1)，在 (\alpha,\beta) 终止的全部 hook-walk 路径中，经过的行列集合分别是 A,B 的概率。

原因是，行列的行走是独立的。因此概率相乘。上面的两篇博客使用的是 dp 归纳。\Box

那么整个求和的结果就是最终到达 (\alpha,\beta) 的概率。即

\mathbb{P}(c=(\alpha,\beta))=\frac{H(\mu)}{H(\lambda)}

所以得到

\sum_{\mu\uparrow\lambda}\frac{H(\mu)}{H(\lambda)}=\sum \mathbb{P}(c=(\alpha_i,\beta_i))=1 \Box