Major index

In mathematics (and particularly in combinatorics), the major index of a permutation is the sum of the positions of the descents of the permutation. In symbols, the major index of the permutation ''w'' is

: $\operatorname(w) = \sum_ i.$

For example, if ''w'' is given in one-line notation by ''w'' = 351624 (that is, ''w'' is the permutation of such that ''w''(1) = 3, ''w''(2) = 5, etc.) then ''w'' has descents at positions 2 (from 5 to 1) and 4 (from 6 to 2) and so maj(''w'') = 2 + 4 = 6.

This statistic is named after Major Percy Alexander MacMahon who showed in 1913 that the distribution of the major index on all permutations of a fixed length is the same as the distribution of inversions. That is, the number of permutations of length ''n'' with ''k'' inversions is the same as the number of permutations of length ''n'' with major index equal to ''k''. (These numbers are known as ''Mahonian numbers'', also in honor of MacMahon.M. Bóna, Combinatorics of Permutations, 2004, p. 43ff, .) In fact, a stronger result is true: the number of permutations of length ''n'' with major index ''k'' and ''i'' inversions is the same as the number of permutations of length ''n'' with major index ''i'' and ''k'' inversions, that is, the two statistics are equidistributed. For example, the number of permutations of length 4 with given major index and number of inversions is given in the table below.
:$\begin & 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$

References

*.

Permutations

{{combin-stub