Permutation induced by a partition

Question

Let $\lambda$ be a partition of length $n$ and suppose its largest diagonal block, the Durfee square of $\lambda$, has size $r$. By this I mean that $\lambda = (\lambda_1,\ldots,\lambda_n)$ is a non-increasing sequence of numbers, which I depict by the following diagram

\begin{align*} &\square \cdots \square \square \quad (\lambda_1 \text{ squares })\\ &\square \cdots \square \quad (\lambda_2 \text{ squares }) \\ &\quad\vdots \\ &\square \quad(\lambda_n \text{ squares }) \end{align*}

and the largest $i\times i$ block one can fit to the topmost left is of size $r\times r$. The conjugate partition $\lambda'$ is given by reflecting the drawing above along the diagonal. If $\alpha_i$ and $\beta_i$ denote the sequence of numbers of blocks to the right of the diagonal in the $i$th row, and below the diagonal in the $i$th column, we write $\lambda = (\alpha_1,\ldots,\alpha_r\mid \beta_1,\ldots,\beta_r)$.

For example, for the partition $(5,4,2,1,1)$ has diagram $$ \begin{align} &\blacksquare\square\square\square\square\\ &\square\blacksquare\square\square\\ &\square\square\\ &\square\\ &\square \end{align} $$

and its conjugate is $(5,3,2,2,1)$. Its diagonal has length $2$, and in Frobenius notation we have $\lambda = (4,2\mid 4,1)$.

How can one show that the numbers $\lambda_1',\lambda_2'-1,\ldots,\lambda_r'-r+1,r+1-\lambda_{r+1},\ldots,n-\lambda_n$ form a permutation of $1,\ldots,n$? If $\lambda = (\alpha\mid \beta)$ in Frobenius notation, this is equivalent to the identity $$\sum_{i=1}^n t^i (1-t^{-\lambda_i}) = \sum_{j=1}^r (t^{\beta_j+1}-t^{-\alpha_j})$$ which is Example 4 in page 11 of MacDonald's Symmetric Functions and Hall Polynomials, which he states without proof, so presumably this is easy.

Continuing with the example, we compute that the sequence for $\lambda = (5,4,2,1,1)$ is $$5,3-1,3-2,4-1,5-1=5,2,1,3,4$$ a permutation of $1,2,3,4,5$. In $(1.7)$ MacDonald proves that if we take $m\geqslant \lambda_1$ and $n\geqslant\lambda_1'$ then the numbers $$\lambda_i+n-i,1\leqslant i\leqslant n,\quad n-1+j-\lambda_j',1\leqslant j\leqslant m$$

are a permutation of $0,\ldots,m+n-1$ by labelling the vertical and horizontal edge-lines on the diagram of $\lambda$ fitted inside the diagram of $(m^n)$, but I haven't been able to come up with a proof similar to this.

Answer 1

The concept here, although I'm not sure how far I can formalise it, is to extend the diagonal as far as the bottom of the Ferrers diagram. Then consider only the lower triangle. So your example

$$\begin{align} &\blacksquare\square\square\square\square\\ &\square\blacksquare\square\square\\ &\square\square\\ &\square\\ &\square \end{align}$$

becomes

$$\begin{align} &\blacksquare\\ &\blacksquare\blacksquare\\ &\blacksquare\blacksquare\square\\ &\blacksquare\square\square\square\\ &\blacksquare\square\square\square\square \end{align}$$

where $\blacksquare$s were in the original Ferrers diagram and $\square$s were not.

Now the elements $\lambda_1',\lambda_2'-1,\ldots,\lambda_r'-(r-1)$ correspond to vertical lines of $\blacksquare$ and the elements $r+1-\lambda_{r+1},\ldots,n-\lambda_n$ correspond to horizontal lines of $\square$. We can extract the permutation by considering the bottom-left space: if it is in the Ferrers diagram then we remove the left edge, which is a vertical line of $\blacksquare$; otherwise we remove the bottom edge, which is a horizontal line of $\square$. We then repeat on the resulting triangle, whose edge size has been reduced by one, until we have nothing left.

Answer 2

We will prove that $\lambda_j'-j+1 \neq k-\lambda_k$ (*) for every $j,k$, by induction on $n+\lambda_1$ (the sum of lengths of $\lambda, \lambda'$). As we mentioned in comments, this proves the lemma. Note that (*) rewrites as $(j-\lambda_j') +(k-\lambda_k) \neq 1$.

$n+\lambda_1 = 1$: $\lambda= \lambda'=(1)$. In this case $(1-1)+(1-1) \neq 0$.

Let's see the inductive step. Consider a partition $\lambda$. Let's say that an index is little (L) if it is $\le r$, big (B) otherwise. We have to prove four cases for the indexes $j,k$: (LL), (LB), (BL), (BB).

Let's prove (LB). Focus on the first $r$ columns. If we take out the famous top-left $r\times r$ square, we are left with a $n-r < n$ partition $\mu$ such that:

• $\lambda_{r+k}= \mu_k$ for $1 \le k \le n-r$;
• $\lambda'_j = r+\mu'_j$ for $1 \le j \le r$.

We know that $\mu$ satisfies not-equalities (*) by inductive hypotheses. Thus we have, for $r+1 \le r+k $, $1 \le j \le r$ : $$ (j-\lambda_j')+ (k+r-\lambda_{k+r}) = (j-\mu_j'-r)+ (k+r-\lambda_{k+r}) = (j-\mu_j')+ (k-\mu_k) \neq 1 $$

Now we show (BL) by duality. Apply the previous reasoning to $\lambda'$. This yields $$(j-\lambda_j') +(k-\lambda_k) \neq 1$$ for $1 \le k \le r, r+1 \le j $.

Let's prove (LL). Here $\lambda_k \ge r \ge k, \lambda'_j \ge r \ge j$, thus $ (j-\lambda_j')+(k-\lambda_k) \le 0 < 1$. Similarly, for (BB) we have $r+1 \le j,k$ and $\lambda_k, \lambda'_j \le r$. Thus $(j-\lambda_j')+(k-\lambda_k) \ge 2 > 1$.

Yuppi!