Indice majeur

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 w est

${\displaystyle \operatorname {maj} (w)=\sum _{w(i)>w(i+1)}i}$.

Cet article est une ébauche concernant les mathématiques.

Par exemple, si la permutation w est donnée en notation sur une seule ligne par ${\displaystyle w=351624}$ (c'est-à-dire que w est la permutation de ${\displaystyle \{1,2,3,4,5,6\}}$ définie par ${\displaystyle w(1)=3,\ w(2)=5,\ w(3)=1}$, etc.), alors w a des descentes aux indices 2 (de 5 à 1) et 4 (de 6 à 2) et donc ${\displaystyle \operatorname {maj} (w)=2+4=6}$.

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 n avec k inversions est égal au nombre de permutations de longueur n dont l'indice majeur vaut k. (Ces nombres sont appelés nombres mahoniens, en hommage à MacMahon^[1].)

Plus précisément, en notant ${\displaystyle \operatorname {inv} (w)}$ le nombre d'inversions d'une permutation w de longueur n, on a (pour une indéterminée q) :

${\displaystyle \sum _{w\in {\mathfrak {S}}_{n}}q^{\operatorname {maj} (w)}=\prod _{i=1}^{n}{\frac {q^{i}-1}{q-1}}=\sum _{w\in {\mathfrak {S}}_{n}}q^{\operatorname {inv} (w)}}$.

En réalité, on a un résultat plus fort : le nombre de permutations de longueur n d'indice majeur k qui admettent i inversions est égal au nombre de permutations de longueur n d'indice majeur i qui admettent k 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.

${\displaystyle {\begin{array}{c|ccccccc}&0&1&2&3&4&5&6\\\hline 0&1&0&0&0&0&0&0\\1&0&1&1&1&0&0&0\\2&0&1&2&1&1&0&0\\3&0&1&1&2&1&1&0\\4&0&0&1&1&2&1&0\\5&0&0&0&1&1&1&0\\6&0&0&0&0&0&0&1\end{array}}}$