Liczba inwersji w permutacji
Inwersje w kombinatoryce to liczba par elementów, w których następny element ma mniejszą liczbę niż poprzedni. Czasami ważne jest, aby określić ilościowo stopień odróżnienia arbitralnej permutacji od leksygraficznie najmniejszej liczby naruszeń rosnącej kolejności wartości jej elementów. Każda para elementów, w których występuje takie naruszenie ich wzajemnej pozycji w permutacji, nazywa się inwersją.
.Inwersje permutacji
Do kompaktowego zapisu inwersji na elementach permutacji stosuje się wektor inwersji (V1,…Vj,…Vn) i tabela inwersji (W1,…Wj,…Wn). Te obie formy zapisu identyfikują liczby inwersji dla wszystkich elementów permutacji.
Skład wektora i tabeli inwersji dla permutacji cyfrowej P=(5,9,1,8,2,6,4,7,3) pokazano w poniższym przykładzie, w którym pozycje wszystkich elementów są indeksowane dla jasności:
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | pj | 5 | 9 | 1 | 8 | 2 | 6 | 4 | 7 | 3 | Vj | 0 | 0 | 2 | 1 | 3 | 2 | 4 | 2 | 6 | Wj | 2 | 3 | 6 | 4 | 0 | 2 | 2 | 1 | 9 |
W szczególności w tym przykładzie V8=2, ponieważ po lewej stronie elementu P8=7 w permutacji znajdują się 2 elementy P2=9 i P4=8 o większej wartości niż 7. Z drugiej strony, W8=1, ponieważ po lewej stronie elementu o wartości 8 (jest to P4) w permutacji jest tylko 1 element (P2=9), którego wartość jest większa niż 8. Podobnie można uzasadnić wybór wielkości pozostałych składników wektora i tabeli inwersji w tym przykładzie. Należy również zauważyć, że dla każdej permutacji wartości składników wektora i tabeli inwersji są powiązane następującymi relacjami:
V1 = Wn = 0; Vj = Wi | i = Pj; Wj = Vi | Pi = j.
Wracając do szacunków całkowych, należy zauważyć, że suma wartości wszystkich składników wektora lub tabeli inwersji określa całkowitą liczbę inwersji i permutacji. W szczególności dla rozważanego przykładu jest to 20:
I(5, 9, 1, 8, 2, 6, 4, 7, 3) = 20.