Integer Partitions by George Andrews, Kimmo Eriksson

Chapter 2

  1. [2.2] Partitioning Identity Defintion and Example: \(p(n \mid \text{even parts})\) \(= p(n \mid \text{even number of each part})\)

  2. [2.2] Exercise 3: Show that \(p(n \mid \text{even parts})\) \(= p(n/2)\) \(= p(n \mid \text{even number of each part})\)

  3. [2.3] Euler's Identity: \(p(n \mid \text{odd parts}) = p(n \mid \text{ distinct parts})\)

  4. [2.3] Exercise 4: Show that \(p(n \mid \text{even number of odd parts})\) \(= p(n \mid \text{distinct parts, number of odd parts is even})\) [TODO]

  5. [2.3] Exercise 6: Show that \(p(n \mid \text{no parts divisible by \(k\)})\) \(= p(n \mid \text{less than \(k\) copies of each part})\)

  6. [2.4] \(p(n \mid \text{parts in }\{1\}) =\) \(p(n \mid \text{distinct parts in }\{1,2,4,8,...\})\)

  7. [2.4] Theorem 1: \(p(n \mid \text{parts in }\{N\}) =\) \(p(n \mid \text{distinct parts in }\{M\})\) for \(n \geq 1\), where \(N\) is any set of integers such that no elements of \(N\) is a power of two times an element of \(N\), and \(M\) is the set containing all elements of \(N\) together with all their multiplies of powers of two.

  8. [2.4] Exercise 7: Let \(\lfloor x \rfloor\) denote the largest integer smaller than or equal to \(x\). Use Theorem 1 to prove that \(\lfloor n/3 \rfloor + 1\) is the number of partitions of \(n\) into distinct parts where each part is either a power of two or three times a power of two.

  9. [2.4] Exercise 8: For a given set \(N\), there can be at most one set \(M\) such that \(N,M\) is an Euler pair. Why? Think backward: "If there were two different such sets, \(M\) and \(M'\), then there would have to be some smallest integer \(n\) that lies in one set but not in the other" What does this mean for \(p(n \mid \text{distinct parts in} M)\) compared to \(p(n \mid \text{distinct parts in }M')?\)

  10. [2.4] Exercise 9: For a given set \(N\) where some element is a power of two times some other element say \(2^ka\) and \(a\), there can exist no set \(M\) such that \(N,M\) is an Euler pair. Why? Let \(2^ka\) be the smallest element of the above mentioned type, and show that \(M\) can be uniquely constructed so that it works successfully for all \(n > 2^ka\) but that the construction will fail for \(n = 2^k\), just as in the above example.

  11. [2.4] Exercise 10: Show that Euler pairs can be characterized more succinctly as pairs \(N,M\) such that \(2M \subset M\) and \(N = M - 2M\). [TODO]

  12. [2.4] Exercise 11: (Andrews, 1969a) Show that the number of partitions of \(n\) into \(k\)th powers \((k < 1)\) in which no part appears more than \(k - 1\) times is always equal [TODO]

Chapter 3

  1. [3.2] Ferrers Graphs and Conjugation: \(p(n \mid m \text{ parts}) =\) \(p(n \mid \text{greatest part is }m)\)

  2. [3.2] Exercise 17: For \(n=7\) and \(m=3\), explicitly show how conjugation proves Eq. (3.1) by listing all the pairings of partitions.

  3. [3.2] Exercise 18: Use conjugation to give a complete bijective proof for the identity $$p(n \mid \leq m\text{ parts}) = p(n \mid \text{all parts }\leq m)$$

  4. [3.2] Exercise 20: Partition identities usually involve conditions on sizes of parts and on the number of parts. We have seen how these notions are connected by conjugation. Another common condition is that parts be distinct. Use conjugation to show that \[ p(n \mid \text{distinct parts}) = p(n \mid \text{parts of every size from } 1 \text{ to the largest part}). \] For example, for \(n = 6\), the left-hand side counts the four partitions \(6, 5+1, 4+2, 3+2+1\) while the right-hand side counts the four partitions \(1+1+1+1+1+1\), \(2+1+1+1+1\), \(2+2+1+1\), \(3+2+1\)

  5. [3.2] Exercise 21: Let us say that a partition is a long rectangle if its Ferrers graph is rectangular with length at least as great as height. Use the above idea of merging rows with corresponding columns to show that \( p(n \mid \text{consecutive parts differ by } 2)\;=\;p(n \mid \text{long rectangle}).\)

  6. [3.2] Exercise 22: Show that \( p(n \mid \text{long rectangle}) \) equals the number of divisors of \( n \) that are less than or equal to \( \sqrt{n} \).

Other Notes

  1. Every positive integer \(n\) has a unique expression of the form \(n = 2^rm\), \(r \geq 0\), \(m\) a positive odd integer.