Inwersja (kombinatoryka)

kombinatoryka

Inwersja – para liczb: w ciągu: gdzie 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ściEdytuj

  • 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