6533b836fe1ef96bd12a14e4

RESEARCH PRODUCT

A new Euler–Mahonian constructive bijection

subject

description

AbstractUsing 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.