Major index
In mathematics, the major index of a permutation is the sum of the positions of the descents, [runs">Permutation">descents, [runs and excedances|descents] of the permutation. In symbols, the major index of the permutation w is
For example, if w is given in one-line notation by w = 351624 = 3, w then w has descents at positions 2 and 4 and so maj = 2 + 4 = 6.
This statistic is named after Percy [Alexander MacMahon|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. 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.