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

Question

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

Answer 1

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