Distinct parts and odd parts
Tonight's idea
A partition of a number writes it as a sum of positive whole numbers. Order is ignored, so \(4 + 1\) and \(1 + 4\) are the same partition.
Pick out two kinds. In a partition into distinct parts, no part is used twice. In a partition into odd parts, every part is odd, and repeats are allowed.
For every positive whole number \(n\), the number of partitions of \(n\) into distinct parts equals the number of partitions of \(n\) into odd parts.
Euler proved this with a product of brackets: \((1 + q)(1 + q^2)(1 + q^3)\cdots\). Multiply out. Each term comes from picking the power of \(q\) in some brackets and the 1 in the rest. The picked powers are all different, and their exponents add. So the number in front of \(q^n\) counts the partitions of \(n\) into distinct parts. Euler wrote a second product that counts odd parts, and showed the two products are equal. Sums and products in a letter \(q\) like these are called \(q\)-series.
Watch one: the number 5
All of them. List the partitions of 5 with the biggest part first, so none is missed. The number on its own counts too: \(5\),\(4+1\), \(3+2\), \(3+1+1\), \(2+2+1\), \(2+1+1+1\), \(1+1+1+1+1\). That is 7.
Distinct parts. \(5\), \(4+1\), \(3+2\). That is 3. Odd parts. \(5\), \(3+1+1\), \(1+1+1+1+1\). That is 3 as well. Only \(5\) is on both lists, so the two lists are different but equally long.
The brackets. To reach \(q^5\) you need the brackets up to \((1 + q^5)\). There are three ways to make \(q^5\): pick \(q^5\) alone, or \(q^4\) and \(q\), or \(q^3\) and \(q^2\). They match \(5\), \(4+1\) and \(3+2\). The full product begins
\[(1+q)(1+q^2)(1+q^3)(1+q^4)(1+q^5) = 1 + q + q^2 + 2q^3 + 2q^4 + 3q^5 + 3q^6 + \cdots\]The trap. The numbers are right only as far as \(q^5\). The product says 3 for \(q^6\), but 6 has 4 partitions into distinct parts. The missing one is \(6\) itself, which needs the bracket \((1 + q^6)\).
Your turn
- List all the partitions of 6, biggest part first. There are 11.
- From your list for 6, (a) pick out the partitions into distinct parts, (b) pick out the partitions into odd parts, and (c) say which partitions are on both lists. Do the two counts agree?
- (a) Multiply out \((1 + q)(1 + q^2)(1 + q^3)\). (b) The number in front of \(q^3\) should be 2. Which two partitions of 3 does it count? (c) The number in front of \(q^4\) is 1, but 4 has two partitions into distinct parts. Which one did the product find, which one is missing, and which bracket would supply it?
- (a) Check the callout for \(n = 7\): list the partitions of 7 into distinct parts, then the partitions of 7 into odd parts. (b) Check it for \(n = 1\), 2, 3 and 4 as well.
Stretch: merge the twins
Take a partition into odd parts. Whenever two parts are equal, merge them into one part twice as big. Keep going until no two parts are equal. For example \(1+1+1+1+1\) becomes \(2+2+1\) and then \(4+1\). (a) Do this to each of the four partitions of 6 into odd parts. What do you notice about the four results? (b) Go backwards: split every even part into two halves until all the parts are odd. Start from \(4+2+1\) and from \(6+1\). (c) Why must the merging stop? Why can two different starting partitions never merge to the same result?
Answers
- \(6\), \(5+1\), \(4+2\), \(4+1+1\), \(3+3\), \(3+2+1\), \(3+1+1+1\), \(2+2+2\), \(2+2+1+1\), \(2+1+1+1+1\), \(1+1+1+1+1+1\). That is 11.
- (a) Distinct parts: \(6\), \(5+1\), \(4+2\), \(3+2+1\). (b) Odd parts: \(5+1\), \(3+3\), \(3+1+1+1\), \(1+1+1+1+1+1\). (c) Only \(5+1\) is on both lists. The counts agree, 4 and 4, even though the lists are mostly different.
- (a) \((1+q)(1+q^2) = 1 + q + q^2 + q^3\). Multiplying by \((1 + q^3)\) gives \(1 + q + q^2 + 2q^3 + q^4 + q^5 + q^6\). (b) One \(q^3\) comes from the third bracket alone, which is the partition \(3\). The other comes from \(q^2 \times q\), which is \(2+1\). (c) The product found \(q^3 \times q\), which is \(3+1\). The partition \(4\) is missing, and the bracket \((1 + q^4)\) would supply it. Three brackets give correct counts only up to \(q^3\).
- (a) Distinct parts: \(7\), \(6+1\), \(5+2\), \(4+3\), \(4+2+1\). Odd parts: \(7\), \(5+1+1\), \(3+3+1\), \(3+1+1+1+1\), \(1+1+1+1+1+1+1\). That is 5 each. (b) For 1: \(1\) and \(1\), one each. For 2: \(2\) is distinct and \(1+1\) is odd, one each. For 3: \(3\) and \(2+1\) are distinct, \(3\) and \(1+1+1\) are odd, two each. For 4: \(4\) and \(3+1\) are distinct, \(3+1\) and \(1+1+1+1\) are odd, two each.
Stretch. (a) \(5+1\) stays \(5+1\). \(3+3\) becomes \(6\). \(3+1+1+1\) becomes \(3+2+1\). \(1+1+1+1+1+1\) becomes \(2+2+2\), then \(4+2\). The results are the four partitions of 6 into distinct parts, each exactly once. (b) \(4+2+1\) becomes \(2+2+2+1\), then \(1+1+1+1+1+1+1\). And \(6+1\) becomes \(3+3+1\). (c) Each merge leaves one part fewer, so the merging cannot go on for ever, and when it stops no two parts are equal. Halving undoes merging: a part made by merges is some odd part doubled a number of times, and halving it all the way gives those equal odd parts back. So the result tells you the start, and two different starts cannot share a result. To finish Euler's theorem you also need every partition into distinct parts to turn up. That uses one more fact: every whole number is a sum of different powers of 2 in exactly one way.