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.


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

| cite | improve this answer | |
  • 1
    $\begingroup$ I believe it must be so, I was given this problem by my math olympics tutor. Thank you kindly! $\endgroup$ – Ignacio Rojas Jun 27 '18 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.