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

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

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

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.