# Proof of the number of partitions.

Prove that the number of partitions of $n$ for which no part occur more than $9$ times is equal to the nujmber of partitions of $n$ with no parts divisible by $10$.

-
Keyword: Glaisher's theorem. –  darij grinberg Apr 20 '13 at 20:54
Hint: Do you know the diamond lemma (about confluence and local confluence of rewriting systems)? Start with a partition with no parts occuring more than $9$ times. As long as there is a part divisible by $10$, break it into $10$ equal parts. Iterate, until no part is divisible by $10$. Conversely, start with a partition with no parts divisible by $10$. As long as there exist $10$ equal parts, take such $10$ parts and combine them into one big part. Iterate, until there are no $10$ equal parts. The only thing you need to show is that the final result of such an iterative procedure does not ... –  darij grinberg Apr 20 '13 at 20:56
... depend on the choices you made during the procedure (i. e., which parts to break or combine first). This is where the diamond lemma comes in, but you can also avoid it by arguing digits (in the $10$-adic system, apparently an attempt of the problem poser to make things more intuitive). –  darij grinberg Apr 20 '13 at 20:58
You can replace the integer $9$ by any positive integer $k$ and $10$ by $k + 1$ and the result is easy to establish via generating functions. –  Paramanand Singh Aug 3 '13 at 4:53

The generating function for the first case is given by $$f(z) =\prod_{k\ge 1} (1 + z^k + z^{2k} + \cdots + z^{9k}) = \prod_{k\ge 1} \frac{1-z^{10k}}{1-z^k}.$$

The generating function for the second case is given by $$g(z) = \prod_{k\ge 1} \frac{1}{1-z^k} \prod_{m\ge 1} (1-z^{10m}).$$

These two are the same and we are done. The first GF lists the contribution from each value from zero to nine times. The second GF includes all partitions through the first product and then cancels those that correspond to parts that are divisible by ten.

-