# 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

## 1 Answer

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.

• Very nice. I just want to give an excellent reference for the cycle decomposition identity - Theorem 5.1.4 in page 3 (!) of "Enumerative Combinatorics, Vol. 2" by Stanley covers this identity in its most general form. Proofs and applications are given. – Ofir Gorodetsky Sep 27 '16 at 18:49
• For the direct use/relevant to your problem, look at Example 5.2.10 in the same reference, which results from an application of the aforementioned Theorem 5.1.4. – T. Amdeberhan Sep 27 '16 at 22:09
• 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
• In case you're interested, this proof now appears in my paper "The high dimensional cohomology of the moduli space of curves with level structures" (see Lemma 5.2), available on my webpage nd.edu/~andyp/papers – Andy Putman Oct 3 '16 at 1:59
• ps: I assume that you want to maintain pseudo-anonymity, but if you don't feel free to email me and I can thank you by name in the paper. This was a big help! – Andy Putman Oct 3 '16 at 2:16