Inwersja (kombinatoryka)

Inwersja – para liczb: ${\displaystyle a_{j},a_{k}}$ w ciągu: ${\displaystyle a_{1},a_{2},\dots ,a_{n}\in \mathbb {N} ,}$ gdzie ${\displaystyle j<k,}$ jeżeli ${\displaystyle 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ę ${\displaystyle i(\pi )}$ do oznaczenia liczby inwersji w pewnej permutacji ${\displaystyle \pi .}$

Właściwości

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

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

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