A new EulerMahonian 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 MacMahons 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 EulerMahonian. 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.
constructive bijection major index inversion number permutation (bi)statistic