Bonsoir !
Quelqu'un aurait-il une idée pour calculer le maximum, pour sigma parcourant l'ensemble des permutations de [1;n] (n€N* fixé), de la somme de i=1 à n de |sigma(i)-i| ? Pour quelle(s) permutation(s) ce maximum est-il atteint ?
Merci d'avance

Intuitivement je dirais pour tau(1;n) o tau(2;n-2) o tau(3;n-3) o ... mais je ne suis pas sûr

Je dirais que c'est i envoyé vers (n+1-i) la permutation que tu cherches.
Après pour le prouver là comme ça je vois pas. Je cherche.

Il me semble avoir déjà eu ca en colle et je crois que Leit a raison

J'ai une idée de ""démo"".
sigma est une bijection de [1;n] dans [1;n].
On veut que sum(sigma(x)-x,x=1..n) soit maximale.

La distance entre deux éléments vaut au plus n. Entre 1 et n, donc on échange ces deux là. Une fois cette permutation effectuée, la distance la plus grande est entre n-1 et 2, donc on les échange, et etc...

Par contre pour écrire ça proprement j'ai du mal.

Merci, je vais essayer de formaliser ça !