10
$\begingroup$

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

$\endgroup$
23
$\begingroup$

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

$\endgroup$
  • 14
    $\begingroup$ 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$). $\endgroup$ – darij grinberg Feb 21 at 18:24
  • $\begingroup$ Thank you both Gjergji and Darij. $\endgroup$ – T. Amdeberhan Feb 22 at 20:29
2
$\begingroup$

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)

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

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.