jcreed blog > Understanding the Hook Length Formula

Understanding the Hook Length Formula

Some Definitions

A Young diagram is a collection of boxes (or "cells") arranged in left-justified rows, with the row lengths in non-increasing order. We use $\lambda$ as a variable Young diagrams, and write $|\lambda|$ for the number of boxes in $\lambda$. A standard tableau on $\lambda$ is a way of putting the numbers $1,\ldots,|\lambda|$ in all the cells of $\lambda$, such that the numbers always decrease when we move down or to the right. We write $T(\lambda)$ for the set of standard tableaux on $\lambda$. A corner in $\lambda$ is a cell that has no neighbors down or to the right. We write $C(\lambda)$ for the set of corners in $\lambda$. The hook of a cell is the set of cells to the right and down from that cell, including the cell itself. A pointer tableau on a Young diagram is a way of assigning each cell a "pointer" to some cell in its hook. In other words, a way of assigning numbers and a direction ("right" or "down") in some cells, such that if we move that many cells in that direction, we stay inside the diagram. Alternatively, we may leave a cell blank to mean that it points to itself --- and we must do so for corner cells, since they are the only cell in their hook. We write $P(\lambda)$ for the set of pointer tableaux on $\lambda$. A strict pointer tableau is a pointer tableau where all of the non-corner cells points to a different cell, not to themselves. We write $P^\x(\lambda)$ for the set of strict pointer tableaux on $\lambda$. If $c$ is some particular corner of a Young diagram, then a pointer tableau strict away from $c$ is a pointer tableau that is strict outside of $c$'s row and $c$'s column. We write $P_c^\x(\lambda)$ for the set of pointer tableaux on $\lambda$ that are strict away from $c$. The "Hook-Length Formula" is a way of counting how many Young tableaux on a diagram $\lambda$ there are. It asserts: \[ |T(\lambda)| = {|\lambda|!\over |P(\lambda)| }\] Ideally, we'd like to prove this by a well-behaved ("combinatorial", "bijective") proof. That is, we expect there to be an explanation of the above identity between numbers by way of showing the existence of a bijection between sets: \[ T(\lambda) \x P(\lambda) \cong S_{|\lambda|}\] where $S_n$ is the set of permutations of $n$ things.

However, this is a bit hard to obtain. It seems to have been achieved in "A Direct Bijective Proof of the Hook-Length formula" [Novelli, Pak, Stoyanovskii, 1997] but I don't understand their paper yet.

I read "A Probabilistic Proof of a Formula for the Number of Young Tableaux of a Given Shape " [Greene, Nijenhuis, Wilf, 1979] and tried to "bijectionify" it, and I found I was able to get a bijection \[ T(\lambda) \x P(\lambda) \x \Delta \cong S_{|\lambda|} \x \Delta\] for an 'auxiliary' set $\Delta$. I think in doing so I have recapitulated the algorithm in "A short hook-lengths bijection inspired by the Greene-Nijenhuis-Wilf proof" [D. Zeilberger, 1984].

Lemmas

There are two key bijective lemmas we need to establish. One is pretty trivial, and the other is arguably the central idea of [Greene, Nijenhuis, Wilf, 1979].

Lemma 1 For any $\lambda$ and $c \in C(\lambda)$, we have $P(\lambda) P^\x(\lambda) \cong P(\lambda - c) P^\x_c(\lambda)$.
Proof: Given a pointer tableau $t_1$ and a strict pointer tableau $t_2$ and a choice of corner $c$: we swap some data between the two tableaux, namely all data in the row and column of the corner. The only subtlety is that when we introduce strict pointer tableau data into the smaller diagram $\lambda - c$, we must remove any pointer that points to $c$, replacing it with a self-pointer, as shown in the red cells in the example below. This yields a pointer tableau $t_1'$ on $\lambda - c$, and a pointer tableau $t_2'$ that is strict away from $c$. This process is reversible. $\cqed$

Lemma 2 For any $\lambda$ with $|\lambda| = n$, \[n P^\x(\lambda) \cong \sum_{c \in C(\lambda)} P^\x_c(\lambda)\] Proof: An element of $n P^\x(\lambda)$ is a choice of "starting cell" in the diagram ($n$) together with a pointer tableau $P^\x(\lambda)$. We must produce a choice of corner $c$ and a pointer tableau that is strict away from $c$.

To determine the corner $c$, we take the starting cell and iteratively move according to the pointer tableau. This will inevitably lead to some corner. Now erase every number that occurs along the path taken, and flip the direction. If a path cell is in the row or column of the final corner, erase its direction as well. For each direction path cell left, follow its direction until you reach the row or column of the corner. We are going to "steal" from these cells in the row or column of the selected corner. If the "stolen" cell is pointing in the same direction as the path cell, we keep the same target cell that the pointer used to have, which means increasing its number. If it points in the opposite direction as the path cell, we simply move the "stolen" cell to the path cell's position, keeping its offset and direction intact. Here is the final state: we have produced a pointer tableau that is strict away from the corner $c$. The reader can check that the procedure above is reversible, establishing that we have a bijection \[n P^\x(\lambda) \cong \sum_{c \in C(\lambda)} P^\x_c(\lambda)\] as required. $\cqed$

Main Theorem

Now we can prove the main theorem. We write $\mu < \lambda$ when $\mu$ is a strict subdiagram of the Young diagram $\lambda$, and $\mu \le \lambda$ when it is a maybe equal subdiagram.

Theorem For any $\lambda$, we have \[ T(\lambda) \x P(\lambda) \x \prod_{\mu \le \lambda} P^\x(\mu)\cong S_{|\lambda|} \x \prod_{\mu \le \lambda} P^\x(\mu)\] Proof: By induction on the size $|\lambda|=n$ of $\lambda$. Observe that any standard tableau arises from a standard tableau with one chosen corner removed, so that \[T(\lambda) = \sum_{c \in C(\lambda)} T(\lambda - c)\] This means \[T(\lambda) \x P(\lambda) \x \prod_{\mu \le \lambda} P^\x(\mu) \cong \sum_{c \in C(\lambda)} T(\lambda - c) \x P(\lambda) \x \prod_{\mu \le \lambda} P^\x(\mu)\] \[\cong \sum_{c \in C(\lambda)} T(\lambda - c) \x P(\lambda) \x P^\x(\lambda) \x \prod_{ \mu < \lambda} P^\x(\mu)\] which by Lemma 1 is \[\cong \sum_{c \in C(\lambda)} T(\lambda - c) \x P(\lambda - c) \x P^\x_c(\lambda) \x \prod_{ \mu < \lambda} P^\x(\mu)\] \[\cong \sum_{c \in C(\lambda)} T(\lambda - c) \x P(\lambda - c) \x \left(\prod_{ \mu < \lambda -c} P^\x(\mu)\right) \x P^\x_c(\lambda) \x \prod_{ \mu < \lambda, \mu \not\le \lambda - c} P^\x(\mu)\] which by the induction hypothesis is \[\cong \sum_{c \in C(\lambda)} S_{n-1} \x \left(\prod_{ \mu \le \lambda -c} P^\x(\mu)\right) \x P^\x_c(\lambda) \x \prod_{ \mu < \lambda, \mu \not\le \lambda - c} P^\x(\mu)\] \[\cong \left(\sum_{c \in C(\lambda)} P^\x_c(\lambda)\right) \x S_{n-1} \x \prod_{ \mu < \lambda} P^\x(\mu)\] which by Lemma 2 is \[\cong n \x P^\x(\lambda) \x S_{n-1} \x \prod_{ \mu < \lambda} P^\x(\mu)\] \[\cong S_{n} \x \prod_{ \mu \le \lambda} P^\x(\mu)\] as required. $\cqed$