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.

## No comments :

## Post a Comment