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

How do I prove bijectively

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

-
use the fact that kC2 is trianglular number – user58512 Feb 21 '13 at 14:22

We can establish a bijection like this.

Let us say we have a partition of $n$ into $k$ parts. Order it in non-decreasing order. Now start adding $0$ to the first part, $1$ to the second part, $2$ to the third part, $\ldots,$ $k-1$ to the $k$th part. You will get a partition of $n + \binom{k}{2}$ into $k$ distinct parts.

I hope it is clear.

-
(+1) I added a little $\LaTeX$ and formatting to make it easier to read, and changed partition to part where you’re talking about one part of the partition. – Brian M. Scott Feb 21 '13 at 13:13

HINT (complementary to Novice’s answer): Start with the Ferrers diagram of a partition of $n+\binom{n}2$ into $k$ distinct parts. Note that the bottom ($k$-th) row must have at least one dot, the next one up at least $2$, and so on. Now remove the following array of dots:

$$\begin{array}{c|l} \text{Row}&\text{Remove}\\ \hline 1&\underbrace{\bullet\bullet\bullet\ldots\bullet\bullet\bullet}_{k-1}\\ 2&\underbrace{\bullet\bullet\bullet\ldots\bullet\bullet}_{k-2}\\ 3&\underbrace{\bullet\bullet\bullet\ldots\bullet}_{k-3}\\ &\quad\vdots\\ k-3&\bullet\bullet\bullet\\ k-2&\bullet\bullet\\ k-1&\bullet\\ k&\text{(nothing)} \end{array}$$

How many dots have you removed? How many are left? Have you emptied any row?

-