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

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

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

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

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

$0\le 𝚒𝚗𝚟(X)\le \frac{n(n-1)}{2}$

Див. також

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

Джерела

• Шаблон:Вишенський.Перестюк.Комбінаторика
• Шаблон:TAOCP.v3