Inwersja (kombinatoryka)

Szablon:Inne znaczenia 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}.$