What is $\underset{\pi \in S_n}{\max}\underset{1\leq i\leq n}{\sum}|i-\pi(i)|$, where $S_n$ is the set of permutations of $(1,2,\ldots,n)$?

Question

What is the value of $$\underset{\pi \in S_n}{\max} \biggl( \underset{1\leq i\leq n}{\sum} \big|i-\pi(i)\big|\biggr)\,,$$ where $S_n$ is the set of permutations of $(1,2,\ldots,n)$?

I can see that if $n$ is even,then we can achieve the sum to be $\frac{n^2}{2}$ by considering the following permutation:

Switch the following pairs $(1,\frac{n}{2}+1),(2,\frac{n}{2}+2),.......,(\frac{n}{2},n)$.

Can we go above $\frac{n^2}{2}$?

I am trying to decompose $\pi\in S_n$ as composition of transpositions or cycles and to observe how a particular transposition affects the sum.

Any help would be appreciated.Thanks in advance.

Answer 1

Start with your setup for even $n$ of two lists $$1: (1,n/2+1),(2,n/2+2),...,(n/2,n) \\ 2: (n/2+1,1),(n/2+2,2),...,(n,n/2)$$ for which the corresponding sum equals $n^2/2$. Any permutation within either list will lead to the same value $n^2/2$. For example in list 1 interchange $n/2+i$ and $n/2+j$ for some distinct $i,j=1,2,...,n/2$ which doesn't change $|n/2+i-j|+|n/2+j-i|=n$ while the other terms don't change. Permuting $n/2+i$ with $i=1,...,n/2$ from list 1 with $j=1,...,n/2$ from list 2 gives $|i-j|+|n/2+j-n/2-i|=2|i-j|<n$.

For odd $n$ you have the three lists $$1: (1,(n+1)/2+1),(2,(n+1)/2+2),...,((n-1)/2,n) \\ 2: ((n+1)/2,(n+1)/2) \\ 3: ((n+1)/2+1,1),((n+1)/2+2,2),...,(n,(n-1)/2)$$ which gives the sum $(n^2-1)/2$. As before permuting distinct elements $i,j=1,...,(n-1)/2$ within each list doesn't change the value. E.g. for list 1 we have: $|(n+1)/2+j-i|+|(n+1)/2+i-j|=n+1 \, .$ Permuting element $(n+1)/2+i$ from list 1 with $j$ from list 3 gives $|i-j|+|(n+1)/2+j-(n+1)/2-i|=2|i-j|<n+1 \, .$ Finally you can check that permuting elements from list 1 or 3 with the element of list 2 doesn't change the value e.g. take $(n+1)/2+i$ from list 1 reduces the sum of list 1 by $i$, but the value in list 2 increases to $i$.

Overall the maximum sum is $\left \lfloor \frac{n^2}{2} \right \rfloor$.

Answer 2

Write $f(\pi):=\sum\limits_{i=1}^n\,\big|\pi(i)-i\big|$ for each $\pi\in S_n$. Decompose a permutation $\pi\in S_n$ as a product of disjoint cycles $$\pi=\gamma_1\gamma_2\cdots\gamma_k\,.$$ For each $j=1,2,\ldots,k$, let $m(\gamma_j)$ and $M(\gamma_j)$ denote the smallest entry and the largest entry in the cycle $\gamma_j$, respectively. Prove (using the Triangle Inequality for absolute values) that $$f(\pi)\leq 2\,\sum_{j=1}^k\,\big(M(\gamma_j)-m(\gamma_j)\big)\,.\tag{*}$$ Use the previous inequality to show that $$\max_{\pi\in S_n}\,f(\pi)\leq 2\,\left(\sum_{j=\left\lceil \frac{n}{2}\right\rceil+1}^n\,j-\sum_{j=1}^{\left\lfloor \frac{n}{2}\right\rfloor}\,j\right)=2\left\lfloor\frac{n}{2}\right\rfloor\left\lceil\frac{n}{2}\right\rceil=2\left\lfloor\frac{n^2}{4}\right\rfloor=\left\lfloor\frac{n^2}{2}\right\rfloor\,.\tag{#}$$ See the spoiler below if you want to see how to deduce (#) from (*).

To deduce (#) from (*), we note the following. If we reorder $M(\gamma_1)$, $M(\gamma_2)$, $\ldots$, $M(\gamma_k)$ from the largest to the smallest and call the new sequence $M_1$, $M_2$, $\ldots$, $M_k$, then $$M_j\leq n-j+1\text{ for }j=1,2,\ldots,k\,.$$ Similarly, if we reorder $m(\gamma_1)$, $m(\gamma_2)$, $\ldots$, $m(\gamma_k)$ from the smallest to the largest and call the new sequence $m_1$, $m_2$, $\ldots$, $m_k$, then $$m_j\geq j\text{ for }j=1,2,\ldots,k\,.$$

The inequality (#) becomes an equality if $$\pi(i)=n-i+1$$ for every $i=1,2,\ldots,n$. Any $\pi\in S_n$ such that $f(\pi)=\left\lfloor\dfrac{n^2}{2}\right\rfloor$ is a product of $\left\lfloor\dfrac{n}{2}\right\rfloor$ disjoint cycles of the form $\left(a\,\,b\right)$ where $a\in\Bigg\{1,2,\ldots,\left\lfloor\dfrac{n}{2}\right\rfloor\Bigg\}$ and $b\in\Bigg\{\left\lfloor\dfrac{n}{2}\right\rfloor+1,\left\lfloor\dfrac{n}{2}\right\rfloor+2,\ldots,n\Bigg\}$. That is, there are precisely $\left\lfloor\dfrac{n}{2}\right\rfloor !$ possible permutation $\pi\in S_n$ such that $f(\pi)$ is the maximum value $\left\lfloor\dfrac{n^2}{2}\right\rfloor$.