Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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.

share|cite|improve this answer
(+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?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.