En mathématiques, et plus particulièrement en combinatoire, l'indice majeur d'une permutation est la somme des indices des descentes de la permutation. Formellement, l'indice majeur de la permutation est
.
Par exemple, si la permutation est donnée en notation sur une seule ligne par (c'est-à-dire que est la permutation de définie par ), alors a des descentes aux indices 2 (de 5 à 1) et 4 (de 6 à 2) et donc .
Cette statistique porte le nom du major Percy Alexander MacMahon, qui a démontré en 1913 que la distribution de l'indice majeur pour toutes les permutations d'une longueur donnée est identique à celle des inversions. Autrement dit, le nombre de permutations de longueur avec inversions est égal au nombre de permutations de longueur dont l'indice majeur vaut . (Ces nombres sont appelés nombres mahoniens, en hommage à MacMahon..)
Plus précisément, en notant le nombre d'inversions d'une permutation de longueur , on a (pour une indéterminée ) : .
En réalité, on a un résultat plus fort : le nombre de permutations de longueur d'indice majeur qui admettent inversions est égal au nombre de permutations de longueur d'indice majeur qui admettent inversions, c'est-à-dire que les deux statistiques sont équidistribuées.
Par exemple, le tableau ci-dessous donne le nombre de permutations de longueur 4 qui ont un indice majeur et un nombre d'inversions donnés : le résultat se manifeste par le fait que le tableau est symétrique par rapport à la diagonale principale.
Références
.
Catégorie:Permutation