[2.3] Exercise 6
Show that
$$
\begin{align}
p(n \mid \text{no parts divisible by \(k\)})= p(n \mid \text{less than \(k\) copies of each part})
\end{align}
$$
Note that when \(k = 2\), then we get back Euler’s Identity.
Example
Take \(k = 3\) and \(n = 6\), then the partitions of \(n\) using parts not divisible by \(3\)
$$
\begin{align}
6 &= 5 + 1 \\
6 &= 4 + 2 \\
6 &= 4 + 1 + 1 \\
6 &= 2 + 2 + 2 \\
6 &= 2 + 2 + 1 + 1 \\
6 &= 2 + 1 + 1 + 1 + 1 \\
6 &= 1 + 1 + 1 + 1 + 1 + 1
\end{align}
$$
So we have \(7\) partitions. Meanwhile, the number of partitions with fewer than \(3\) copies of each part is
$$
\begin{align}
6 &= 6 \\
6 &= 5 + 1 \\
6 &= 4 + 2 \\
6 &= 3 + 3 \\
6 &= 3 + 2 + 1 \\
6 &= 4 + 1 + 1 \\
6 &= 2 + 2 + 1 + 1 \\
\end{align}
$$
Solution
Consider the following map: starting with parts not divisible by \(k\), consider any part $a$ with multiplicity equal or greater than \(k\). Replace \(k\) copies of \(a\) by a single part of \(ka\). Repeat this until no part occurs \(k\) or more times. The final partition has fewer than \(k\) copies of each part. This process terminates since the number of parts decreases with every iteration. For example, take \(n = 6\) and \(k = 3\), then
$$
\begin{align}
6 &= 5 + 1 \rightarrow 6 = 5 + 1 \\
6 &= 4 + 2 \rightarrow 6 = 4 + 2 \\
6 &= 4 + 1 + 1 \rightarrow 6 = 4 + 1 + 1 \\
6 &= 2 + 2 + 2 \rightarrow 6 = 6 \\
6 &= 2 + 2 + 1 + 1 \rightarrow 6 = 2 + 2 + 1 + 1 \\
6 &= 2 + 1 + 1 + 1 + 1 \rightarrow 6 = 3 + 2 + 1 \\
6 &= 1 + 1 + 1 + 1 + 1 + 1 \rightarrow 6 = 3 + 3
\end{align}
$$
Conversely, given a partition of \(n\) in which each part occurs fewer than \(k\) times, if some part \(a\) is divisible by \(k\), replace \(a\) by \(k\) copies of \(a/k\). Repeat until no part is divisible by \(k\). Then for each partition above,
$$
\begin{align}
6 &= 6 \rightarrow 6 = 2 + 2 + 2 \\
6 &= 5 + 1 \rightarrow 6 = 5 + 1 \\
6 &= 4 + 2 \rightarrow 6 = 4 + 2 \\
6 &= 3 + 3 \rightarrow 6 = 1 + 1 + 1 + 1 + 1 + 1 \\
6 &= 3 + 2 + 1 \rightarrow 6 = 2 + 1 + 1 + 1 + 1 \\
6 &= 4 + 1 + 1 \rightarrow 6 = 4 + 1 + 1 \\
6 &= 2 + 2 + 1 + 1 \rightarrow 6 = 2 + 2 + 1 + 1.
\end{align}
$$
Replacing \(k\) copies of \(a\) by \(ka\) is the inverse of by replacing \(ka\) by \(k\) copies of \(a\). Hence the two maps are inverses and therefore define a bijection.
References