major index

combinatorics

What

The major index of a permutation $w$ is the sum of the positions of the descent of the permutation.

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

Example: $w=351624$ is a permutation of $\{1,2,3,4,5,6\}$, there are 2 descents at positions 2 (from 5 to 1) and 4 (from 6 to 2) → $maj(w)=2+4=6$

Named after Major Percy Alexander MacMahon.

Distribution

In 1913 that, MacMahon showed that: the distribution of the major index on all permutations of a fixed length is the same as the distribution of inversions.

Which means the number of permutations of length $n$ with major index equal to $k$) is the same as the number of permutations of length $n$ with $k$ inversions

(These numbers are known as Mahonian numbers, also in honor of MacMahon)

Calculation

Calculated indirectly by calculating the distribution of inversions.