Определить четность подстановок (2n 2n-1 ... 4 3 2 1
2n-1 2n......3 4 1 2)

Предыдущий
вопрос Следующий
вопрос

Для определения четности подстановки нужно посчитать количество инверсий в ней. Инверсией называется пара элементов (i, j), такая что i < j, но a[i] > a[j].

В данной подстановке (2n, 2n-1, ..., 4, 3, 2, 1, ..., 2n-1, 2) можно найти такие инверсии:
(2n, 2n-1), (2n, 2n-2), ..., (2n, 1), (2n, 2n-1), ..., (3, 2), (2, 1)

Таким образом, общее количество инверсий равно n*(n-1)/2. Так как n(n-1)/2 - четное число, то подстановка имеет четную четность.