Інверсія (дискретна математика)

Інверсією в дискретній математиці називається послідовність із двох чисел впорядкованих в оберненому порядку.

Показана одна із інверсій в перестановці

Інверсією в перестановці ${\displaystyle \pi }$ називається пара індексів ${\displaystyle i,\ j}$ така, що ${\displaystyle 1\leqslant i<j\leqslant n}$ и ${\displaystyle \pi (i)>\pi (j)}$. Парність числа інверсій в перестановці визначає парність перестановки.

Числом інверсії послідовності є кількість інверсій в послідовності, це число в межах

${\displaystyle 0\leq {\mathtt {inv}}(X)\leq {\frac {n(n-1)}{2}}}$

Див. також

• Сортування бульбашкою

Джерела

• И. И. Ежов, А. В. Скороход, М. И. Ядренко. Элементы комбинаторики. Москва: Наука, 1977. — 80 с.