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

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

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

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

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

Див. також

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

Джерела

В.А. Вишенський, М.О. Перестюк. Комбінаторика: перші кроки. — Кам'янець-Подільський : Аксіома, 2010. — 324 с. — ISBN 978-966-496-136-0.(укр.)
Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — ISBN 0-201-89685-0.(англ.)