Combinatorial Interpretation of a partition identity

Question

I am working on the book "Number Theory in the Spirit of Ramanujan" by Bruce Berndt.

• In Exercise $1.3.7$: He wants us to prove that $$ np\left(n\right) = \sum_{j = 0}^{n - 1}p\left(j\right)\sigma\left(n - j\right) $$ where $p(n)$ is the number of partitions of $n$ and $\sigma(n)$ is the sum of divisors of $n$.
• I did solve the exercise by following his hints. However, I could not find any combinatoric explanation of the identity. Is there any combinatorial explanation for this identity?

Thanks in advance.

The solution provided in the book:

STEP1: Let's start with the identity $F(q) := \sum_{n=0}^{\infty}p(n)q^n=\frac{1}{(q;q)_\infty}$ where $p(n)$ is the number of partitions of $n$ and $(q;q)_\infty := (1-q)(1-q^2)(1-q^3).. $.

STEP2: Take logarithm of both sides and differentiate to get:

$$\frac{\sum_{n=0}^{\infty}np(n)q^{n-1}}{\sum_{n=0}^{\infty}p(n)q^n} = \frac{1}{1-q} + \frac{2q}{1-q^2} + \frac{3q^2}{1-q^3} + ... = \sum_{n=1}^{\infty}\frac{nq^{n-1}}{1-q^n} $$

STEP3: Expand the geometric series in the right hand side to get:

$$\sum_{n=1}^{\infty}nq^{n-1}\sum_{m=0}^{\infty} q^{nm} = \sum_{n=1}^{\infty}\sigma(n)q^{n-1}$$ where $\sigma(n) = \sum_{d|n} d$.

STEP4: Now, cross-multiplying each sides and equating the coefficients of $q^n$s in both sides gives the desired result.

Answer 1

There is a beautiful proof in page 61 of Integers Partitions by George E. Andrews and Kimmo Eriksson. I write it down here as an answer for convenience.

First we write down all partitions of $n$ and then add them all up. Since there are $p(n)$ of them, the total of this sum must be $np(n)$. On the other hand, let us keep track of how many times the summand $h$ appears in all of these partitions. Clearly it appears at least once in $p(n-h)$ partitions. It appears at least twice in $p(n-2h)$ partitions. It appears at least three times in $p(n-3h)$ partitions. Hence, the total numbers of appearances of $h$ is

$$p(n-h)+p(n-2h)+p(n-3h)+\cdots$$

Therefore,

$$\begin{aligned}np(n)&=\sum_{h=1}^nh(p(n-h)+p(n-2h)+p(n-3h)+\cdots)\\ &=\sum_{hk\leq n}hp(n-hk)=\sum_{j=1}^np(n-j)\sum_{h|j}h\\ &=\sum_{j=1}^np(n-j)\sigma(j)=\sum_{j=0}^{n-1}p(j)\sigma(n-j).\end{aligned}$$

Answer 2

Hopefully the diagram above is a "Proof without Words" ?

A partition can be represented by a Young Diagram & If we choose a given square then we have a rooted Young diagram (RYD) (These are enumerated by $n p_n$ (where $p_n$ are the number of partitions of $n$)).

Given a RYD the root will occur in a part of size $d$. Now remove all of the parts of size $d$ that are to the left & including the part containing the root (This will be a rectangle), Also note the partition that remains. Thus a RYD can be mapped to a pair consisting of a rectangle & a Young diagram.

Now these pairs are counted by $p_j$ Young diagrams and the rectangles are enumerated by the sum of $d$ that divide $n-j$ ( In other words $ \sigma(n-j) $).

So \begin{eqnarray*} n p_n = \sum _{j=0}^{n-1} p_j \sigma(n-j). \end{eqnarray*}