A new Euler–Mahonian constructive bijection

详细信息    查看全文

• 作者：Vincent Vajnovszki^a ; ^{vvajnov@u-bourgogne.fr"" rel=""nofollow}
• 关键词：Permutation (bi)statistic ; Constructive bijection ; Inversion number ; Major index
• 刊名：Discrete Applied Mathematics
• 出版年：2011
• 出版时间：28 August 2011
• 年：2011
• 卷：159
• 期：14
• 页码：1453-1459
• 全文大小：331 K

文摘

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, , related to the Lehmer code, and using our new bijection we show that the bistatistic 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.