Se proporciona una lista de [math] n [/ math] elementos distintos. ¿Por qué el número total de inversiones en la lista y en su reverso es igual a [math] n (n-1) / 2 [/ math]?

Answer 1

Consideraré, como en el ejercicio, una lista L de N elementos distintos .

Considere un elemento X en la posición i. El número de inversiones con respecto a este elemento es la cantidad de elementos a su derecha que son más pequeños que X.

Ahora considere este mismo elemento X en la lista inversa L ‘ . Los elementos que estaban a su izquierda en la lista original, ahora están a su derecha.

Entonces, considerando las inversiones tanto en la lista original como en la inversa, todos los elementos estarán a la derecha de cada elemento: ya sea en L o L ‘ .

Para cada elemento X , el total de inversiones en ambas listas será igual al número de elementos más pequeños que X. Dado que todos los elementos son distintos, esto es igual a

[matemáticas] 0 + 1 + 2 +… + (N-1) = \ frac {N (N-1)} {2} = \ binom {n} {2} [/ matemáticas].