Количество инверсий в перестановке

Инверсии  в комбинаторике – это количество пар элементов, в которых следующий элемент имеет меньший номер, чем предыдущий. Иногда важно иметь количественную оценку степени отличия произвольной перестановки от лексиграфически наименьшей по числу нарушений возрастающего порядка значений ее элементов. Любая пара элементов, где имеет место такое нарушение их взаимного положения в перестановке, называется инверсией. 

.
Количество инверсий в перестановке
Последовательность
{ }

Инверсии перестановок

Для компактной записи инверсий по элементам перестановки применяются вектор инверсий (V1,…Vj,…Vn) и таблица инверсий (W1,…Wj,…Wn). Эти обе формы записи идентифицируют числа инверсий для всех элементов перестановки.

Состав вектора и таблицы инверсий для цифровой перестановки P=(5,9,1,8,2,6,4,7,3) показан в следующем примере, где для наглядности индексированы позиции всех элементов:

j123456789
pj591826473
Vj002132426
Wj236402219

В частности, в этом примере V8=2, потому что слева от элемента P8=7 в перестановке есть 2 элемента P2=9 и P4=8 с большим значением, чем 7. С другой стороны, W8=1,потому что слева от элемента со значением 8 (это P4) в перестановке имеется только 1 элемент (P2=9), значение которого больше, чем 8. Аналогичным образом можно обосновать выбор величин остальных компонентов вектора и таблицы инверсий в данном примере. Следует также отметить, что для любой перестановки значения компонентов вектора и таблицы инверсий связаны следующими соотношениями:

V1 = Wn = 0; V= Wi | i = Pj; Wj = Vi | Pi = j.

Возвращаясь к интегральным оценкам, следует отметить, что сумма значений всех компонентов вектора или таблицы инверсий определяет общее число инверсий I перестановки. В частности, для рассмотренного примера оно равно 20:

I(5, 9, 1, 8, 2, 6, 4, 7, 3) = 20.