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{maj}(w) = \sum_{w(i)>w(i+1)} i.

For example, if w is given in one-line notation by w = 351624 (that is, w is the permutation of {1, 2, 3, 4, 5, 6} 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.[1]) 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{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}

References

  1. ↑ M. Bóna, Combinatorics of Permutations, 2004, p. 43ff, ISBN 1-58488-434-7.
This article is issued from Wikipedia - version of the Sunday, January 10, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.