Plane permutations and applications to a result of Zagier-Stanley and distances of permutations

Abstract

In this paper, we introduce plane permutations, i.e. pairs $\mathfrak{p}=(s,\pi )$ where $s$ is an $n$-cycle and $\pi$ is an arbitrary permutation, represented as a two-row array. Accordingly a plane permutation gives rise to three distinct permutations: the permutation induced by the upper horizontal ($s$), the vertical $\pi$) and the diagonal ($D_{\mathfrak{p}}$) of the array. The latter can also be viewed as the three permutations of a hypermap. In particular, a map corresponds to a plane permutation, in which the diagonal is a fixed point-free involution. We study the transposition action on plane permutations obtained by permuting their diagonal-blocks. We establish basic properties of plane permutations and study transpositions and exceedances and derive various enumerative results. In particular, we prove a recurrence for the number of plane permutations having a fixed diagonal and $k$ cycles in the vertical, generalizing Chapuy's recursion for maps filtered by the genus. As applications of this framework, we present a combinatorial proof of a result of Zagier and Stanley, on the number of $n$-cycles $\omega$, for which the product $\omega (12\cdots n)$ has exactly $k$ cycles. Furthermore, we integrate studies on the transposition and block-interchange distance of permutations as well as the reversal distance of signed permutations. Plane permutations allow us to generalize and recover various lower bounds for transposition and block-interchange distances and to connect reversals with block-interchanges.

arXiv commentTo appear in SIAM J. Discrete Math. Considering the scope of the journal, the content in arXiv:1502.07971 "A simple framework on sorting permutations" was included