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$.

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

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.