Bijective Proof - partitions

Question

what is a bijective proof of #93 in the link provided http://math.mit.edu/~rstan/bij.pdf:

The number of partitions of $n$ with $k$ parts equals the number of partitions of $n + \binom{k}{2}$ with $k$ distinct parts

Answer 1

If $a_1\leq a_2 \leq a_3 ... \leq a_k$ is a partition of $n$ then $a_1 < a_2+1 < a_3+2 <... < a_k + {k-1}$ is a partition of $n+0+1+2+...+k-1 = n+\binom{k}{2}$

Answer 2

I am going to partition $5$ into three parts. How I do it below will give an indication of the bijection you can use.

There are two such partitions. Arrange the numbers in nondecreasing order:

$\color{blue}{5=3+1+1}$

$\color{brown}{5=2+2+1}$

Now, leave the last number in each partition alone, add $1$ to the number before that, add $2$ to the number preceding the one to which you added $1$, and so on until you have added $k-1$, in this case $3-1=2$, to the first element. You find that your partitions of $5$ are mapped into two distinct partitions:

$\color{blue}{5+(2+1)=(3+2)+(1+1)+1}$

$\color{brown}{5+(2+1)=(2+2)+(2+1)+1}$

Note that $2+1=\binom{3}{2}=\binom{k}{2}$

$\color{blue}{5+\binom{3}{2}=8=5+2+1}$

$\color{brown}{5+\binom{3}{2}=8=4+3+1}$

The addition process is invertible, so we have bijected the two three-way partitions of $5$ into the two distinct three-way partitions of $8$.

Can you work from there?

For another bijective proof in partition theory, see here.