Same number of partitions of a certain type?

Solution 1:

I don’t know of a nice intuitive argument; the usual proof is by generating functions. The generating function for the number of partitions with no part divisible by $d$ is $$g(x)=\prod_{k\ge 1,\,d\nmid k}\frac1{1-x^k}\;,\tag{1}$$ and the generating function for the number of partitions with no part repeated $d$ or more times is $$h(x)=\prod_{k\ge 1}(1+x^k+x^{2k}+\cdots+x^{(d-1)k})=\prod_{k\ge 1}\frac{1-x^{dk}}{1-x^k}\;.\tag{2}$$

Then $$g(x)\prod_{k\ge 1}(1-x^k)=\prod_{k\ge 1,\,d\mid k}(1-x^k)=\prod_{k\ge 1}(1-x^{dk})=h(x)\prod_{k\ge 1}(1-x^k)\;,$$ so $h(x)=g(x)$.

To see why $(1)$ and $(2)$ are the desired generating functions, note that $$\frac1{1-x^k}=1+x^k+x^{2k}+x^{3k}+\cdots\;.$$ Thus, in the product in $(1)$ there is one $x^n$ term for every way of writing $n$ as a sum of numbers not divisible by $d$, and the coefficient of $x^n$ must therefore be the number of ways of writing $n$ as a sum of numbers not divisible by $d$. In the product in $(2)$ there is one $x^n$ term for every way of writing $n$ as a sum $n_1k_1+n_2k_2+\cdots+n_mk_m$ in which the $k_i$ are distinct and the coefficients $n_i$ are all less than $d$. Such a decomposition of $n$ corresponds to a partition with $n_i$ parts of size $k_i$ for $i=1,\dots,m$, so the coefficient of $x^n$ in $h(x)$ must be the number of partitions of $n$ in which every part appears at most $d-1$ times.

Solution 2:

A bijective argument:

On the side without too many repetitions, you break up parts divisible by $d^k$ into $d^k$ parts (where $d^k$ is the highest power of $d$ dividing the size of the part). This gets you a partition without parts divisible by $d$.

To go back, you write the multiplicities in base $d$ and if you have $\sum_i a_i d^i$ parts of size $s$, then you glue them, to get $a_i$ parts of size $sd^i$.