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 less than or equal to i < j less than or equal to 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 subset of Z. (C) 1999 Academic Press.