Question

Формула чётности инверсии в перестановке?

Answer 1

Перестановка называется четной, если число инверсий в ней четно, и нечетной - в противном случае.

Количество инверсий (беспорядка) в перестановке – это количество пар элементов (не обязательно соседних), в которых следующий элемент имеет меньший номер, чем предыдущий.  

Пример 1.6. Найти количество инверсий в перестановке

(2, 3, 1, 6, 4, 5, 7).

 

Решение.

Первый способ. Перечислим все пары: (2, 3), (2, 1) , (2, 6), (2, 4), (2, 5),

(2, 7), (3, 1) , (3, 6), (3, 4), (3, 5), (3, 7), (1, 6), (1, 4), (1, 5), (1, 7), (6, 4) ,

(6, 5) , (6, 7), (4, 5), (4, 7) и (5, 7). Инверсии подчёркнуты – всего их 4.

 

Второй способ представляет собой алгоритм нахождения числа инверсий.

Считаем количество элементов левее 1: их 2. Удаляем единицу: (2, 3, 6, 4, 5, 7). Считаем количество элементов левее 2: их нет (0). Далее удаляем двойку: (3, 6, 4, 5, 7). Считаем количество элементов левее 3: их тоже нет. Продолжаем. После удаления тройки: (6, 4, 5, 7) находим, что левее 4 есть 1 элемент, после удаления 4: (6, 5, 7) левее 5 – 1 элемент; и в (6, 7) левее 6 нет элементов. Суммируем найденные числа – это и есть количество инверсий: 2 + 0 + 0 + 1 + 1 + 0 = 4.

Answer 2

Для понимания формулы чётности инверсии в перестановке давайте разберем несколько ключевых понятий.

Перестановка (пермутация): Перестановка множества чисел - это упорядоченная последовательность этих чисел. Например, перестановка чисел 1, 2, 3 может быть (2, 1, 3), что означает, что 1 заменено на 2, 2 на 1, а 3 остается на своем месте.

Инверсия в перестановке: Инверсия в перестановке - это пара элементов, которые стоят в неправильном порядке относительно упорядоченной последовательности. Например, в перестановке (2, 1, 3) инверсии - (2, 1), потому что 2 стоит перед 1.

Чётность и нечётность: Перестановка может быть либо чётной, либо нечётной, в зависимости от количества инверсий в ней.

Теперь формула чётности инверсии в перестановке обычно выражается через количество инверсий. Пусть \(n_i\) - количество инверсий в перестановке.

Формула: \[(-1)^{n_i}\]

Если количество инверсий чётное, то \((-1)^{n_i} = 1\), и перестановка считается чётной. Если количество инверсий нечётное, то \((-1)^{n_i} = -1\), и перестановка считается нечётной.

Эта формула основана на свойстве того, что чётное количество инверсий сохраняет чётность, а нечётное количество инверсий меняет чётность перестановки.