Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $Y$ be a Young tableau of shape $\lambda:=(\lambda_1,\ldots,\lambda_n)$, where $\lambda_1\geq\lambda_2\geq\ldots\geq\lambda_n$ and $N:=|\lambda|:=\sum_i\lambda_i$. I'll be using the English notation for Young tableaux. Then the hook of a box $(i,j)$ is every box straight below and straight to the right of $(i,j)$, including $(i,j)$ itself.

The Greene-Nijenhuis algorithm generates a uniformly random Young tableau of the above shape as follows:

1) Set $k=N$.

2) Uniformly pick a random unoccupied cell in $Y$.

3) Do a hook walk algorithm till you reach the edge, and place $k$ there.

4) $k\leftarrow k-1$. Repeat steps 2-4 until $k=0$.

I'm wondering if you can generate a uniformly random Young tableau by running the Greene-Nijenhuis algorithm backwards? So set $k=1$, uniformly pick an unnocupied cell, and now perform a hook walk algorithm, except now the hooks are oriented left and up: the hook of $(i,j)$ is now $(i,j)$ and every box straight above and straight to the left. Obviously 1 ends up in the top-left corner. Now do the same for $k=2$, etc. Naively, I don't think the product of the reverse hooks necessarily equals the product of the usual hooks, so perhaps some sort of modification is required?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.