The Sorting Index and Permutation Codes

William Y.C. Chen, George Z. Gong, and Jeremy J.F. Guo

  Abstract:  In the combinatorial study of the coefficients of a bivariate polynomial that generalizes both the length and the reflection length generating functions for finite Coxeter groups, Petersen introduced a new Mahonian statistic sor, called the sorting index. Petersen proved that the pairs of statistics (sor, cyc) and (inv, rl-min) have the same joint distribution over the symmetric group, and asked for a combinatorial proof of this fact. In answer to this question, we observe a connection between the sorting index and the B-code of a permutation defined by Foata and Han, and we show that the bijection of Foata and Han serves the purpose of mapping (inv, rl-min) to (sor, cyc). We also give a type B analogue of the bijection of Foata and Han, and derive the equidistribution of (invB, LmapB, RmilB) and (sorB, LmapB, CycB) over signed permutations. So we get a combinatorial interpretation of Petersen's equidistribution of (invB, nminB) and (sorB, lB'). Moreover, we show that the six pairs of set-valued statistics (CycB, RmilB), (CycB, LmapB), (RmilB, LmapB), (LmapB, RmilB), (LmapB, CycB) and (RmilB, CycB) are equidistributed over signed permutations. For Coxeter groups of type D, Petersen showed that the two statistics invD and sorD are equidistributed. We introduce two statistics nminD and for elements of Dn and we prove that the two pairs of statistics (invD, nminD) and (sorD, ) are equidistributed.

  AMS Classification:  05A05, 05A15, 20F55

  Keywords:  permutation statistic, Mahonian statistic, Coxeter group, set-valued statistic, bijection

  Download:   PDF