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

preprint2016arXivOpen access

Abstract

In this paper, we introduce plane permutations, i.e. pairs p=(s,π)\mathfrak{p}=(s,π) where ss is an nn-cycle and ππ 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 (ss), the vertical ππ) and the diagonal (DpD_{\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 kk 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 nn-cycles ωω, for which the product ω(1 2 ⋯ n)ω(1~2~\cdots ~n) has exactly kk 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.