[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 bijection. Starting with parts not divisible by \(k\), consider any part \(a\) with multiplicity equal or greater than \(k\). Then, merge \(k\) parts into one until there each part has multiplicity less than \(k\). 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}
$$
The inverse of this map is to split each part \(a\) that is divisible by \(k\) into \(k\) parts each equal to \(a/k\). Repeat until no part is divisible by \(k\).
$$
\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}
$$
Hence, we have a bijection and so they are equal