How do I prove that the # of partitions of n into at most k parts equals the # of partitions of n+k into exactly k parts?
I was trying to improve my ability of bijective-proofs, unfortunately I was not able to find a working bijection to transform the Ferrers Diagram. Can someone give me a hint of what to do? I'd appreciate any help regarding this. Thanks :)
On
I present a proof using PET (Polya Enumeration Theorem) for future reference. We will be using $Z(S_k)$, the cycle index of the symmetric group on $k$ elements. The partition into at most $k$ parts is given by $$[z^n] Z(S_k)\left(\frac{1}{1-z}\right)$$ where the fraction includes the empty term to account for slots being left blank, which represents at most $k$ non-empty parts.
On the other hand partitions of $n+k$ into exactly $k$ parts is $$[z^{n+k}] Z(S_k)\left(\frac{z}{1-z}\right)$$ where we have omitted the empty term.
This is $$[z^{n+k}] z^k Z(S_k)\left(\frac{1}{1-z}\right)$$ which is $$[z^{n}] Z(S_k)\left(\frac{1}{1-z}\right)$$ and we have equality as claimed.
Remark. We have a case here where the vbivariate generating function $$\prod_{q\ge 1} \frac{1}{1-ux^q}$$ would appear not to be all that useful.
Let some of the pieces in the first case contain zero. Then add 1 to all of them.