## Partitioning an integer and its double

A partition of a positive integer $$n$$ is a list of positive integers, ordered from largest to smallest, such that the sum of the integers in the sequence is $$n$$. Each integer in the list is called a part.

What is the ratio of the number of possible partitions of a positive integer $$n$$ to the number of possible partitions of $$2n$$ into $$n$$ parts?

[SOLVED]

#### Rino Raj solved this puzzle:

Let $$p$$ denote the number of possible partitions of $$n$$. Then $$p$$ is also the number of distinct ways in which $$n$$ identical balls can be placed in $$n$$ identical boxes such that some of the boxes could be empty.

To count the number of possible partitions of $$2n$$ into $$n$$ parts, consider placing $$2n$$ identical balls in $$n$$ identical boxes such that all boxes are occupied. One way to do this is to first place one ball in each box, and then distribute the remaining $$n$$ balls in the $$n$$ boxes. The number of ways we can do the latter is the number of possible partitions of $$n$$. Thus, the number of possible partitions of $$2n$$ into $$n$$ parts is also $$p$$. Therefore, the ratio sought is $$1$$.

#### Wonderwice Margera solved this puzzle:

The ratio is $$1$$. Any partition of $$2n$$ into $$n$$ parts corresponds to a unique partition of $$n$$ obtained by subtracting $$1$$ from each part and ignoring the parts that become $$0$$. Similarly, any partition of $$n$$ can have at most $$n$$ parts. Pad this to $$n$$ parts by adding as many zeroes as required. Now add $$1$$ to each part. This gives a unique partition of $$2n$$ into $$n$$ parts corresponding to this partition of $$n$$.

Therefore, we get a bijection from the set of partitions of $$2n$$ into $$n$$ parts to the set of partitions of $$n$$, which proves that the two sets have the same cardinality.

An example will make this clear. For $$n = 2$$, the partitions of $$n$$ are $$(2)$$ and $$(1, 1)$$. The partitions of $$2n$$ into $$n$$ parts are $$(3, 1)$$ and $$(2, 2)$$. $$(2)$$ corresponds to $$(2 + 1, 0 + 1) = (3, 1)$$. $$(1, 1)$$ corresponds to $$(1 + 1, 1 + 1) = (2, 2)$$.

#### Ilan Mayer solved this puzzle:

Each partition of $$2n$$ into $$n$$ parts contains numbers in the range $$1$$ to $$n + 1$$.

Subtracting $$1$$ from each number and discarding the $$0$$s thus results in a partition of $$n$$.

Conversely, any partition of $$n$$ contains $$1$$ to $$n$$ numbers. Adding $$0$$s to partitions with less than $$n$$ numbers to bring up the total to $$n$$ and then adding $$1$$ to each number results in a partition of $$2n$$ into $$n$$ parts.

Thus the ratio is $$1$$.

### Credit

This is an original puzzle from cotpi.