Proving the number of partitions of n where each part of size k appears < k times, for all k

106 Views Asked by At

How to prove that the partitions of $n$ where each part of size $k$ appears $< k$ times is given by $$\prod_{k=1}^\infty (1+p^k + p^{2k} + p^{3k} +\cdots+ p^{(k-1)k})$$

1

There are 1 best solutions below

0
On BEST ANSWER

The generating function of the number of partitions where there are fewer than $k$ parts equal to $k$ for all $k\geq 1$ should be $$f(p)=\prod_{k=1}^\infty \left(1+p^k + p^{2k} + p^{3k} +\cdots+ p^{(k-1)k}\right).$$ The property follows just from the definition of generating function: the factor $$p^{0k}+p^k + p^{2k} + p^{3k} +\cdots+ p^{(k-1)k}$$ implies that a part of size $k$ may appear $0,1,\dots, k-1$ times. See also the OEIS sequence A087153.