Skip to main content

Chapter 8 Integer Partitions

A partition of integer \(n\) is a multiset of positive integers whose sum is \(n\text{.}\) Here are three symbols we use for counting integer partitions:

\begin{equation*} \begin{array}{rcl} p(n,k) & = & \mbox{# partitions of } n \mbox{ into } k \mbox{ parts} \\ \\ p_k(n) & = & \mbox{# partitions of } n \mbox{ into at most } k \mbox{ parts} \\ &=& \displaystyle{\sum_{i=1}^k p(n,i)}\\ \\ p(n) & = & \mbox{# partitions of } n \mbox{ into any number of parts} \\ &=& \displaystyle{\sum_{i=1}^n p(n,i)} \end{array} \end{equation*}

Exercises Practice Problems

1. Integer Partitions With At Most \(k\) Parts.

In this problem, you will investigate the equivalence

\begin{equation*} p_k(n) = p(n+k,k) \end{equation*}

  1. Interpret each side of this equality.

  2. Verify this result for \(n=5\) and \(k=3\text{.}\) In other words, find all partitions of both types. You will find that there are equal numbers of these partitions.

  3. Try to devise a bijection from one set to the other. Hint: start with a partition from the LHS. You must add \(k\) more boxes to get a partition from the RHS. How can you do this in an invertible way? (We will develop a rigorous proof of your bijection as a class.)

2. Integer Partitions Into Distinct Parts.

Let \(\mbox{dist}(n,k)\) be the number of integer partitions of \(n\) with first part \(k\) and all parts distinct. The initial conditions for this function are

\begin{equation*} \begin{array}{cccccc} \mbox{dist}(0,0)=1, & \mbox{dist}(n,0)=0 \mbox{ for } n > 0, & \mbox{dist}(1,1)=1. \end{array} \end{equation*}

It is also clear that \(\mbox{dist}(n,k)=0\) when \(k>n\text{.}\)

  1. Here are the values of \(\mbox{dist}(9,k)\) for \(1 \leq k \leq 9\text{:}\)

    \begin{equation*} \begin{array}{c|cccccccccccc} k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \mbox{dist}(9,k) & 0 & 0 & 0 & 0& 1 & 2 & 2 & 1 & 1 & 1 \end{array} \end{equation*}

    Find each of these eight integer partitions of 9 into distinct parts.

  2. Find a recurrence relation for \(\mbox{dist}(n,k)\text{.}\) Justify your formula.

3. Integer Partitions into Odd Parts.

In this problem you will prove a very cool result:

\begin{equation*} \begin{array}{ccc} \begin{array}{c} \mbox{# integer partitions of } \\ \mbox{into distinct parts} \end{array} &=& \begin{array}{c} \mbox{# integer partitions of } \\ \mbox{into odd parts} \end{array} \end{array} \end{equation*}

  1. In the previous problem, you found the eight integer partitions of 9 into distinct parts. Now find the eight integer partitions of 9 into odd parts.

  2. Given an integer partition of \(n\) into odd parts, here is the mapping that creates an integer partition with distinct parts. For each step, perform the described operation for the integer partition given by

    \begin{equation*} 35 = 7+5+5+3+3+3+3+3+1+1+1. \end{equation*}

    1. For each odd number \(2k+1\text{,}\) let \(a_{2k+1}\) be the number of times that \(2k+1\) appears in the partition. In other words, the type of the partition of \(n\) is \((a_1, 0, a_3, 0, a_5 , 0, \ldots )\) and we have

      \begin{equation*} n = a_1 \cdot 1 + a_3 \cdot 3 + a_5 \cdot 5 + \cdots. \end{equation*}

      Perform this step for our integer partition of 35.

    2. Write each \(a_{2k+1}\) as the sum of distinct powers of two. For example, \(5 = (4 + 1)\) and \(42 = (32 + 8 + 2)\text{.}\) There is a unique way to do this, and it is equivalent to writing \(a_{2k+1}\) using binary notation.

      Perform this step for our integer partition of 35.

    3. Now multiply each odd number \(2k+1\) by this "sum of distinct powers of 2 expansion of \(a_{2k+1}\)" from the previous step. For example, if we started with \(a_{7}=11\) then we would get

      \begin{equation*} a_7 \cdot 7 = 11 \cdot 7 = (8 + 2 + 1) \cdot 7 = 56 + 14 +7. \end{equation*}

      We have now represented \(n\) as the sum of distinct positive integers!

      Perform this step for our integer partition of 35.

  3. Explain why each of the terms obtained by the process in part (b) are all distinct.

  4. Use the mapping from part (b) to match the partitions of 9 into odd parts from part (b) to their corresponding partition of 9 into distinct parts from 2(a).

  5. Describe the reverse mapping that takes a partition of \(n\) with distinct parts and maps it to a partition of \(n\) with odd parts. Explain how you know the resulting partition must have odd parts. Then use your mapping the integer partition

    \begin{equation*} 6 + 12 + 15 + 16 + 20. \end{equation*}

    to an integer partition with odd parts.