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.

Theorem:

For any $ n, k \in \mathbb N$, the number of partitions of $n$ into parts, each of which appears at most $k$ times, is equal to the number of partitions of $n$ into parts the sizes of which are not divisible by $k+1$.

I knew of a proof where $k =2$. I take advantage of the proof but I failed. The proof involves generating function. (see: the book of cheng chuan-chong- "Principles and Techniques in Combinatorics" ) There could really be a better way of attacking this problem. I just don't know. need help for some hints. Thanks

share|improve this question
    
hold on. let me re-phrase –  a little don Mar 3 '12 at 5:35

2 Answers 2

up vote 5 down vote accepted

$$\prod(1+x^j+x^{2j}+\cdots+x^{kj})=\prod{1-x^{(k+1)j}\over1-x^j}=\prod_{k+1\nmid j}{1\over1-x^j}$$

share|improve this answer
1  
I don't get the solution. Can you please further explain how come? thanks.. or is there anyone who can quite expound why is the initial stuff is like that..:) –  Keneth Adrian Mar 3 '12 at 11:09
1  
The 1st product is the generating function for partitions, each part appearing at most $k$ times. Geometric series gets you to the 2nd product. Cancellation gets you to the 3rd product, which is the generating function for partitions into parts not divisible by $k+1$. Let me know if you need more - but, if you do, please let me know exactly which part you need more about. –  Gerry Myerson Mar 3 '12 at 11:57
    
Thanks a lot for the explanation..How could the second product turn to the blast product. Is it algebraic? because the numerator suddenly turns to 1 –  Keneth Adrian Mar 4 '12 at 10:19
2  
I don't know what a blast product is. Each factor in the numerator of the second product also appears, later on, in the denominator. Cancel, and nothing is left in the numerator, while all the terms of the form $1-x^{(k+1)r}$, $r=1,2,\dots$, are gone from the denominator. Write out the first few terms for, say, $k=2$, and you'll see the cancellation. –  Gerry Myerson Mar 4 '12 at 11:38
    
Sorry, It should have been "last".. Oh, I see it.. thanks. :) –  Keneth Adrian Mar 5 '12 at 2:09

There is also a bijective proof.

Given a partition of $n$ in which no part is divisible by $k+1$, suppose you have some part $a$ that is used more than $k$ times. Then merge $k+1$ occurrences of $a$ into a single occurrence of $(k+1)a$. Repeat until no part is used more than $k$ times.

Given a partition of $n$ in which no part is used more than $k$ times, if you have a part $a=(k+1)r$ that is a multiple of $k+1$, split it into $k+1$ occurrences of the part $r$. Repeat until no part is a multiple of $k+1$.

This gives you a bijection between partitions with no part divisible by $k+1$, and partitions with no part used more than $k$ times.

To illustrate, with $k=2$. Consider the partition $$39=1+1+1+1+1+1+1+2+2+2+2+2+2+4+4+4+4+4$$ This partition has no part divisible by $3$. Let's abbreviate it to $1^72^64^5$. Then we go $$1^72^64^5\to1^31^42^64^5\to1^42^634^5\to1^312^634^5\to12^63^24^5\to12^32^33^24^5\to12^33^24^56\to$$

$$\to13^24^56^2\to13^24^34^26^2\to13^24^26^2(12)$$ and we have a partition with no part used more than twice.

In the other direction, suppose we start with $51=123^24^2567^29$, no part used more than twice. We split the $9$ into three $3$s, then the $6$ into three $2$s, then each $3$ into three $1$s: $$123^24^2567^29\to123^54^2567^2\to12^43^54^257^2\to1^{16}2^44^257^2$$ a partition with no part divisible by $3$.

share|improve this answer

Your Answer

 
discard

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

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