I want to calculate the following sum over symmetric group:
$$\sum_{w\in S_n}(-1)^{l(w)}n^{l(w)},$$
where $l(w)$ is the number of cycles in the cycles of $w$. For example the element $w=(1)(2)(345)\in S_5$ has $l(w)=3$.
I think it has a very simple expression at least when $n$ is a prime. Any help is appreciated, thanks!
In your notation $$\sum_{w\in S_n}x^{l(w)}=\prod_{j=0}^{n-1}(x+j) =x(x+1)\cdots(x+n-1).$$ That's because the number of permutations in $S_n$ with $k$ cycles is a Stirling number of the first kind $s(n,k)$. Stirling numbers satisfy a two-variable recurrence, and this formula follows by induction from that recurrence. Substituting $x=-n$ gives your formula.