4
$\begingroup$

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

  • 0
    hold on. let me re-phrase2012-03-03

2 Answers 2

5

$$\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}$$

  • 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..:)2012-03-03
  • 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.2012-03-03
  • 0
    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 12012-03-04
  • 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.2012-03-04
  • 0
    Sorry, It should have been "last".. Oh, I see it.. thanks. :)2012-03-05
2

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