• Apr 6th 2013, 09:40 PM
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.