5
$\begingroup$

By logarithmic differentiation, one can deduce that \[ n P_n = \sum_{j=1}^n \, \sigma(j) P_{n-j} \] where $P_n$ is the $n$-th partition number, and $\sigma(j)$ the sum of the divisors of $j$.

I see there is a nice proof with generating functions here. Is there also a combinatorial proof of this identity?

1 Answers 1

7

The left hand side counts the number of Young diagrams of size $n$ with one square marked (the shape of the diagram gives a partition, and for every shape there are $n$ choices for the square to mark). Given $j$, the number $\sigma(j)$ counts the number of ways to arrange $j$ squares in a rectangle and mark one square in the top row of the rectangle (the shape $(j/d)\times d$ corresponds to the divisor $d$ of $j$, and is counted the $d$ times, the number of columns of the rectangle).

Now extract from a marked Young diagram the rectangle formed by the row containing the marked square and all further rows of the same size; if the rectangle has size $j$, then an unmarked Young diagram with $n-j$ squares remains. Conversely given an unmarked Young diagram with $n-j$ squares and a rectangle of $j$ squares with a square marked in its top row, whose length is some divisor $d$ of $j$, insert the rectangle into the Young diagram after the rows of length${}\leq j$.

  • 0
    Wow, very cool. Thank you Marc!2012-02-11