• Apr 6th 2013, 09:40 PM
The question: What permutation(s) $\displaystyle \sigma \in S_n$ give the maximum values for $\displaystyle D_n$?

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

Explanation: I want to maximize $\displaystyle D_n$ (when given a particular $\displaystyle n$). If you think if $\displaystyle i,j \in \{1,2,...,n\}$ as distinct elements in a sequence (of length $\displaystyle n < \infty$), and the permutation as moving them to new locations (i.e. shuffling the sequence), then $\displaystyle 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 $\displaystyle n$ I though about making a computer program to brute-force the problem; (i.e. compute $\displaystyle D_n(\sigma)$ for every $\displaystyle \sigma \in S_n$). However, since $\displaystyle |S_n| = n!$ and I'm really interested in larger $\displaystyle n$ e.g. $\displaystyle n = 60$, that method becomes infeasible. If there are permutations $\displaystyle \sigma \in S_n$ I could rule out -- e.g. for $\displaystyle 1_{S_n} \in S_n$ (i.e. the identity map), $\displaystyle 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 $\displaystyle 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.

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

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