The sorting index and permutation codes

DOI10.1016/J.AAM.2012.10.004MaRDI QIDQ1940422zbMATH OpenOpenAlexFDO

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

Publication date 6 March 2013

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.0503

zbMATH Keywords

bijectionCoxeter groupMahonian statisticpermutation statisticset-valued statistic

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Reflection and Coxeter groups (group-theoretic aspects) (20F55)

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,rlextrm-min)$ have the same joint distribution over the symmetric group, and asked for a combinatorial proof of this fact. In answer to the question of Petersen, 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,rlextrm-min)$ to $(sor,cyc)$. We also give a type $B$ analogue of the Foata-Han bijection, and we derive the quidistribution of $(in{v}_B,mLma{p}_B,mRmi{l}_B)$ and $(so{r}_B,mLma{p}_B,mCy{c}_B)$ over signed permutations. So we get a combinatorial interpretation of Petersen's equidistribution of $(in{v}_B,nmi{n}_B)$ and $(so{r}_B,{l_B}^{\prime })$. Moreover, we show that the six pairs of set-valued statistics $m(Cy{c}_B,Rmi{l}_B)$, $m(Cy{c}_B,Lma{p}_B)$, $m(Rmi{l}_B,Lma{p}_B)$, $m(Lma{p}_B,Rmi{l}_B)$, $m(Lma{p}_B,Cy{c}_B)$ and $m(Rmi{l}_B,Cy{c}_B)$ are equidistributed over signed permutations. For Coxeter groups of type $D$, Petersen showed that the two statistics $in{v}_D$ and $so{r}_D$ are equidistributed. We introduce two statistics $nmi{n}_D$ and $ilde{l^{\prime }}_D$ for elements of $D_n$ and we prove that the two pairs of statistics $(in{v}_D,nmi{n}_D)$ and $(so{r}_D,ilde{l^{\prime }}_D)$ are equidistributed.

Recommendations

• The sorting index
• The sorting index and equidistribution of set-valued statistics over restricted permutations
• The sorting index on colored permutations and even-signed permutations
• The sorting index and inversion number on order ideals of permutation groups
• New permutation coding and equidistribution of set-valued statistics

Cited in

(12)

• Hultman elements for the hyperoctahedral groups
• Graphical Mahonian statistics on words
• The sorting index on colored permutations and even-signed permutations
• The sorting index and equidistribution of set-valued statistics over restricted permutations
• Sorting parity encodings by reusing variables
• The sorting index and inversion number on order ideals of permutation groups
• Sorting index and Mahonian-Stirling pairs for labeled forests
• Generation, Ranking and Unranking of Permutations based on the Mixed-Radix Codes
• Indexing permutations for binary strings
• An encoding method for multifield sorting and indexing
• The sorting index
• New permutation coding and equidistribution of set-valued statistics

This page was built for publication: The sorting index and permutation codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1940422)