14
$\begingroup$

A few years ago I first read about the marvelous Euler identity:

$\sum_{n\in\mathbb{N}}p(n)z^n=\prod_{k\geq1}\frac{1}{1-z^k}$,

where $p(n)$ is the number of partitions of $n$ ($p(0)=1$ by convention) and some of its beautiful consequences (like the pentagonal number theorem). Taking log of both sides of Euler identity and differentiating, the following nice recursive formula magically appears:

$np(n)=\sum_{k=0}^{n-1}p(k)\sigma(n-k)$,

where $\sigma(n)$ denotes the sum of the divisors of $n$. After some googling I found this identity quoted in a few places, but always without any reference. Since I am quite ignorant about the theory of partitions and related matters, I would like very much to know:

1) Who discovered this identity? Does it have a name?

and the much more interesting:

2) Is there a proof without generating functions?

Thank you!

$\endgroup$
1
  • $\begingroup$ This identity appears on page 79 of the 1918 Hardy–Ramanujan paper applying the circle method to $p(n)$, Asymptotic formulae in combinatory analysis, Proc. Lond. Math. Soc. 17 (1918) 75–115. (Or page 345 of this reprint: ramanujan.sirinudi.org/Volumes/published/ram36.pdf.) The authors claim no originality. $\endgroup$ Feb 6, 2019 at 12:14

4 Answers 4

16
$\begingroup$

2.) There is a proof, due to P. Erdös, in the Annals of Mathematics (2), 43, 1942, pp. 437-450, which does not use the generating function, but rather proves the identity $$ np(n)=\sum_{m=1}^n \sum_{k=1}^{n/m}mp(n-km) $$ by elementary regrouping etc. From this identity, it follows with $km=r$, $$ np(n)=\sum_{r=1}^np(n-r)\sum_{m\mid r}m=\sum_{r=1}^np(n-r)\sigma(r). $$

$\endgroup$
1
  • 2
    $\begingroup$ I thought there world be direct proof of the identity, but I ended up counting two different thing, so deleted my answer. This survey math.ucla.edu/~pak/papers/psurvey.pdf by Igor Pak also contains the proof of the first identity, and tons of bijective proof of other identities. $\endgroup$ Apr 9, 2013 at 21:14
14
$\begingroup$

The proof by Erdös cited in D. Burde's answer can be made explicitly bijective. Interpret $np(n)$ as the number of ways to choose a partition $\lambda$ of $n$ and a box $B$ in the Young diagram of $\lambda$. Suppose that $B$ is in a row of length $m$ and that there are exactly $k$ rows of length $m$ below $B$, including the row containing $B$. Let $\mu$ be the partition of $n-km$ whose Young diagram is obtained from the Young diagram of $\lambda$ by removing these rows. Let $c \in \lbrace 1,\ldots , m\rbrace$ be the column containing $B$. Then $\lambda$ and $B$ are determined by $\mu$ and $c$, and so the map sending $(\lambda, B)$ to $(\mu, c)$ is a bijection. Hence

$$ np(n) = \sum_{m=1}^n \sum_k p(n-km)m = \sum_{r=1}^n p(n-r)\sigma(r) $$

where the final step is as in D. Burde's answer.

Erdös' paper includes a beautiful application of this identity, in which he uses induction on $n$ to show that $p(n) \le \exp c \sqrt{n}$ where $c = 2 \sqrt{\pi^2 /6}$.

$\endgroup$
1
  • $\begingroup$ Yes, this is much nicer than saying "by regrouping etc.". I also find the paper of Erdös ireally beautiful. Erdös says that this identity was already known to Hardy and Ramanujan, who had given the asymtptotic formula for $p(n)$ before. So perhaps we could call it the Hardy-Ramanujan-Erdös identity. $\endgroup$ Apr 10, 2013 at 8:15
5
$\begingroup$

Part 1.) R. Stanley mentions on page 59 (in the answer to exercise 24a, which is the identity mentioned in the OP) in Enumerative Combinatorics vol. 1 (exercise is 78a in later edition) the following somewhat inconclusive fact:

Some related results are due to Euler and recounted in $\S$303 of P.A. MacMahon, Combinatory Analysis, vol. 2, Cambridge University Press, 1916...

Searching the Euler archive showed a few similar results (but those were on the generating function of $\sigma(n)$ being related to the logarithmic derivative of the Euler generating function.

$\endgroup$
2
$\begingroup$

This idenity can be proved using symmetric functions, this is an exercise in the first chapter of Macdonald's book Symmetric Functions and Hall Polynomials.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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