## Wednesday, May 2, 2018

### Combinatorics and probability : Greene, Nijenhuis and Wilf's proof of the hook length formula

I've never been very good at remembering representation theory, past the general facts that hold for all finite groups, especially the representation theory of symmetric groups.  So here are personal notes to help me understand the 1979 paper by Greene, Nijenhuis and Wilf, where they give a probabilistic proof of the hook length formula. If you already know what it is about, then you'd be quicker by browsing at the Wikipedia page that I just linked to!

Heroes of this story are partitions, Ferrers diagrams, and Young tableaux. Let us first give definitions.

A partition of an integer $n$ is a decreasing (US: non-increasing) sequence of integers $\lambda =(\lambda_1\geq \lambda_2\geq \dots\geq \lambda_m)$ of strictly positive integers such that $|\lambda|=\lambda_1+\dots+\lambda_m=n$.

The Ferrrers diagram $F(\lambda)$ of this partition $\lambda$ is the stairs-like graphic representation consisting of the first quadrant cells indexed by integers $(i,j)$, where $1\leq i\leq m$ and $1\leq j\leq \lambda_i$. Visualizing a partition by means of its Ferrers diagram makes clear that there is an involution on partitions, $\lambda\mapsto \lambda^*$, which, geometrically consists in applying the symmetry with respect to the diagonal that cuts the first quadrant. In formulas, $j\leq \lambda_i$ if and only if $i\leq \lambda_j^*$.

A Young tableau of shape $\lambda$ is an enumeration of the $n$ cells of this Ferrers diagram such that the enumeration strictly increases in rows and columns.

There is a graphic way of representing Ferrers diagrams and Young tableaux — the tradition says it's the Soviet way — consisting in rotating the picture by 45° ($\pi/4$) to the left and viewing the first quadrant as a kind of bowl in which $n$ balls with diameter $1$ are thrown from the top.

The hook length formula is a formula for the number $f_\lambda$ of Young tableaux of given shape $\lambda$.

For every $(i,j)$ such that $1\leq i\leq m$ and $1\leq j\leq \lambda_i$, define its hook $H_{ij}$ to be the set of cells in the diagram that are either above it, or on its the right — in formula, the set of all pairs $(a,b)$ such that $a=i$ and $j\leq b\leq \lambda_i$, or $i\leq a\leq m$ and $b=j\leq \lambda_a$. Let $h_{ij}$ be the cardinality of the hook $H_{ij}$.

Lemma. — One has $h_{a,b} = (\lambda_a-b)+(\lambda_b^*-a) +1$.

Indeed, $\lambda_a-b$ is the number of cells above $(a,b)$ in the Ferrers diagram of $\lambda$, excluding $(a,b)$, while $(\lambda_b^*-a)$ is the number of cells on the right of $(a,b)$.

Theorem (Frame, Thrall, Robinson; 1954). — Let $n$ be an integer and let $\lambda$ be a partition of $n$. The number of Young tableaux of shape $\lambda$ is given by
$f_\lambda = \frac{n!}{\prod_{(i,j)\in F(\lambda)} h_{ij}}.$

From the point of view of representation theory, partitions of $n$ are in bijection with conjugacy classes of elements in the symmetric group $\mathfrak S_n$ (the lengths of the orbits of a permutation of $\{1,\dots,n\}$ can be sorted into a partition of $n$, and this partition characterizes the conjugacy class of the given permutation). Then, to each partition of $n$ corresponds an irreducible representation of $\mathfrak S_n$, and $f_\lambda$ appears to be its dimension. (In a future post, I plan to explain this part of the story.)

As already said, the rest of this post is devoted to explaining the probabilistic proof due to Greene, Nijenhuis, and Wilf. (Aside: Nijenhuis is a Dutch name that should pronounced roughly like Nay-en uys.)

A corner of a Ferrers diagram is a cell $(i,j)$ which is both on top of its column, and on the right of its row; in other words, it is a cell whose associated hook is made of itself only. A bit of thought convinces that a corner can be removed, and furnishes a Ferrers diagram with one cell less. Conversely, starting from a Ferrers diagram with $n-1$ cells, one may add a cell on the boundary so as to get a Ferrers diagram with $n$ cells. In the partition point of view, either one part gets one more item, or there is one more part, with only one item. In a Young tableau with $n$ cells, the cell numbered $n$ is at a corner, and removing it furnishes a Young tableau with $n-1$ cells; conversely, starting from a Young tableau with $n-1$ cells, one can add a cell so that it becomes a corner of the new tableau, and label it with $n$.

Let $P(\lambda_1,\dots,\lambda_m)$ be the number on the right hand side of the Frame-Thrall-Robinson formula. By convention, it is set to be $0$ if $(\lambda_1,\dots,\lambda_m)$ does not satisfy $\lambda_1\geq\dots\geq\lambda_m\geq 1$. By induction, one wants to prove
$P(\lambda_1,\dots,\lambda_m) = \sum_{i=1}^m P(\lambda_1,\dots,\lambda_{i-1},\lambda_i-1,\lambda_{i+1},\dots,\lambda_m).$
For every partition $\lambda$, set
$p_i(\lambda_1,\dots,\lambda_m) = \frac{P(\lambda_1,\dots,\lambda_{i-1},\lambda_i-1,\lambda_{i+1},\dots,\lambda_m)}{P(\lambda_1,\dots,\lambda_m)}.$
We thus need to prove
$\sum_{i=1}^m p_i(\lambda)=1;$
which we will do by interpreting the $p_i(\lambda)$ as the probabilities of disjoint events.

Given the Ferrers diagram $F(\lambda)$, let us pick, at random, one cell $(i,j)$, each of them given equal probability $1/n$; then we pick a new cell, at random, in the hook of $(i,j)$, each of them given equal probability $1/(h_{ij}-1)$, etc., until we reach a corner of the given diagram. Such a trial defines a path in the Ferrers diagram, ending at a corner $(a,b)$; its projections  are denoted by $A=\{a_1<a_2<\dots\}$ and $B=\{b_1<b_2<\dots\}$. Let $p(a,b)$ be the probability that we reach the corner $(a,b)$; let $q(A,B)$ be the probability that its projections be $A$ and $B$ conditioned to the hypothesis that it start at $(\inf(A),\inf(B))$.

Lemma. — Let $A,B$ be sets of integers, let $a=\sup(A)$ and let $b=\sup(B)$;  assume that $(a,b)$ is a corner of $\lambda$. One has $q(A,B)= \prod_{\substack{i\in A\\ i\neq a}} \frac1{h_{i,b}-1} \prod_{\substack{j\in B\\ j\neq b}} \frac1{h_{a,j}-1}.$

We argue by induction on the cardinalities of $A$ and $B$. If $A=\{a\}$ and $B=\{b\}$, then $q(A,B)=1$, since both products are empty; this proves the formula in this case. As above, let $a_1<a_2<\dots$ be the enumeration of the elements of $A$ and $b_1<b_2<\dots$ be that for $B$; let also $A'=A\setminus\{a_1\}$ and $B'=B\setminus\{b_1\}$. By construction of the process, after having chosen the initial cell $(a_1,b_1)$,  it either goes on above the initially chosen cell $(a_1,b_1)$, hence at $(a_1,b_2)$, or on its right, that is, at $(a_2,b_1)$. One thus has
\begin{align*} q(A,B) = \mathbf P(A,B\mid a_1,b_1) & = \mathbf P(a_1,b_1,b_2\mid a_1,b_1) \mathbf P(A,B\mid a_1,b_1,b_2) + \mathbf P(a_1,a_2,b_1\mid a_1,b_1) \mathbf P(A,B\mid a_1,a_2,b_1)\\ &= \frac1{f_{a_1,b_1}-1} \mathbf P(A,B'\mid a_1,b_2) + \frac1{f_{a_1,b_1}-1} \mathbf P(A',B\mid a_2,b_1) \\ &= \frac1{h_{a_1,b_1}-1}\left( q(A',B) + q(A,B') \right). \end{align*}
By induction, we may assume that the given formula holds for $(A',B)$ and $(A,B')$. Then, one has
\begin{align*} q(A,B) & = \frac1{h_{a_1,b_1}-1} \left( \prod_{\substack{i\in A'\\ i\neq a}} \frac1{h_{i,b}-1} \prod_{\substack{j\in B \\ j\neq b}} \frac1{h_{a,j}-1} + \prod_{\substack{i\in A\\ i\neq a}} \frac1{h_{i,b}-1} \prod_{\substack{j\in B' \\ j\neq b}} \frac1{h_{a,j}-1}\right) \\ & =\frac{ (h_{a_1,b}-1)+(h_{a,b_1}-1)}{h_{a_1,b_1}-1} \prod_{\substack{i\in A\\ i\neq a}} \frac1{h_{i,b}-1} \prod_{\substack{j\in B \\ j\neq b}} \frac1{h_{a,j}-1}, \end{align*}
which implies the desired formula once one remembers that
$h_{a,b_1} + h_{a_1,b} = h_{a_1,b_1} + h_{a,b}= h_{a_1,b_1}+1$
since $(a,b)$ is a corner of $F(\lambda)$.

Proposition. — Let $(a,b)$ be a corner of the diagram $F(\lambda)$; one has $p(a,b)=p_a(\lambda)$. (Note that $b=\lambda_a$.)

Write $F_a(\lambda)$ for the Ferrers diagram with corner $(a,b)$ removed. Its $(i,j)$-hook is the same as that of $F(\lambda)$ if $i\neq a$ and $j\neq b$; otherwise, it has one element less. Consequently, writing $h'_{i,j}$ for the cardinalities of its hooks, one has
\begin{align*} p_a(\lambda) &= \frac1n \frac{\prod_{(i,j)\in F(\lambda)}h_{i,j}}{\prod_{(i,j)\in F_a(\lambda)} h'_{i,j}} \\ &= n \prod_{i<a} \frac{h_{i,b}}{h_{i,b}-1} \prod_{j<b}\frac{h_{a,j}}{h_{a,j}-1}\\ &=\frac1n \prod_{i<a}\left(1+ \frac1{h_{i,b}-1}\right) \prod_{j<b} \left(1+\frac1{h_{a,j}-1}\right). \end{align*}
Let us now expand the products. We get
$p_a(\lambda) = \frac1n \sum_{\sup(A)<a} \sum_{\sup(B)<b} \prod_{i\in A} \frac1{h_{i,b}-1}\prod_{j\in B}\frac1{h_{a,j}-1},$
where $A$ and $B$ range over the (possibly empty) subsets of $\{1,\dots,n\}$ satisfying
the given conditions $\sup(A)<a$ and $\sup(B)<b$. (Recall that, by convention, or by definition, one has $\sup(\emptyset)=-\infty$.) Consequently, one has
\begin{align*} p_a(\lambda) & =\frac1n \sum_{\sup(A)=a} \sup_{\sup(B)=b} \prod_{\substack{i\in A\\ i\neq a}} \frac1{h_{i,b}-1} \prod_{\substack{j\in B \\ j\neq b}} \frac1{h_{a,j}-1} \\ & = \frac1n \sum_{\sup(A)=a} \sum_{\sup(B)=b} q(A,B) \\ & = \sum_{\sup(A)=a} \sum_{\sup(B)=b} \mathbf P (A,B ) \\ & = p(a,b), \end{align*}
as claimed.

Now, every trial has to end at some corner $(a,b)$, so that
$\sum_{\text{(a,b) is a corner}} p(a,b) = 1.$
On the other hand, if $(a,b)$ is a corner, then $b=\lambda_a$, while if $(a,\lambda_a)$ is not a corner, then $P_a(\lambda)=0$. We thus get $\sum_a P_a(\lambda)=P(\lambda)$, as was to be shown.

#### 3 comments :

1. Errata:

- "sequence of integers" -> "sequence".

- "Ferrrers" -> "Ferrers".

- Add comma after "geometrically".

- Your "Young tableau" is commonly called "standard Young tableau". Not asking you to change the name, but it's worth mentioning at least once.

- "on its the right" -> "on its right, or $(i, j)$ itself".

- "In the partition point of view, either one part gets one more item, or there is one more part, with only one item." I'd speak of incrementing a part by $1$ or creating a new part equal to $1$, rather than of "items" (these are integer partitions, not set partitions). Also, worth saying what "part" means.

- You don't literally want $P(\lambda_1,\dots,\lambda_m)$ to be $0$ when $\lambda_1\geq\dots\geq\lambda_m\geq 1$ is not satisfied. After all, subtracting $1$ from the last entry of the partition might make that last entry $0$, and this should simply be considered as a partition with one fewer entry.

- After "in the hook of $(i, j)$", add "(but not $(i, j)$ itself)".

- "its projections" should be better explained IMHO.

- In the lemma, I'd require $A$ and $B$ to be nonzero, to avoid the question of what $\sup \varnothing$ is.

- In the second line of
"\begin{align*}
q(A,B) = \mathbf P(A,B\mid a_1,b_1)
& = \mathbf P(a_1,b_1,b_2\mid a_1,b_1) \mathbf P(A,B\mid a_1,b_1,b_2)
+ \mathbf P(a_1,a_2,b_1\mid a_1,b_1) \mathbf P(A,B\mid a_1,a_2,b_1)\\
&= \frac1{f_{a_1,b_1}-1} \mathbf P(A,B'\mid a_1,b_2)
+ \frac1{f_{a_1,b_1}-1} \mathbf P(A',B\mid a_2,b_1) \\
&= \frac1{h_{a_1,b_1}-1}\left( q(A',B) + q(A,B') \right). \end{align*}"
replace both $f$s by $h$s.

- In the second line of
"\begin{align*}
p_a(\lambda) &= \frac1n \frac{\prod_{(i,j)\in F(\lambda)}h_{i,j}}{\prod_{(i,j)\in F_a(\lambda)} h'_{i,j}} \\ &= n \prod_{i "$p_a(\lambda) = 0$".

- "$\sum_a P_a(\lambda)=P(\lambda)$" -> "$\sum_a p_a(\lambda)=1$".

PS. While I'm picking nits: On the first line of the proof of Proposition 2.4 of https://webusers.imj-prg.fr/~antoine.chambert-loir/enseignement/2015-16/agreg/resultant.pdf , "$A[T]_{m+n}$" should be "$A[T]_{< m+n}$". Also, in the proof of Corollary 2.6, it is useless to define $m = m_1 + m_2$ and $P = P_1P_2$ (you don't use these notations). In Section 3, you probably want to assume the ground ring to be a field. In Section 5.3, "Soit $p$ un nombre impair" should probably also require $p$ to be prime, and "et soit $a \in K$ une racine de $\Phi_p$" should be "et soit $a \in K$ une racine de $T_p$". In the proof of Théorème 5.4, "$Q(\alpha)$" should be "$T_q(\alpha)$". And in Exemple 1.8, "et soit $K$ une extension de $K$" should be "et soit $K$ une extension de $k$".

PPS. Your lecture notes are gorgeous; thanks a lot for them!

1. Just realized parts of my post have been cropped, probably due to <-signs being misunderstood as HTML. So let me repost them:

- In the second line of
"\begin{align*}
p_a(\lambda) &= \frac1n \frac{\prod_{(i,j)\in F(\lambda)}h_{i,j}}{\prod_{(i,j)\in F_a(\lambda)} h'_{i,j}} \\ &= n \prod_{i < a} \frac{h_{i,b}}{h_{i,b}-1} \prod_{j < b}\frac{h_{a,j}}{h_{a,j}-1}\\
&=\frac1n \prod_{i < a}\left(1+ \frac1{h_{i,b}-1}\right) \prod_{j < b} \left(1+\frac1{h_{a,j}-1}\right). \end{align*}"
replace $n$ by $\frac1n$.

- Honestly I'd find it easier to replace "$\sup(A) "$p_a(\lambda) = 0$". - "$\sum_a P_a(\lambda)=P(\lambda)$" -> "$\sum_a p_a(\lambda)=1$". 2. OK, that was better, but some parts are still missing. Next try: - Honestly I'd find it easier to replace "$\sup(A) < a$" by "$A \subseteq \left\{1,\ldots,a-1\right\}$", and similarly for$B$. That way you won't have to explain what you mean by the supremum of the empty set. - The "sup" in "\sup_{\sup(B)=b}" should be a \sum. - The boldfaced P in "\sum_{\sup(A)=a} \sum_{\sup(B)=b} \mathbf P (A,B ) " has never been defined. I assume it is meant to be the same as$q(A, B)$, except that we don't condition to any hypothesis on the starting cell of the trial. - "$P_a(\lambda) = 0$" -> "$p_a(\lambda) = 0$". - "$\sum_a P_a(\lambda)=P(\lambda)$" -> "$\sum_a p_a(\lambda)=1\$".