Number of ways to divide $n$ into parts that are not divisible by $r$.

Prove that the number of ways to divide $$n$$ into summands so that no number included in the sum more than $$r − 1$$ times, equal to the number of ways to divide $$n$$ into parts that are not divisible by $$r$$.

• Here is a solution when $r=2$. There are two methods there, bijective and generating function. Both methods generalize to all $r$. – Mike Earnest May 8 at 19:10
• Thank you a lot! – Arial Pilisov May 8 at 19:11

1 Answer

The generating function for partitions where there are at most $$r-1$$ parts of each size is $$(1+x+x^2+\dots+x^{r-1})(1+x^2+x^4+\dots+x^{2(r-1)})(1+x^3+\dots+x^{3(r-1)})\cdots$$ When expanding this out, the choice of the summand $$x^{kj}$$ in the factor $$1+x^k+\dots+x^{k(r-1)}$$ corresponds to having $$j$$ parts of size $$k$$ in the partition. We can write this as $$\frac{1-x^r}{1-x}\cdot \frac{1-x^{2r}}{1-x^2}\cdot \frac{1-x^{3r}}{1-x^3}\cdot \cdots$$ Al factors in the numerator cancel with something in the denominator. What remains is the product of $$(1-x^k)^{-1}$$ over all $$k$$ which are not multiples of $$r$$. This is precisely the generating function for partitions where no parts have a size which is a multiple of $$k$$; the choice of summand in the factor $$(1-x^k)^{-1}=(1+x^k+x^{2k}+\dots)$$ determines the number of parts of size $$k$$.

• I got it. Thank you! – Arial Pilisov May 8 at 19:40