Enumerative Combinatorics: Activities and Exercises

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

In this problem, you will investigate the equivalence

1. Interpret each side of this equality. Solution.

   • LHS = Number of partitions of \(n\) into at most \(k\) parts

   • RHS = Number of partitions of \(n+k\) into exactly \(k\) parts.

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. Solution.

   The partitions of \(5\) into at most 3 parts are:

   

   The partitions of \(8\) into exactly 3 parts are:

   

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.)

   Solution.

   Let \(A\) be the set of partitions of \(n\) into at most \(k\) parts. Let \(B\) be the set of partitions of \(n+k\) into exactly \(k\) parts. We define a bijection \(f: A \rightarrow B\text{.}\) The partitions are listed in part (b) to reflect the bijection. Given the Ferrers diagram of a partition \(\sigma \in A\) we add a column of length \(k\) to the left of the diagram. The result is a partition \(f(\sigma)\) of \(n+k\) into exactly \(k\) parts. This process is reversible: we just remove this leftmost column of length \(k\) to recover the original partition of \(n\) into at most \(k\) parts. It remains to show that this function is surjective. But this is easy: Given a partition \(\tau \in B\text{,}\) removing the leftmost column gives a partition \(\sigma \in A\text{.}\) Obviously, \(f(\sigma) = \tau\text{.}\) Since \(f\) is surjective and reversible, it must be a bijection.

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

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. Solution.

   Here are the partitions of 9 into distinct parts.

   \begin{equation*} \begin{array}{l} 9 \\ 8 + 1 \\ 7 + 2 \\ 6 + 3 \\ 6 + 3 + 1 \\ 5 + 4 \\ 5 + 3 + 1 \\ 4 + 3 + 2 \end{array} \end{equation*}

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

   The recurrence relation is

   \begin{equation*} \mbox{dist}(n,k) = \sum_{i=0}^{k-1} \mbox{dist}(n-k,i). \end{equation*}

   Removing the first row of our partition results in a partition of \(n-k\) into at most \(k-1\) parts, and all parts distinct. The sum on the RHS counts the number of such partitions.

   It is worth noting that the "there are 0 ways to do the impossible" mantra is really helpful here. In particular, \(\mbox{dist}(n-k,0)=0\) when \(n-k>0\) and \(\mbox{dist}(n-k,i)=0\) when \(i > n-k\text{.}\) So we can simply take the limits of our summation to be \(0 \leq i \leq k-1\text{.}\)

   Finally, note that we do need to start at \(i=0\) to handle the case where \(k=n\text{.}\) We have \(\mbox{dist}(n,n) = \mbox{dist}(0,0) = 1\text{.}\) The last formula is an example of "there is one way to do nothing."

3. Integer Partitions into Odd Parts.

In this problem you will prove a very cool result:

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. Solution.

   \begin{equation*} \begin{array}{l} 9 \\ 7+1+1 \\ 5+3+1 \\ 5+1+1+1+1 \\ 3+3+3 \\ 3+3+1+1+1 \\ 3+1+1+1+1+1+1 \\ 1+1+1+1+1+1+1+1+1 \end{array} \end{equation*}

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. Solution.

      For the given partition of 35, we have

      \begin{equation*} \begin{array}{cccc} a_7 = 1& a_5 = 2 & a_3 = 5 & a_1 = 3. \end{array} \end{equation*}

   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. Solution.

      For the given partition of 35, we have

      \begin{equation*} \begin{array}{cccc} a_7 = 1& a_5 = 2 & a_3 = 4+1 & a_1 = 2+1. \end{array} \end{equation*}

   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. Solution.

      For the given partition of 35, we have

      \begin{equation*} \begin{array}{rcl} 35 &=& 7+5+5+3+3+3+3+3+1+1+1 \\ &=& 1 \cdot 7 + 2 \cdot 5 + (4+1) \cdot 3 + (2+1) \cdot 1 \\ &=& 7 + 10 + (12 + 3) + (2 + 1) \\ &=& 12 + 10 + 7 + 3 + 2 +1 \end{array} \end{equation*}

      and these parts are all distinct!

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

   Every positive integer \(m\) can be written uniquely as \(m = 2^i q\) where \(q\) is an odd number and \(i \geq 0\text{.}\) Every number that appears in the final expansion is of this form.

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). Solution.

   Remember that we expand the coefficients \(a_{2k+1}\) but not the odd numbers \(2k+1\text{.}\)

   \begin{equation*} \begin{array}{rcl} 9 & \longleftrightarrow & 9\\ 7+1+1 & \longleftrightarrow & 7 + 2\\ 5+3+1 & \longleftrightarrow & 5 + 3 + 1\\ 5+1+1+1+1 & \longleftrightarrow & 5 + 4\\ 3+3+3 & \longleftrightarrow & 6 + 3\\ 3+3+1+1+1 & \longleftrightarrow & 6 + 2 + 1\\ 3+1+1+1+1+1+1 & \longleftrightarrow & 4 + 3 + 2\\ 1+1+1+1+1+1+1+1+1 & \longleftrightarrow & 8 + 1 \end{array} \end{equation*}

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. Solution.

   Start with a partition \(n = b_1 + b_2 + \cdots + b_k\) into distinct parts.

   1. Factor part \(b_j = 2^{i_j} q_j\) where \(i \geq 0\) and \(q_j\) is odd.

   2. For each odd number \(q\) that appears, let \(a_q\) be the sum of all the distinct powers of two that are multiplied by \(q\text{.}\)

   3. Our new integer partition has \(a_q\) parts of size \(q\text{.}\)

   The resulting partition only has odd parts because each \(q\) is an odd number.

   Applying this to \(6 + 12 + 15 + 16 + 20\) gives

   \begin{equation*} \begin{array}{cl} &1 + 6 + 12 + 15 + 16 + 20 \\ = &1 \cdot 1 + 2 \cdot 3 + 2^2 \cdot 3 + 1 \cdot 15 + 2^4 \cdot 1 + 2^2 \cdot 5 \\ =& (1+16) \cdot 1 + (2 + 4) \cdot 3 + 4 \cdot 5 + 15 \\ =& \underbrace{1 + \cdots + 1}_{17} + \underbrace{3+\cdots+3}_{6} + \underbrace{5+\cdots+5}_{4} + 15 \end{array} \end{equation*}