Inwersja (kombinatoryka)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Ujednoznacznienie Ten artykuł dotyczy kombinatoryki. Zobacz też: inne znaczenia tego słowa.

Inwersją nazywamy parę 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[edytuj | edytuj kod]

  • 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}
  • Ilość inwersji jest taka sama dla permutacji \pi i permutacji odwrotnej \pi^{-1}.