Total Relative Displacement of Permutations

摘要

Let #phi# be a permutation of the set {1, 2, 3, ..., N}. We call the sum #delta#_#phi# = #SIGMA# ||i - j| - |#phi#(i) - #phi#(j)|| the total relative displacement (where the sum is over all i, j such that 1 <= i < j <= N). Chartrand, Gavlas, and VanderJagt conjectured that among permutations of {1, ..., N} the smallest positive value of #delta#_#phi# is 2N - 4. We prove this result and develop a general theory for small values of #delta#_#phi# for permutations and, more generally, for functions S -> Z with finite domain S is contained in Z.