The question: What permutation(s) \sigma \in S_n give the maximum values for D_n?

Definition: Let D_n: S_n \rightarrow \mathbb{Z}_{\geq 0} be a map such that D(\sigma) = \sum_{i=1}^{n}{ \sum_{j=i}^{n}{ [[i - j] - [\sigma(i) - \sigma(j)]] } }

Explanation: I want to maximize D_n (when given a particular n). If you think if i,j \in \{1,2,...,n\} as distinct elements in a sequence (of length n < \infty), and the permutation as moving them to new locations (i.e. shuffling the sequence), then D_n(\sigma) would represents a sort of metric for how "different" the new permuted sequence would be from the original (in order) sequence.

For small n I though about making a computer program to brute-force the problem; (i.e. compute D_n(\sigma) for every \sigma \in S_n). However, since |S_n| = n! and I'm really interested in larger n e.g. n = 60, that method becomes infeasible. If there are permutations \sigma \in S_n I could rule out -- e.g. for 1_{S_n} \in S_n (i.e. the identity map), D_n(1_{S_n}) = 0, a minimum, not a maximum -- maybe a computer program could analyze the remaining permutations. I also though about just randomly computing D_n(\sigma) for different permutations and going with a high-water mark algorithm on those.

Any suggestions on how to approach this problem, or where I could study/look would be appreciated.


S_n = \{\sigma: \mathbb{Z}_n \rightarrow \mathbb{Z}_n | \sigma \text{ is a bijection} \}
See Permutation - Wikipedia, the free encyclopedia

\[x\] = |x|
I used bracket notation instead because of the nested absolute values.