Как определить число инверсий для перестановки? Нужно определить число инверсий и указать общий признак для тех чисел n, для которых эта перестановка четна и нечетна.
1, 4, 7, ... , 3n-2, 2, 5, 8, ... , 3n-1, 3, 6, 9, ... , 3n
Объясните пожалуйста алгоритм решения подобного вида задач на этом примере.

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

Для определения числа инверсий в данной перестановке нужно посчитать количество пар элементов, расположенных в обратном порядке относительно друг друга.

Для данной перестановки у нас есть три группы элементов: первая - элементы 1, 4, 7, ..., 3n-2, вторая - элементы 2, 5, 8, ..., 3n-1, третья - элементы 3, 6, 9, ..., 3n.

Теперь для каждой группы необходимо посчитать количество инверсий внутри нее. Например, в первой группе у нас элементы 1, 4, 7, ..., 3n-2. Если взять два элемента, например, 1 и 4, то они образуют инверсию, так как 1 < 4. Аналогично во второй и третьей группах.

Теперь посчитаем количество инверсий в каждой группе: в первой группе это будет (3n-2) раз (так как каждый элемент встает в своем порядке), во второй и третьей группах - 0 инверсий.

Таким образом, общее количество инверсий для данной перестановки равно (3n-2).

Теперь посмотрим на общий признак для тех чисел n, для которых перестановка будет четной или нечетной. У нас есть 3 группы элементов, и каждая группа содержит одинаковое количество элементов. Поэтому если количество элементов в каждой группе четное, то общее количество инверсий также будет четным числом. А если количество элементов в каждой группе нечетное, то общее количество инверсий будет нечетным числом. Таким образом, перестановка будет четной для четного n и нечетной для нечетного n.