In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
(and particularly in
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
), the major index of a
permutation
In mathematics, a permutation of a set can mean one of two different things:
* an arrangement of its members in a sequence or linear order, or
* the act or process of changing the linear order of an ordered set.
An example of the first mean ...
is the sum of the positions of the
descents of the permutation. In symbols, the major index of the permutation ''w'' is
:
For example, if ''w'' is given in
one-line notation
In mathematics, a permutation of a set can mean one of two different things:
* an arrangement of its members in a sequence or linear order, or
* the act or process of changing the linear order of an ordered set.
An example of the first meanin ...
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
A statistic (singular) or sample statistic is any quantity computed from values in a sample which is considered for a statistical purpose. Statistical purposes include estimating a population parameter, describing a sample, or evaluating a hypot ...
is named after
Major Percy Alexander MacMahon who showed in
1913
Events January
* January – Joseph Stalin travels to Vienna to research his ''Marxism and the National Question''. This means that, during this month, Stalin, Hitler, Trotsky and Tito are all living in the city.
* January 3 &ndash ...
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.
:
References
*.
Permutations
{{combin-stub