Cycles and sorting index for matchings and restricted permutations

2012/06/06 by Poznanovik, Svetlana
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1206.1301

Abstract

We prove that the Mahonian-Stirling pairs of permutation statistics (\sor, \cyc) and (\inv, rlmin) are equidistributed on the set of permutations that correspond to arrangements of n non-atacking rooks on a Ferrers board with n rows and n columns. The proofs are combinatorial and use bijections between matchings and Dyck paths and a new statistic, sorting index for matchings, that we define. We also prove a refinement of this equidistribution result which describes the minimal elements in the permutation cycles and the right-to-left minimum letters. Moreover, we define a sorting index for bicolored matchings and use it to show analogous equidistribution results for restricted permutations of type B_n and D_n.

Related

• The sorting index on colored permutations and even-signed permutations
• The Sorting Index and Permutation Codes
• Statistics on permutations with bounded drop size
• Combinatorial Statistics on Pattern-avoiding Permutations
• Two Vignettes On Full Rook Placements