# Permutation induced by a partition

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.

• Maybe a numerical example would help you to reach a little larger audience... – Jean Marie Jan 24 '18 at 23:38
• I quote. It seems like the question is in some sense elementary but I don't know the words involved. – Andrea Marino Jan 25 '18 at 0:19
• @JeanMarie Added an example. – Pedro Tamaroff Jan 25 '18 at 0:42
• @AndreaMarino ^ – Pedro Tamaroff Jan 25 '18 at 0:43
• Thank you! I will think about it. – Andrea Marino Jan 25 '18 at 0:47

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.

• Ok. This is exactly what I was thinking about, yes. – Pedro Tamaroff Jan 26 '18 at 9:44
• (Note that in this way the resulting partition might have a permutation rather different. What "really" works is simply removing exactly one block from the last part.) – Pedro Tamaroff Feb 2 '18 at 21:43
• I don't understand what you mean. What "resulting partition"? – Peter Taylor Feb 2 '18 at 22:51
• I'm having trouble following the arguments that makes the original diagram change. Can you explain that a bit? – Naweed G. Seldon Feb 5 '18 at 22:05
• @junkquill, which part do I need to make clearer: the correspondence between vertical lines and $\lambda'_i - (i-1)$ and horizontal lines and $i-\lambda_i$; or the fact that that's why I took the lower triangle in the diagram? – Peter Taylor Feb 6 '18 at 7:24

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!

• +1: This is fine, but I really want to see if there is some clear bijection obtained by decorating the diagram of $\lambda$. – Pedro Tamaroff Jan 25 '18 at 17:02