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

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

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

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

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

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

Див. також

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

Джерела

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