number of permutations maximizing a sum 
Let $n$ be an odd integer greater than $1$. Find the number of permutations $\sigma$ of the set $\{1,\cdots, n\}$ for which $|\sigma(1) - 1| + |\sigma(2) - 2|+\cdots + |\sigma(n) - n| = \frac{n^2 - 1}2$.

I found the solution below from a book, but I have some questions:

*

*Why is $\frac{n^2 - 1}2$ the maximum possible value of $\sum_{i=1}^n |\sigma(i) - i|$? I find it hard to prove this formally as $\sigma(i)$ is a bijection. For instance, it might not be true that $|\sigma(i) - i|\leq \frac{1}n (n^2 - 1)/2$ for all $i$.

*Why must $\{\sigma((n+2)/2),\sigma((n+5)/2),\cdots, \sigma(n)\}\subset \{1,2,\cdots, (n+1)/2\}$ and why must $\{\sigma(1),\cdots, \sigma((n-1) / 2)\}\subset \{(n+1) / 2, \cdots n\}$?

*If $\sigma((n+1)/2) = k\leq (n+1)/2$, then how can one verify that $\sum_{i=1}^{n} |\sigma(i) - i|$ indeed achieves the maximum value? I'm not sure if $\sum_{i=1}^{(n-1)/2} |\sigma(i) - i|$ and $\sum_{i=(n+3)/2}^{n} |\sigma(i) - i|$ have values only dependent on $k$.

I've also read this post but I'm still unsure how to answer my questions.


 A: This is not so much a new solution as a more detailed version of what you already wrote and that hopefully clears up some  of your questions
Consider the sum for some arbitrary permuation $\sigma$ and introduce the sets $S$ and $T$ by
$$
S = \{1 \leq i \leq n | \sigma(i) \geq i\}
$$
$$
T = \{1 \leq i \leq n | \sigma(i) < i\}
$$
which implies that $S \cup T = \{1,2,\cdots,n\}$ and that for the size of the we have |S| + |T| = n. Then we can rewrite the sum as
\begin{eqnarray}
\sum_{i=1}^n | \sigma(i) - i |
& = \sum_{i \in S} \left| \sigma(i) - i \right| + \sum_{i \in T} \left| \sigma(i) - i \right| \\
& = \sum_{i \in S} \left( \sigma(i) - i \right) + \sum_{i \in T} \left( i - \sigma(i) \right) \\
& = \left( \sum_{i \in S} \sigma(i) + \sum_{i \in T} i \right) - \left( \sum_{i \in S} i + \sum_{i \in T} \sigma(i) \right)
\end{eqnarray}
In each of the four sums the terms are distinct and a subset of $\{1,2,\dots,n\}$. In the two left-hand sums together we have $n$ terms of the multiset $M=\{1,1,2,2,\dots,n,n\}$ and hence we know that
the sum can not be larger than the $n$ largest elements of $M$
$$
\sum_{i \in S} \sigma(i) + \sum_{i \in T} i \leq \frac{n+1}{2} + \frac{n+3}{2} + \frac{n+3}{2} + \dots + n + n = \frac{(n+1)(3n-1)}{4} \qquad (*)
$$
Likewise, the two right-hand sums can not be smaller than the $n$ smallest elements of $M$
$$
\sum_{i \in S} i + \sum_{i \in T} \sigma(i) \geq 1 + 1 + 2 + 3 \dots + \frac{n-1}{2} + \frac{n-1}{2} + \frac{n+1}{2} = \frac{(n+1)^2}{4} \qquad (**)
$$
and hence we find that
$$
\sum_{i=1}^n | \sigma(i) - i | \leq \frac{(n+1)(3n-1)}{4}  -  \frac{(n+1)^2}{4} = \frac{n^2-1}{2}
$$
This is an upper bound for the sum and we just need to show that it can be reached, which is the case for the permutation $\sigma(i)=n+1-i$.
This proofs the maximum value and answers your first question.
Since the elements in either sum of $(*)$ are distinct, there are only two possibilities in which a permutation can reach the maximum in $(*)$

*

*$\{\sigma(i) | i \in S\} = \{\frac{n+1}{2},\frac{n+3}{2},\dots,n\}$
and $T = \{\frac{n+3}{2},\frac{n+5}{2},\dots,n\}$
Since we defined $S$ and $T$ such that if $i \in S$ than $i \notin T$, it then follows that
$S = \{1,2,\dots,\frac{n+1}{2} \}$ and
$\{\sigma(i) | i \in T\} = \{1,2,\dots,\frac{n-1}{2}\}$
Hence
$$\{\sigma(1),\dots,\sigma(\frac{n+1}{2})\} = \{\frac{n+1}{2},\dots,n\}$$
$$\{\sigma(\frac{n+3}{2}),\dots,\sigma(n)\} = \{1,\dots,\frac{n-1}{2}\}$$


*$\{\sigma(i) | i \in S\} = \{\frac{n+3}{2},\frac{n+5}{2},\dots,n\}$
and
$T = \{\frac{n+1}{2},\frac{n+3}{2},\dots,n\}$
Since we defined $S$ and $T$ such that if $i \in S$ than $i \notin T$, it then follows that
$S = \{1,2,\dots,\frac{n-1}{2}\}$
and
$\{\sigma(i) | i \in T\} = \{1,2,\dots,\frac{n+1}{2}\}$
Hence
$$\{\sigma(1),\dots,\sigma(\frac{n-1}{2})\} = \{\frac{n+3}{2},\dots,n\}$$
$$\{\sigma(\frac{n+1}{2}),\dots,\sigma(n)\} = \{1,\dots,\frac{n+1}{2}\}$$
Combining the result of these both posibilities gives indeed
$$\{\sigma(1),\dots,\sigma(\frac{n-1}{2})\} \subset \{\frac{n+1}{2},\dots,n\}$$
$$\{\sigma(\frac{n+3}{2}),\dots,\sigma(n)\} \subset \{1,\dots,\frac{n+1}{2}\}$$
Which gives the answer to your second question. (Note there was a small typo , $\sigma((n+2)/2)$ should have been  $\sigma((n+3)/2)$)
In order to confirm that all these permutations are correct and result in the maximum sum, we need to check that they satisfy the definition of $S$ given by $S = \{1 \leq i \leq n | \sigma(i) \geq i\}$ so that each of the terms $|\sigma(i) -i|$ is correctly rewritten.

*

*for $1 \leq i \leq \frac{n+1}{2}$ we have $\sigma(i) \geq \frac{n+1}{2} \geq i$
for $\frac{n+3}{2} \leq i \leq n$ we have $\sigma(i) \leq \frac{n-1}{2} < i$


*for $1 \leq i \leq \frac{n-1}{2}$ we have $\sigma(i) \geq \frac{n+3}{2} > i$
for $\frac{n+1}{2} \leq i \leq n$ we have $\sigma(i) \leq \frac{n+1}{2} \leq i$
In the last case equality could occur, but only for one term in the sum,i.e.  $\sigma(\frac{n+1}{2})=\frac{n+1}{2}$. Permutations that include this particular pair, however, are not new permutations, but ones that were already included under 1).
I hope this answers your third question.
