A new Euler–Mahonian constructive bijection

Using generating functions, MacMahon proved in 1916 the remarkable fact that the major index has the same distribution as the inversion number for multiset permutations, and in 1968 Foata gave a constructive bijection proving MacMahon’s result. Since then, many refinements have been derived, consisting of adding new constraints or new statistics.Here we give a new simple constructive bijection between the set of permutations with a given number of inversions and those with a given major index. We introduce a new statistic, mix, related to the Lehmer code, and using our new bijection we show that the bistatistic (mix,INV) is Euler–Mahonian. Finally, we introduce the McMahon code for permutations which is the major-index counterpart of the Lehmer code and show that the two codes are related by a simple relation.

► We give a simple bijection between permutations with a given number of inversions and a given major index. ► A new statistic, mix, is introduced. ► We show that the bistatistic (mix,INV) is Euler–Mahonian. ► We introduce a McMahon code for permutations. ► This code is simply related to the Lehmer code.