On plane permutations

arXiv1411.5552MaRDI QIDQ6256597

Ricky X. F. Chen, Christian M. Reidys

Publication date: 20 November 2014

Abstract: In this paper we generalize permutations to plane permutations. We employ this framework to derive a combinatorial proof of a result of Zagier and Stanley, that enumerates the number of $n$-cycles $omega$, for which $omega(12cdotsn)$ has exactly $k$ cycles. This quantity is $0$, if $n-k$ is odd and $frac2C(n+1,k)n(n+1)$, otherwise, where $C(n,k)$ is the unsigned Stirling number of the first kind. The proof is facilitated by a natural transposition action on plane permutations which gives rise to various recurrences. Furthermore we study several distance problems of permutations. It turns out that plane permutations allow to study transposition and block-interchange distance of permutations as well as the reversal distance of signed permutations. Novel connections between these different distance problems are established via plane permutations.

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) General biology and biomathematics (92B05)

This page was built for publication: On plane permutations

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