# A cancellation property for permutations?

Let $$S_n$$ be the group of $$n$$-permutations. Denote the number of inversions of $$\sigma\in S_n$$ by $$\ell(\sigma)$$.

QUESTION. Assume $$n>2$$. Does this cancellation property hold true? $$\sum_{\sigma\in S_n}(-1)^{\ell(\sigma)}\sum_{i=1}^ni(i-\sigma(i))=0.$$

Let $$n$$ be some integer greater than 2. Since the number of even and odd permutations in $$S_n$$ is the same we have $$\sum_{\sigma\in S_{n}}(-1)^{\ell(\sigma)}=0$$ therefore the contribution of $$\sum_{\sigma\in S_{n}}(-1)^{\ell(\sigma)}\left(\sum_{i=1}^n i^2\right)$$ is zero. It remains to show that $$\sum_{\sigma\in S_{n}}(-1)^{\ell(\sigma)}\sum_{i=1}^n i\sigma(i)=0.$$ Notice that if we write $$P(x)=\det\left(x^{ij}\right)_{i,j=1}^n$$ then this sum is simply $$P'(1)$$. However the order of vanishing of $$P$$ at $$1$$ is $$\binom{n}{2}$$ (notice that the matrix is pretty much a Vandermonde matrix) and this is greater than $$1$$ since $$n>2$$, therefore $$P'(1)=0$$.

• Alternatively, $\sum_{\sigma\in S_{n}}(-1)^{\ell(\sigma)}\sum_{i=1}^n i\sigma(i) = \sum_{i=1}^n i \sum_{\sigma\in S_{n}}(-1)^{\ell(\sigma)} \sigma(i)$. But it is easy to check that the inner sum is $0$ for each $i$ (because for any given $i$ and $j$, there are as many even as there are odd permutations among those $\sigma \in S_n$ that send $i$ to $j$). – darij grinberg Feb 21 at 18:24
• Thank you both Gjergji and Darij. – T. Amdeberhan Feb 22 at 20:29

Too long to fit in comments.

Remark(?).
$$\sum_{\sigma\in S_n}(-1)^{\ell(\sigma)}\sum_{i=1}^ni^{(any~real~number)}\sigma(i)=0.$$

That probably follows from Darij's comment. Here again: n>2 ( n=2 is really an exception).

The Python code below checks it. (One can use https://colab.research.google.com/ for free - you even do not need to install anything on your comp - use browser and code runs on google's servers: )

import numpy as np
import time

def inversion(permList): # http://code.activestate.com/recipes/579051-get-the-inversion-number-of-a-permutation/
"""
Description - This function returns the number of inversions in a
permutation.
Preconditions - The parameter permList is a list of unique positve numbers.

Postconditions - The number of inversions in permList has been returned.

Input - permList : list
Output - numInversions : int
"""
if len(permList)==1:
return 0
else:
numInversion=len(permList)-permList.index(max(permList))-1
permList.remove(max(permList))
return numInversion+inversion(permList)

# Get all permutations  # https://www.geeksforgeeks.org/permutation-and-combination-in-python/
#  using library function
from itertools import permutations # import lib
n = 7
lst = range(1,(n+1) ) # =  [1, 2, 3, 4, 5, 6, 7,..., n]
perm = permutations(lst) # all n! permutations are here

start_time = time.time()
_sum = 0
_new_power = 4.44
for p in list(perm):  # Loop over permutations
inv_count = inversion(list(p)) # Calculate inversion number for "p"
for i in range(1,(n+1)):
_sum += (-1)**inv_count * (i**_new_power) *p[i-1]

print(_sum)

print('n=',n, time.time() - start_time  , 'seconds passed' )


For n= 9 it runs: 6.369966745376587 seconds passed on google's colab (it should be faster than notebook, but not much)

• In fact, $\sum_{\sigma\in S_n}(-1)^{\ell(\sigma)}\sum_{i=1}^n x_i \sigma(i)=0$. – Martin Rubey Feb 23 at 16:57
• @MartinRubey Thank you ! – Alexander Chervov Feb 23 at 17:01
• The code was intended for that question: mathoverflow.net/questions/324003/… and just slightly modified – Alexander Chervov Feb 24 at 13:49
• and Martin's generalization also follows from Darij's argument (see the comment to Gjergji's answer) – Fedor Petrov Feb 26 at 21:25