Cycles and sorting index for matchings and restricted permutations
Svetlana Poznanović
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 fixed 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.
Résumé. Nous prouvons que les paires de statistiques de Mahonian-Stirling (sor, cyc) et (inv, rlmin) suivent la même distribution pour des permutations correspondant à des placements de n tours sur un tableau de Ferrer fixé avec n lignes et n colonnes. Les preuves sont combinatoires et utilisent des bijections entre les couplages et les chemins de Dyck. Nous définissons une nouvelle statistique, l'indice de tri pour les couplages. Nous prouvons également un résultat plus fin qui décrit les éléments minimaux dans les cycles des permutations et les lettres minimum droite á gauche.
Résumé. Nous prouvons que les paires de statistiques de Mahonian-Stirling (sor, cyc) et (inv, rlmin) suivent la même distribution pour des permutations correspondant à des placements de n tours sur un tableau de Ferrer fixé avec n lignes et n colonnes. Les preuves sont combinatoires et utilisent des bijections entre les couplages et les chemins de Dyck. Nous définissons une nouvelle statistique, l'indice de tri pour les couplages. Nous prouvons également un résultat plus fin qui décrit les éléments minimaux dans les cycles des permutations et les lettres minimum droite á gauche.
Full Text: PostScript PDF