Какое максимальное число инверсий может иметь массив A размера n?

Question

У нас есть массив A [1 ... n]. В инверсии это когда i A [j]. Я хочу описать максимальное количество инверсий, которое может иметь массив A длины n (учтите, что начальный индекс равен 1, а не 0).

Я пытался найти образец, но, похоже, не могу придумать обобщенную формулу для n.

at n=3 we have 3 possible inversions
at n=4 we have 7 possible inversions 
at n=5 we have 10 possible inversions 
at n=6 we have 15 possible inversions (10 + 5)
at n=7 we have 21 possible inversions (15 + 6)
at n=8 we have 28 possible inversions (21 + 7)

Кажется, что есть повторение nb inversions for n = nb inversion for n-1 + (n-1), но, похоже, оно не выполняется для n=3,4,5.

Answer 1

Максимальное количество инверсий достигается для массива, отсортированного в обратном порядке.

Такой массив содержит

(n-1) + (n-2) + (n-3) +.. + 1 = n*(n-1)/2 

инверсий (формула для арифметической прогрессии c, так называемая triangular numbers )

Обратите внимание, что at n=4 we have 7 является ошибкой - только 6.