Let $n\ge3$ be a positive integer and $S_{n}$ the set of all permutations of {1, 2, 3, …, n}. For every permutation $\sigma \in S_{n}$, we denote by $\epsilon (\sigma) $ the sign of $\sigma$ and by Fix$(\sigma)$ the number of fixed points of $\sigma$.
Prove that: $$\sum_{\sigma \in S_{n}} \epsilon(\sigma) \text{fix}({\sigma})=0 $$
Idea: Using derangements (by inclusion exclusion principle) and the product rule, I've managed to show that the number of permutations with exactly k fixed point is equal to: $$\frac{n!}{k!}\sum_{i=2}^{n-k} \frac{(-1)^{i}}{i!}$$
Now, the question is how many of these are even and how many are odd. Is there any explicit formula?
Or maybe I should try a different approach using cycles?
Best Answer
One way to do it is to split the sum between even and odd permutations, and then count the number of even/odd permutations which fix a given point : \begin{align} \sum_{\sigma} \epsilon(\sigma)\rm{fix}(\sigma) &= \sum_{\sigma \text{ even}}\rm{fix}(\sigma) - \sum_{\sigma\text{ odd}}\rm{fix}(\sigma) \\ &= \#\{(i,\sigma) |\sigma(i) = i\text{ and }\sigma\text{ even}\}-\#\{(i,\sigma) |\sigma(i) = i\text{ and }\sigma\text{ odd}\} \\ &= \sum_{i=1}^n\Big(\#\{\sigma |\sigma(i) = i\text{ and }\sigma\text{ even}\}-\#\{\sigma|\sigma(i) = i\text{ and }\sigma\text{ odd}\}\Big) \end{align} Ad $n\geq 3$, we have, for every $i$ : $$\#\{\sigma |\sigma(i) = i\text{ and }\sigma\text{ even}\}=\#\{\sigma|\sigma(i) = i\text{ and }\sigma\text{ odd}\}$$ and therefore, we find :
$$\sum_{\sigma} \epsilon(\sigma)\rm{fix}(\sigma) =0$$