
In One Line and Anywhere. Permutations as Linear Orders. 63
the major index or greater index maj(p) of p to be the sum of the descents of
p. That is, maj(p)=
i∈D(p)
i.
Example 2.16
If p = 352461, then D(p)={2, 5}, therefore maj(p)=7.
In 1916, MacMahon showed [201] the following surprising theorem by prov-
ing that the two relevant generating functions were identical. It was not until
1968 that a bijective proof was found by Dominique Foata [129], who worked
in a more general setup. Another proof that can be turned into a bijective
proof is given in Exercises 31 and 32. We present Foata’s proof in the simpli-
fied language of permutations.
THEOREM 2.17
F