Prove that number of partitions $n^2$ on $n$ distinct parts $=$ partitions of $\binom{n}{2}$ on at most $n$ parts

I tried to find bijection. We can noticed that $$ \binom{n}{2} = \frac{n^2-n}{2} $$ which is kind of hint there...
Let find bijection in use of example. Let $n=8$ and $n^2 = 64$ let $\pi$ be $$ 1+2+3+4+5+6+7+8+9+19 $$ Now rearrange them: Odd first, even later: $$ 2+4+6+8+1+3+5+7+9+19$$ now we do $$n^2 \rightarrow n^2-n$$: $$ 1+3+5+7+0+2+4+6+8+18$$ Now do $/2$: $$ 0+1+2+3+0+1+2+3+4+9$$

OK but there are two problems

  • how can I come back (due to lost $2 \times 0$ at different steps of process)$

  • In that way, my second partitions has from $n-2$ to $n$ parts. So it can't be bijection because In should get also partitions with $1$, $2$, ... $n-3$ elements...


Example for $n=3$ (rather easily generalized):

Take $9$ dots and arrange in three rows so that each row has more dots than the one below it. For instance, $$ \begin{array}{ccccc} \bullet&\bullet&\bullet&\bullet&\bullet\\ \bullet&\bullet&\bullet\\ \bullet \end{array} $$ Each partition of $9$ into $3$ distinct parts corresponds to the rows in a such array of dots, each partition corresponds to a unique array, and each array corresponds to a unique partition.

Now remove $3$ dots from the top row, $2$ dots from the middle row and one dot from the bottom row (this should be proven to always be possible, also in the general case). You get $$ \begin{array}{ccc} \bullet&\bullet\\ \bullet\\ \phantom\bullet \end{array} $$ Now read the rows as a partition of the remaining $\binom 32=3$ dots with at most three dots per row (it should be proven that the rows are still sorted from largest to smallest, so that dot arrangements still bijectively correspond to partitions).

  • $\begingroup$ That is enough clear, right, for future readers: we should notice that $0 + 1 +2+ \cdots + n-1 = \frac{n(n-1)}{2} = \binom{n}{2} $. Thanks a lot $\endgroup$ – user677339 Aug 11 '19 at 8:04
  • $\begingroup$ @Tester I should have removed one more from each row, yes. Sorry about the mistake. $\endgroup$ – Arthur Aug 11 '19 at 8:08
  • $\begingroup$ Also, the dots are unnecessary. I first read it as "parts at most $n$ large", and in that case, you read off the columns in the grid. This kind of transposing from rows to columns is difficult to describe clearly without pictures. However, since we're still reading off rows, we don't really need the pictures. $\endgroup$ – Arthur Aug 11 '19 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy