About a sum that looks like a determinant

129 Views Asked by At

I want to prove the following equality.

$$\sum_{\sigma\in S_n}\frac{\text{sgn}(\sigma)}{|\text{Fix}(\sigma)|+1}=(-1)^{n+1}\frac{n}{n+1},$$ where $\sigma$ is a permutation on $n$ elements and $\text{sgn}, \text{Fix}$ stand for the sign of the permutation and the fixed points of the permutation.

The sum reminds me of a determinant since, but I can't see how would $$\prod_{i=1}^na_{i,\sigma(i)}=\frac{1}{|\text{Fix}(\sigma)|+1}.$$

I tried also looking at the element on the right hand side. The $\frac{1}{n+1}$ reminds me of two things, one could be an alternating geometric series and the other one is the integral of $x^n$.

My instinct tells me that matrix whose determinant is this must not be very complicated, I feel there must be some symmetries as well.

If you can provide any insight or hints it would be very much appreciated.

1

There are 1 best solutions below

1
On BEST ANSWER

You definitely are on the right track. The LHS can be written as

$$ \int_{0}^{1} \sum_{\sigma\in S_n}\text{sgn}(\sigma) x^{|\text{Fix}(\sigma)|}\,dx=\int_{0}^{1}\det\left(\mathbf{1}+(x-1)\mathbf{I}\right)\,dx $$ where $\mathbf{1}$ stands for the rank-1 matrix whose entries are 1s only and $\mathbf{I}$ is the identity matrix.
The involved determinant equals $(n+x-1)(x-1)^{n-1}$ and $$ \int_{0}^{1}(n+x-1)(x-1)^{n-1}\,dx = (-1)^{n+1}\frac{n}{n+1}$$ is pretty straightforward. Nice problem! Is that a Putnam exercise, by chance?


The same technique allows to prove that $$ \sum_{\sigma\in S_n}\frac{\text{sgn}(\sigma)}{(|\text{Fix}(\sigma)|+1)^{\color{red}2}}=(-1)^{n+1}\left[\frac{nH_n}{n+1}-\frac{1}{(n+1)^2}\right]$$ too, by considering $\int_{0}^{1}-\log(x)\det\left(\mathbf{1}+(x-1)\mathbf{I}\right)\,dx.$