This week’s topic comes from partition theory. Consider all the ways to write 7 as the sum of positive integers:
$$\begin{align*}
&7, && 3+2+2,\\
&6+1, && 3+2+1+1,\\
&5+2, && 3+1+1+1+1,\\
&5+1+1, && 2+2+2+1,\\
&4+3, && 2+2+1+1+1,\\
&4+2+1, && 2+1+1+1+1+1,\\
&4+1+1+1, && 1+1+1+1+1+1+1+1.\\
&3+3+1, &&
\end{align*}$$ (We don’t care about order: for example, \(5+2\) and \(2+5\) are the same.) These are called the partitions of 7, and there are 15 of them.

We can also consider imposing constraints on these partitions: For example, how many of these partitions of 7 use only odd integers? These “odd” partitions are
$$\begin{align*}
& 7, && 3+1+1+1+1, \\
& 5+1+1, && 1+1+1+1+1+1+1, \\
& 3+3+1, &&
\end{align*}$$ and there are 5 of them. Here’s a very different question: how many partition of 7 have no repeated parts? These “distinct” partition are
$$\begin{align*}
& 7, && 6+1, && 5+2, && 4+3, && 4+2+1,
\end{align*}$$ and there are 5 of these as well.

This must be coincidence, right? Let’s try a bigger example. How many partitions of 11 use only odd parts? You can (and should!) check that there are 12. And how many partitions of 11 use only distinct parts? Again, there are 12. Surprisingly, these numbers will always match!:

Theorem (Euler): For any positive integer \(n\), the number of “odd” partitions of \(n\) is the same as the number of “distinct” partitions of \(n\).

Transforming Between “Odd” and “Distinct” Partitions

Let’s try to make sense of this. Given a partition of \(n\) into odd parts, there is a simple way to transform it into a partition with distinct parts: whenever two parts are the same, add them together, and repeat until they are all distinct. For example, the partition \(7+3+3+3+3+3+3+1+1+1\) of 28 is transformed into
$$\begin{align*}
& 7+(3+3)+(3+3)+(3+3)+(1+1)+1 \\
& \quad \to 7+(6+6)+6+2+1 \\
& \quad \to 12+7+6+2+1,
\end{align*}$$ which has distinct parts. In the other direction, to transform a “distinct” partition to an “odd” one, we can reverse this process: whenever there is an even part, cut it in half and write it twice. Our example \(12+7+6+2+1\) from above becomes
$$\begin{align*}
& (6+6)+7+(3+3)+(1+1)+1 \\
&\quad \to (3+3)+(3+3)+7+3+3+1+1+1,
\end{align*}$$ which is the “odd” permutation we started with. These transformations can be shown to match “odd” permutations with “distinct” permutations in pairs, proving that these sets have the same size. (A careful argument uses binary representation.) For example, the 5 partitions of 7 above are paired as follows:
$$\begin{align*}
& 7 &&\leftrightarrow && 7 \\
& 6+1 &&\leftrightarrow && 3+3+1 \\
& 5+2 &&\leftrightarrow && 5+1+1 \\
& 4+3 &&\leftrightarrow && 3+1+1+1+1 \\
& 4+2+1 &&\leftrightarrow && 1+1+1+1+1+1+1.
\end{align*}$$ (If you know something about generating functions, then a different proof follows by proving the identity
$$\frac{1}{(1-x)(1-x^3)(1-x^5)(1-x^7)\cdots} = (1+x)(1+x^2)(1+x^3)(1+x^4)\cdots$$ and noting that the coefficients of \(x^n\) in the expansions of the left and right products equals the number of “odd” and “distinct” permutations of \(n\), respectively.)

More Coincidences

These apparent coincidences are characteristic of many results in partition theory. Try your hand at proving the following generalization:

Theorem: The number of partitions of \(n\) into parts that are not divisible by 10 equals the number of partitions of \(n\) where no part is repeated 10 or more times. The same is true for any positive integer in place of 10.

(Hint: both methods used above can be extended to prove this.) If instead we want the parts to be really distinct and make sure no two parts are equal or consecutive, then we want my favorite partition theory result:

Theorem (Rogers-Ramanujan Identity): The number of partitions of \(n\) where any two parts differ by at least 2 is the same as the number of partitions of \(n\) where every part is one more or one less than a multiple of 5.

Despite the simplicity of the statement, this is much harder to prove than the previous theorems.