Indice majeur

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

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

maj (w) = \sum_{w (i) > w (i + 1)} i

.

Par exemple, si la permutation $w$ est donnée en notation sur une seule ligne par $w = 351624$ (c'est-à-dire que $w$ est la permutation de ${1, 2, 3, 4, 5, 6}$ définie par $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 $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 $inv (w)$ le nombre d'inversions d'une permutation $w$ de longueur $n$ , on a (pour une indéterminée $q$ ) :

\sum_{w \in 𝔖_{n}} q^{maj (w)} = \prod_{i = 1}^{n} \frac{q^{i} - 1}{q - 1} = \sum_{w \in 𝔖_{n}} q^{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.

\begin{matrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 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{matrix}

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Major index » (voir la liste des auteurs).

↑ Miklós Bóna, Combinatorics of permutations, 2004, 383 p. (ISBN 1-58488-434-7), p. 43 sqq..

Percy Alexander MacMahon, « The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects », American Journal of Mathematics, vol. 35,‎ 1913, p. 281-322 (DOI 10.2307/2370312, JSTOR 2370312).

Portail des mathématiques

[1] Miklós Bóna, Combinatorics of permutations, 2004, 383 p. (ISBN 1-58488-434-7), p. 43 sqq..

[1]