# Identity involving a sum over all partitions of $n$

In some work I've been doing on the cohomology of the moduli space of curves, the following identity has come up:

$$\prod_{i=1}^n \frac{x^{i-1}}{x^i-1} = \sum_{(a_1^{r_1},\ldots,a_{\ell}^{r_{\ell}}) \vdash n} \left(\prod_{j=1}^{\ell} \frac{1}{a_i^{r_i} (x^{a_i}-1)^{r_i} (r_i)!}\right).$$

Here $x$ is a formal variable and the sum on the RHS is over all partitions of $n$. By $(a_1^{r_1},\ldots,a_{\ell}^{r_{\ell}}) \vdash n$, I mean a partition of the form

$$r_1 a_1 + r_2 a_2 + \cdots + r_{\ell} a_{\ell} = n$$

with $r_1,\ldots,r_{\ell} \geq 1$ and $a_1>a_2>\cdots>a_{\ell} \geq 1$.

I have verified this identity with Mathematica for $1 \leq n \leq 20$. However, I cannot figure out how to prove that it is always true. Can anyone help me?

This reminds me a little bit of the identity in this question, and I've tried without success to use the tools discussed in the answers to that question to solve it.

EDIT: In case anyone is interested, a version of this identity now appears as Lemma 5.2 in my paper "The high dimensional cohomology of the moduli space of curves with level structures" (joint w/ Neil Fullarton), which can be downloaded from my webpage here. Thanks to Lucia for telling me how to prove it!

• Nice! Food for thought: $n! / \prod_{j=1}^\ell\left(a_i^{r_i} r_i!\right)$ is the number of permutations in $S_n$ having cycle type $\left(a_1^{r_1},\ldots,a_\ell^{r_\ell}\right)$. Thus, the right hand side is probably better regarded as an average over $S_n$. – darij grinberg Sep 27 '16 at 18:10
• This follows if you use the interpretation in terms of cycle decompositions (as in that question) together with a simple combinatorial identity for partitions (see en.wikipedia.org/wiki/Q-Pochhammer_symbol and the section on combinatorial interpretation, which is pretty much your identity). – Lucia Sep 27 '16 at 18:22
• The RHS is the coefficient of $t^n$ in $$\exp (\sum_{n \ge 1} \frac{t^n}{n} (x^n-1)^{-1})$$ – Ofir Gorodetsky Sep 27 '16 at 18:33
• @Lucia: I'm having trouble figuring out your argument. Can you give a few more details? I'm sorry for being slow -- I'm just a simple topologist, and this kind of combinatorics is far outside my comfort zone. – Andy Putman Sep 27 '16 at 18:37
• @AndyPutman: Hope the quick sketch below helps. Will look later if there are still any issues. – Lucia Sep 27 '16 at 18:47

Here's a quick sketch (since I'm pressed for time). Multiply both sides of the identity by $t^n$ and sum over $n$ from $0$ to infinity. From the cycle decomposition identity (Polya's formula) the right side becomes $$\exp \Big( \sum_{i=1}^{\infty} \frac{t^i}{i (x^i-1)} \Big)= \exp\Big( -\sum_{i=1}^{\infty} \frac{t^i}{i} \sum_{j=0}^{\infty} x^{ji} \Big) = \exp\Big( \sum_{j=0}^{\infty} \log (1-t x^j) \Big) = \prod_{j=0}^{\infty} (1-tx^j).$$ The RHS is also known as a Pochhammer symbol (see the Wikipedia article linked in my comment): it is $(t;x)_{\infty}$. The wikipedia article already describes the combinatorial identity (simple partition relation) $$(t;x)_{\infty} = \sum_{n=0}^{\infty} \frac{(-1)^n x^{n(n-1)/2} }{(x;x)_n} t^n,$$ where $$(x;x)_n = (1-x) (1-x^2) \cdots (1-x^n).$$ This matches what you get from multiplying your LHS by $t^n$ and summing.
• Also, for clarification: usually Polya's formula (cycle decomposition) is written as a sum over permutation $S_n$. From this, you get to the RHS in the above problem by converting to "cycle types" so that sum run though permutation $\lambda\vdash n$. – T. Amdeberhan Sep 28 '16 at 0:16