Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.