Inwersja (kombinatoryka)

Inwersja – para liczb: $a_{j},a_{k}$ w ciągu: $a_{1},a_{2},\dots ,a_{n}\in \mathbb {N} ,$ gdzie $j<k,$ jeżeli $a_{j}>a_{k}$.

Przykład: Niech dany będzie ciąg liczb: 1, 2, 5, 7, 4, 6 – pary (5, 4), (7,4) oraz (7, 6) tworzą inwersje w tym ciągu.

Używa się $i(\pi )$ do oznaczenia liczby inwersji w pewnej permutacji $\pi .$

Właściwości

• Przestawienie dwóch liczb w permutacji $\pi$ zmienia liczbę inwersji o nieparzystą liczbę. Czyli: $(-1)^{i(\pi )}=-(-1)^{i(\delta )},$ gdzie $\delta$ jest permutacją $\pi$ po przestawieniu tych liczb.

• Niech $\pi$ będzie pewną permutacją liczb naturalnych, w której $\pi (j)=k.$ Niech $\delta$ będzie ciągiem liczb postaci $\pi (1),\pi (2),\dots ,\pi (j-1),\pi (j+1),\dots ,\pi (n).$ Zachodzi wtedy: $(-1)^{i(\pi )}=(-1)^{i(\delta )+j+k}.$

• Liczba inwersji jest taka sama dla permutacji $\pi$ i permutacji odwrotnej $\pi ^{-1}.$