Max d’une somme

Bonjour,
Je commence avec une conjecture pour $n=2p$: les permutations maximales sont exactement celles qui envoient les $p$ premiers termes sur les $p$ derniers et vice-versa, que l'on peut compter au nombre de $(p!)^{2}$. De plus, la permutation $\begin{pmatrix}
1, 2, ..., n-1, n\\
n, n-1, ..., 2, 1
\end{pmatrix}$ réalise le maximum, qui vaudra sauf erreur de calcul $2\sum_{k=1}^{p}(2n-2p+1)=2p^{2}$.

Pour le cas impair $n=2p+1$, je pense qu'on peut raisonner de même avec une coupure des $p$ premiers indices envoyés sur les $p$ derniers (modulo un point fixe), ce qui doit donner une formule très similaire.

Bonjour, il y a le fait d'être rigoureux, vu que les réponses donnent la permutation maximale, on peut démontrer que le nombre de différences dans la somme (en valeure absolue) égale à $m$ pour $1\le m\le n-1$ est au plus $2(n-m)$. Ceci pour n'importe quelle permutation et donc -en comptant les differences du plus petit au plus grand- la permutation maximale en est pour la somme $$\sum_{i=1}^{n-1}i=\dfrac{n(n-1)}{2}.

$$ À corriger... Edit

Pour $n=2p$, le maximum est aussi réalisé pour la permutation $\tau$ de $\Z/(2p\Z)$ $x \mapsto x+p$.
Je n'ai pas compris pourquoi le problème revient à maximaliser $\sum (k-\sigma(k))^2$.

Bonjour, le problème général tient aussi si on remplace la suite d'entiers par une suite croissante $u_n,$ dans ce cas le maximum $$\max_{\sigma\in \mathfrak{S_n}}\sum_{k=1}^{n} | u_k - u_{\sigma(k)}|
$$ est pour la permutation des transpositions inversant l'ordre de la suite appelé $T$. Je crois même que la suite pourrait prendre des valeurs négatives. En tout cas pour prouver ce cas particulier pour les entiers $1,\ldots,n$ on devrait passer par le cas général de la façon suivante.

Pour une suite croissante d'entiers $u_k$, $\mathfrak{T}$ est le groupe des transpositions : $$\max_{\sigma\in \mathfrak{T}}\sum_{k=1}^{n} | u_k- u_{\sigma(k)}|=\sum_{k=1}^{n} | u_k- u_{T(k)}|.

$$ Puis comme toute permutation est une composition de cycles disjoints on peut aller par récurrence (on compare le cas de cycle complet contre la transposition $T$ qui devrait être simple, en prenant les images des extrémités de la suite formant le cycle...) pour trouver la somme maximale sur les éléments de chaque cycle (on inverse l'ordre d'éléments composants le cycle) en appliquant $T$. Et donc on revient au cas de maximiser la somme sur les groupes de transpositions. Comme vous dites il y a plein de permutation réalisant le maximum entre autre $T$.

Edit 3
Cordialement.

En reprenant une idée de Polka ci-dessus on peut prouver que la permutation $\begin{pmatrix}

1, 2, ..., n-1, n\\

n, n-1, ..., 2, 1

\end{pmatrix}$ réalise le maximum sans distinguer cas pair/impair.

Pour une permutation $\sigma$ quelconque notons $S_{\sigma}:=\sum_{k=1}^{n} | k - \sigma(k)|$.

On remarque que si pour $i<j$ on a $\sigma(i)<\sigma(j)$ alors $S_{\sigma}\leq S_{\tilde{\sigma}}$ (où $\tilde{\sigma}=\sigma \circ (i,j)$).

À présent si $\sigma(1)\neq n$ alors on considère $j>1$ tel que $\sigma(j)=n$ et on applique la transformation ci-dessus pour obtenir une permutation qui envoie $1$ sur $n$.

Avec cette nouvelle permutation, notée à nouveau $\sigma$, si $\sigma(2)\neq n-1$ alors on considère $j>2$ tel que $\sigma(j)=n-1$ et on applique la transformation ci-dessus pour obtenir une permutation qui envoie $2$ sur $n-1$.

Bref, par récurrence on construit une suite finie de permutations qui rendent la somme $S_{\sigma}$ de plus en plus grande. À la fin on tombe sur la permutation $\begin{pmatrix}

1, 2, ..., n-1, n\\

n, n-1, ..., 2, 1

\end{pmatrix}$.