Combinatorics] Partition Numbers

Question

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

Workings:

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

Answer 1

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

Answer 2

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.