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

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

Если перестановка записана как a₁, a₂, ..., a_n, то инверсия - это пара индексов (i, j), где i < j и a_i > a_j. Количество инверсий показывает, насколько перестановка отличается от упорядоченной.

Формулы и методы решения: число инверсий задается как мощность множества пар (i, j), где i < j и a_i > a_j. \[ I = |\{(i, j): i < j,\ a_i > a_j\}| \]

Где используется и применяется: число инверсий важно в комбинаторике, при анализе сортировок, оценке упорядоченности данных и в задачах на ранжирование.

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

Интересный факт: максимальное число инверсий для перестановки длины n равно n(n-1)/2 и достигается в полностью обратной последовательности.