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]

3 comments

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.

Post a comment

RSS