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

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

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

Інверсією в перестановці ${\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}}}$

Див. також

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

Джерела

• В.А. Вишенський, М.О. Перестюк. Комбінаторика: перші кроки. — Кам'янець-Подільський : Аксіома, 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.(англ.)