Sum of sign of permutation * number of fixed points over $S_{n}$

Question

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?

Answer 1

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$$

Answer 2

Here is a method that you won't find in your textbook (this claim might be false).

What is the determinant of the following $n\times n$ matrix? $$M=\begin{bmatrix}x& 1& \cdots&1& 1\\ 1&x& \cdots&1& 1\\ \vdots&\vdots&\ddots&\vdots &\vdots\\ 1&1&\cdots& x&1 \\1&1&\cdots&1&x \end{bmatrix}$$

It is $$\text{Det}(M)= ((n-1) - x) (1 - x)^{(n-1)}.$$ It is also $$\text{Det(M)}=\sum_{\sigma\in \mathfrak{S}_n} \text{sgn}(\sigma)\prod_i a_{i,\sigma(i)}=\sum_{\sigma\in \mathfrak{S}_n} \text{sgn}(\sigma) x^{\text{fix}(\sigma)}.$$

Differentiating tells us that

$$\dfrac{d((n-1) - x) (1 - x)^{(n-1)}}{dx}=\dfrac{d\text{Det}(M)}{dx}=\sum\limits_{\sigma\in \mathfrak{S}_n} \text{sgn}(\sigma)\text{fix}(\sigma) x^{\text{fix}(\sigma)-1}.$$

Put $x=1$ and voila!

---

You need $n\ge 3$ for the derivative to vanish at $x=1$.

Answer 3

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.