Let $R(n,k)$ denote the number of partitions of $n$ into $k$ (non-empty) parts.

That is for example $R(7,2) = 3$ because it can be expressed as $1+6, 2+5$ and $3+4$.

Prove that:

$R(n,1) +R(n,2) + ... + R(n,k) = R(n+k,k)$


LHS counts the number of ways partitions there are of $n$ by breaking it into $1$ to $k$ parts.

RHS counts the number of partitions there are of $n+k$ into $k$ parts.

That's about all I know. So any help will be appreciated.

Edit: Hint: Ferrer's Diagram


HINT: Take any partition of $n+k$ into $k$ parts and subtract $1$ from each part. What do you get? Is the process reversible?

  • $\begingroup$ Would you have $R(n+k-1, k-1) + R(n+k-2, k-2) + ... + R(n+k-k,k-k)?$ This process can be reversed by adding $1$'s There was a hint given that I forgot to post earler Ferrer's Diagram $\endgroup$ – hockeynl Nov 19 '14 at 17:42
  • $\begingroup$ @hockeynl: Look at a single partition of $n+k$ into $k$ parts. When you reduce each part by $1$ you get a partition of what into what? My hint can actually be understood in terms of Ferrers diagrams. If you start with the Ferrers diagram of a partition of $n+k$ into $k$ parts, and you remove the lefthand column, you get the Ferrers diagram of ... what? $\endgroup$ – Brian M. Scott Nov 19 '14 at 17:49
  • $\begingroup$ Okay so I was playing around with Ferrer's diagram and it seems like that there is a partition of $n$ into $L$ nonempty parts, where $L$ is the number of parts in the original partition whose sizes are at least $2$. $\endgroup$ – hockeynl Nov 19 '14 at 18:09
  • $\begingroup$ @hockeynl: More to the point, you get a partition of $n$ into at most $k$ parts. How does that compare with your LHS? $\endgroup$ – Brian M. Scott Nov 19 '14 at 18:11
  • $\begingroup$ LHS counts partitions of $n$ that goes from $1$ up to $k$ parts $\endgroup$ – hockeynl Nov 19 '14 at 18:25

This problem merits special attention because it is an instance of a partition problem that can be solved by the Polya Enumeration Theorem as well as by Ferrer's diagrams.

Using the material from this MSE link we have for the sum on the LHS the equality

$$\sum_{q=1}^k P_q(n) = \sum_{q=1}^k [z^n] Z(S_q)\left(\frac{z}{1-z}\right) = [z^n] \sum_{q=1}^k Z(S_q)\left(\frac{z}{1-z}\right)$$ where $Z(S_q)$ is the cycle index of the symmetric group.

Recall that the OGF $G(w)$ of the cycle indices $Z(S_q)$ is given by $$G(w) = \exp\left(a_1 w + a_2 \frac{w^2}{2} + a_3 \frac{w^3}{3} + a_4 \frac{w^4}{4} + \cdots\right)$$

This gives for the sum the formula $$[z^n] [w^k] \frac{1}{1-w} \exp\left(\sum_{q\ge 1} \frac{z^q}{1-z^q} \frac{w^q}{q}\right)$$ where the factor $1/(1-w)$ implements the summation.

Re-write this as $$[z^n] [w^k] \exp\log\frac{1}{1-w} \exp\left(\sum_{q\ge 1} \frac{z^q}{1-z^q} \frac{w^q}{q}\right) \\ = [z^n] [w^k] \exp\left(\log\frac{1}{1-w} +\sum_{q\ge 1} \frac{z^q}{1-z^q} \frac{w^q}{q}\right) \\ = [z^n] [w^k] \exp\left(\sum_{q\ge 1}\frac{w^q}{q} + \sum_{q\ge 1} \frac{z^q}{1-z^q} \frac{w^q}{q}\right) \\ = [z^n] [w^k] \exp\left(\sum_{q\ge 1} \frac{1}{1-z^q} \frac{w^q}{q}\right).$$ This can be evaluated by inspection and yields $$[z^n] Z(S_k)\left(\frac{1}{1-z}\right) = [z^{n+k}] z^k Z(S_k)\left(\frac{1}{1-z}\right) = [z^{n+k}] Z(S_k)\left(\frac{z}{1-z}\right) = P_k(n+k),$$ thus completing the proof.

I do think this is remarkably pretty.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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