Permutation induced by a partition

Solution 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.

Solution 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!