A sum over all permutations

Question

I want to consider the sum $$\sum_{\sigma\in\mathfrak{S}_n}\frac{x^{s(\sigma)}}{|\sigma|}$$ where $x$ is a real number, $s(\sigma)$ is the number of cycles of $\sigma$ and $|\sigma|$ is the product of lengths for cycles of $\sigma$. Will it possible to have an exact formula or a generating series for this number when $n$ ranges?

Answer 1

The exponential formula tells us that the OGF of the cycle index $Z(S_n)$ of the symmetric group is given by

$$Z(S_n) = [w^n] \exp\left(\sum_{l\ge 1} a_l \frac{w^l}{l}\right).$$

In the present case we are evaluating at $a_l = x/l$ so we obtain for $P_n(x)$ the polynomial in question

$$P_n(x) = n! [w^n] \exp\left(\sum_{l\ge 1} x \frac{w^l}{l^2}\right) = n! [w^n] \exp(x\mathrm{Li}_2(w)).$$

This is an EGF for $P_n(x).$

For computational purposes we may use the recurrence by Lovasz of the cycle index $Z(S_n)$ which yields (complexity is partition function rather than factorial)

$$Z(S_n) = \frac{1}{n} \sum_{l=1}^n a_l Z(S_{n-l}) \quad\text{where}\quad Z(S_0) = 1.$$

We get for $P_n(x)$ that

$$P_n(x) = (n-1)! \sum_{l=1}^n \frac{x}{l} \frac{P_{n-l}(x)}{(n-l)!} \quad\text{where}\quad P_0(x) = 1.$$

This yields e.g.

$$P_5(x) = {x}^{5}+5\,{x}^{4}+{\frac {125\,{x}^{3}}{12}} +{\frac {65\,{x}^{2}}{6}}+{\frac {24\,x}{5}}$$

and

$$P_6(x) = {x}^{6}+15/2\,{x}^{5}+{\frac {295\,{x}^{4}}{12}} +{\frac {355\,{x}^{3}}{8}}+{\frac {8009\,{x}^{2}}{180}}+20\,x.$$

We also have that the coefficients of $P_n(x)$ are given by

$$[x^k] P_n(x) = \frac{n!}{k!} [w^n] \left(\sum_{l=1}^n \frac{w^l}{l^2}\right)^k.$$