# 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 at 14:22

## 2 Answers

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 22, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.92218416929245, "perplexity_flag": "head"}