# of partitions of $n$ into at most $r$ positive integers $=$ # of partitions of $n + r$ into exactly $r$ positive integers?

Question

How do I see that the number of partitions of the integer $n$ into at most $r$ positive integers is equal to the number of partitions of $n + r$ into exactly $r$ positive integers?

Answer 1

Take the Young diagram of a partition of $n$ into at most $r$ parts, and add an extra box to the end of each row. If there were less than $r$ rows, then add additional rows of length one so that the diagram has $r$ rows. This way, we get the Young diagram of a partition of $n + r$ with exactly $r$ rows.

To see that this is a bijection, it is enough to show that for all Young diagrams $F$ with $r$ rows and $n + r$ boxes, we can find a unique Young diagram whose image is $F$. That diagram can be obtained by simply deleting the last box of each of the $r$ rows of $F$.

Answer 2

One way is to consider the Ferrers diagrams of the partitions. It’s easiest to start with a partition of $n+r$ into $r$ parts. Its Ferrers diagram will have exactly $r$ rows. If you remove the first column of the diagram, you’ll have the Ferrers diagram of a partition of $n$. That diagram might have fewer than $r$ rows (why?), but it can’t have more, so you’ve turned the partition of $n+r$ into $r$ parts into a partition of $n$ into at most $r$ parts.

To finish the argument, just show that the operation is a bijection: that you can start with any partition $\pi$ of $n$ into at most $r$ parts and reverse the operation to get a partition of $n+r$ into exactly $r$ parts that maps into $\pi$ by the operation described in the previous paragraph.

Answer 3

Consider a Ferrer's diagram of $n$ into at most $r$ parts.

$ooooooo\\ oooooo\\ ooo\\ o$

For example this is a partition of $17$ into $4$ parts - $17=7+6+3+1$.

So in this example we know $r\ge4$. This means we can insert a first column of size exactly $r$ to get a partition of $n+r$ with exactly $r$ parts.

We also need to establish a bijection, and we can note that, say $r=4$, then $17-4=13=(7-1)+(6-1)+(3-1)+(1-1)=6+5+2$, which can be said for all the partitions here.

Algebrically, the number of partitions of $n$ into at most $r$ part is given by the coefficient of $x^n$ in:

$$\prod_{k=1}^r\dfrac{1}{1-x^k}$$

Into exactly $r$ parts can be expressed as the coefficient of $x^{n+r}$ in:

$$x^r\prod_{k=1}^r\dfrac{1}{1-x^k}$$

Answer 4

You can find a bijection between the set of partitions of $n$ into $r$ non-negative integers and of $n+r$ into $r$ positive integers.

Let $(\alpha_1, \alpha_2, \dots, \alpha_r)$ be a partition of $n$ such that $\alpha_i \geq 0, \forall i \in \{1,2,\dots,r\}.$

Then $(\alpha_1 + 1, \alpha_2 + 1, \dots, \alpha_r + 1)$ is a partition of

$$ (\alpha_1 + 1) + ( \alpha_2 + 1) + \dots + (\alpha_r + 1) = (\alpha_1 + \alpha_2 + \dots + \alpha_r) + (1+1+\dots + 1) = n + r$$

into $r$ integers, which are now strictly positive.