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

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