¿Cuál es el nombre de esta cantidad?

Question

Para cada permutación $\sigma$ $ \left\{ 1, 2, \dots, n \right\}$ definir $$\operatorname{dist}(\sigma)=\sum_{i=1}^{n}\left| \sigma (i)-i \right|$$ Para cada una de las $n\in\mathbb{N}$, estoy interesado en encontrar el valor máximo de esta función, puede marcar, es decir, $$M_n=\max_{\sigma\in D_n}\left\{\operatorname{dist}(\sigma)\right\}$$

Qué $M_n$ tiene un nombre convencional? Utiliza? Existe una formula para encontrar?

Me he dado cuenta de que $M_n$ crece "en parejas", lo que significa que por cada extraño $a\in \mathbb{N}$ sostiene que $$M_{a+1}-M_a=M_{a+2}-M_{a+1}$$

Supongo que puede representar algún tipo de medida de dureza para ordenar.

Answer 1

Deje $n=2m$. Tomar cualquier permutación donde si $n\leq m$ $\sigma(n)>m$ e si $n>m$$\sigma(n)\leq m$. A continuación,$\sum_{(k=i)}^m|\sigma(m)-i|=\sum_{(k=i)}^m\sigma(m)-i=m^2$$\sum_{(i=m+1)}^{2m}|\sigma(m)-i|=\sum_{(i=m+1)}^{2m}i-\sigma(m)=m^2$.

Ahora supongamos que usted tiene una permutación que no cumpla con esta. A continuación, tiene un par $i,j$ donde$i,\sigma(i)\leq m$$j,(\sigma(j)>m$. Mostrar interruptor de $\sigma(i)$ $\sigma (j)$ hace que la distancia de la suma más grande.

Hacer lo mismo para el otro lado para obtener:

Para $n=2m+1$ esto es $m(2m+2)$. Para $n=2m$ esto es $2m^2$

Para una interpretación geométrica Ver que si $\sigma(m)$ $(m)$ $\sigma(j)$ $j$ están en lados diferentes, entonces la distancia entre ellos es de más de $DE+FG$