Inwersja (kombinatoryka)

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

Inwersja – para liczb: w ciągu: , gdzie j < k, jeżeli .

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ę do oznaczenia liczby inwersji w pewnej permutacji .

Właściwości[edytuj]

  • Przestawienie dwóch liczb w permutacji zmienia liczbę inwersji o nieparzystą liczbę. Czyli: , gdzie jest permutacją po przestawieniu tych liczb.
  • Niech będzie pewną permutacją liczb naturalnych, w której . Niech będzie ciągiem liczb postaci . Zachodzi wtedy:
  • Liczba inwersji jest taka sama dla permutacji i permutacji odwrotnej .