Identity from integer partitions and Ferrers diagrams

Question

So the problem I'm working on is as follows:

Let $\lambda$ and $\mu$ be integer partitions, and let $\lambda^*$ and $\mu^*$ be their conjugates. By counting a set in two ways, prove $\sum_{i,j}\min\{\lambda_i,\mu_j\}=\sum_k\lambda_k^* \mu_k^*$, where $\lambda_k$ is the $k$th part of the partition $\lambda$ and $\lambda_k^*$ is the $k$th part of the conjugate $\lambda^*$.

I've got many drawings of Ferrers diagrams of some $\gamma^*$ where $\gamma^*_k=\lambda_k^*\mu_k^*$ which easily counts the right-hand side and I can see how it counts the minimum values on the left-hand side of the identity, but I can seem to justify why it works. Any thoughts?

Answer 1

Let $\lambda=\langle\lambda_1,\ldots,\lambda_r\rangle$. Let $F$ be the Ferrers diagram for $\mu$. For $k\in[r]$ let $F_k$ be what remains of $F$ when each row longer than $\lambda_k$ has been shortened to length $\lambda_k$.

• Verify that $\sum_{i,j}\min\{\lambda_i,\mu_j\}=\sum_{k=1}^r|F_k|$.

We now determine how many times each column of $F$ is counted in $\sum_{k=1}^r|F_k|$. Let $G$ be the Ferrers diagram of $\lambda$.

Let $\mu=\langle\mu_1,\ldots,\mu_s\rangle$. For $\ell\in[s]$, column $\ell$ of $F$ is present in $F_k$ precisely for those $k\in[r]$ such that $\lambda_k\ge\ell$. Clearly $\lambda_k\ge\ell$ if and only if $G$ has an element in row $k$ and column $\ell$, so column $\ell$ of $F$ is counted in $\sum_{k=1}^r|F_k|$ once for each element of column $\ell$ of $G$. Column $\ell$ of $F$ has $\mu_\ell^*$ elements, and column $\ell$ of $G$ has $\lambda_\ell^*$ elements, so column $\ell$ of $F$ contributes $\lambda_\ell^*\mu_\ell^*$ to $\sum_{k=1}^r|F_k|$, which is therefore equal to $\sum_k\lambda_k^*\mu_k^*$.

Answer 2

Suppose two finite integer non negative sequences 𝑡 and 𝑠; let min(𝑡,s) be the sequence [min(𝑡𝑖,𝑠𝑗)], reordered anyway. It is immediate that min(𝑡𝑖,𝑠𝑗)=>𝑘 is equivalent to 𝑡i=>𝑘 and 𝑠j=>𝑘; hence the conjugate dual sequence is the following: 𝑠∗.𝑡∗. The result follows since we know that the sum of a finite, integer non negative sequence and the sum of its conjugate are equal. And since min is associative it is possible to extend by induction the identity and get ∑𝑖1,i2,..,ip min{𝜆𝑖1,...,𝜆ip}=∑𝑘𝜆i1∗𝑘...𝜆ip∗𝑘

(I beg your pardon for the poor use of TeX).