Nombre d’Inversions dans la permutation

Les Inversions en combinatoire sont le nombre de paires d’éléments dans lesquelles l’élément suivant a un nombre plus petit que le précédent. Parfois, il est important de quantifier le degré de différence entre une permutation arbitraire et la plus petite violation lexigraphique de l’ordre croissant des valeurs de ses éléments. Toute paire d’éléments où une telle violation de leur position mutuelle dans la permutation se produit est appelée inversion.

.
Nombre d'Inversions dans la permutation
Séquence
{ }

Inversions de permutations

Pour l’enregistrement Compact des Inversions sur les éléments de permutation, utilisez le vecteur d’Inversions (V1,…Vj,…Vn) et tableau des Inversions (W1,…Wj,…Wn). Ces deux formes d’enregistrement identifient les nombres d’Inversions pour tous les éléments de permutation.

Composition du vecteur et de la table d’inversion pour la permutation numérique P=(5,9,1,8,2,6,4,7,3) illustré dans l’exemple suivant, où les positions de tous les éléments sont indexées pour plus de clarté:

j123456789
pj591826473
Vj002132426
Wj236402219

 

V1 = Wn = 0; V= Wi | i = Pj; Wj = Vi | Pi = j.

 

I(5, 9, 1, 8, 2, 6, 4, 7, 3) = 20.