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

score 3 · Accepted Answer · answered Nov 19 '14 at 17:27

3

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

answered Nov 19 '14 at 17:27

Brian M. Scott

616,228

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 – hockeynl Nov 19 '14 at 17:42
@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? – Brian M. Scott Nov 19 '14 at 17:49
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$. – hockeynl Nov 19 '14 at 18:09
@hockeynl: More to the point, you get a partition of $n$ into at most $k$ parts. How does that compare with your LHS? – Brian M. Scott Nov 19 '14 at 18:11
LHS counts partitions of $n$ that goes from $1$ up to $k$ parts – hockeynl Nov 19 '14 at 18:25
@hockeynl: Exactly: the partitions of $n$ into at most $k$ parts. – Brian M. Scott Nov 19 '14 at 18:28
Let us continue this discussion in chat. – hockeynl Nov 19 '14 at 18:37
@hockeynl: Okay; I’m there. – Brian M. Scott Nov 19 '14 at 18:39
@hockeynl: You’re welcome. – Brian M. Scott Nov 19 '14 at 20:43

score 1 · Answer 2 · edited Apr 13 '17 at 12:21

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.

Combinatorics] Partition Numbers

2 Answers2