Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
use the fact that kC2 is trianglular number –  user58512 Feb 21 '13 at 14:22

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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.