Prove that this sum equals 0

Question

We have $n\geq3$ and $S_{n}$ the set of permutations of length n. For every $\sigma\in S_{n}$, we have $\epsilon(\sigma)$ the sign of permutation $\sigma$ and $Fix(\sigma)$ the set of fixed points of $\sigma$. Prove that $$\sum_{\sigma\in{S_{n}}} \epsilon(\sigma)\mid{Fix(\sigma)}\mid=0$$.

Answer 1

With the notation from Wikpedia on random permutations we find that the sign $\sigma(\pi)$ of a permutation $\pi$ is given by

$$\sigma(\pi) = \prod_{c\in\pi} (-1)^{|c|-1}$$

where the product is over all cycles $c$ of $\pi.$

Using combinatorial classes as in Analytic Combinatorics by Flajolet and Sedgewick, we have the following class $\mathcal{P}$ of permutations with fixed points marked:

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{P} = \textsc{SET}( -\mathcal{Z} + \mathcal{V} \mathcal{Z} + \textsc{CYC}_{=1}(\mathcal{Z}) + \mathcal{U} \times \textsc{CYC}_{=2}(\mathcal{Z}) + \mathcal{U}^2 \times \textsc{CYC}_{=3}(\mathcal{Z}) \\ + \mathcal{U}^3 \times \textsc{CYC}_{=4}(\mathcal{Z}) + \cdots).$$

Translating to generating functions we obtain

$$G(z,u,v) = \exp\left(-z+vz+\sum_{k\ge 1} u^{k-1} \frac{z^k}{k}\right) \\ = \exp\left(-z+vz+\frac{1}{u} \log\frac{1}{1-uz}\right) \\ = \exp(-z+vz) \left(\frac{1}{1-uz}\right)^{1/u}.$$

We thus have

$$n! [z^n] G(z, -1, v) = n! [z^n] \exp(-z+vz) (1+z) = \sum_{\pi\in S_n} \sigma(\pi) v^{\nu(\pi)}$$

where $\nu(\pi)$ is the number of fixed points. It follows that the desired statistic is given by

$$n! [z^n] \left.\frac{\partial}{\partial v} \exp(-z+vz) (1+z)\right|_{v=1} \\ = n! [z^n] \left.\exp(-z+vz) z (1+z)\right|_{v=1} = n! [z^n] (z+z^2).$$

This is one when $n=1$ and two when $n=2$ and zero otherwise.

Answer 2

Reverse the order of summation: the sum can be written as $$\sum_{\sigma \in S_n} \sum_{i\in [n], \sigma(i) = i} \varepsilon(\sigma) = \sum_{\sigma \in S_n, i \in [n], \sigma(i) = i} \varepsilon(\sigma) = \sum_{i\in [n]} \sum_{\sigma\in S_n, \sigma(i) = i} \varepsilon(\sigma)$$

The latter inner sum is 0, since the permutations in $S_n$ that fix a given $i$ can be sign-preservingly matched with the permutations in $S_{n-1}$.

Answer 3

Your sum is the sum of the values of the character of the representation of $S_n$ obtained as a tensor product of the tautological permutation representation $V$ and the sign representation $\mathrm{sgn}$. Since $V\otimes\mathrm{sgn}$ does not have trivial summands, that sum is zero.