Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCombinatorially refine a Zagier-Stanley result on products of permutations
86
0
0.0
(
0
)
Authors
Ricky X. F. Chen
Ask ChatGPT about the research
No Arabic abstract
In this paper, we enumerate the pairs of permutations that are long cycles and whose product has a given cycle-type. Our main result is a simple relation concerning the desired numbers for a few related cycle-types. The relation refines a formula of the number of pairs of long cycles whose product has $k$ cycles independently obtained by Zagier and Stanley relying on group characters, and was previously obtained by F{e}ray and Vassilieva by counting some colored permutations first and then relying on some algebraic computations in the ring of symmetric functions. Our approach here is simpler and combinatorial.
rate research
Read More
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 Chapuys 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(1~2~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.
In this paper, we first obtain some analogues of a formula of Zagier (1995) and Stanley (2011). For instance, we prove that the number of pairs of $n$-cycles whose product has $k$ cycles and has $m$ given elements contained in distinct cycles (or separated) is given by $$ frac{2 (n-1)! C_m(n+1,k)}{(n+m)(n+1-m)} $$ when $n-k$ is even, where $C_m(n,k)$ is the number of permutations of $n$ elements having $k$ cycles and separating $m$ given elements. As consequences, we obtain the formulas for certain separation probabilities due to Du and Stanley, answering a call of Stanley for simple combinatorial proofs. Furthermore, we obtain the expectation and variance of the number of fixed points in the product of two random $n$-cycles.
The dynamics of certain combinatorial actions and their liftings to actions at the piecewise-linear and birational level have been studied lately with an eye towards questions of periodicity, orbit structure, and invariants. One key property enjoyed by the rowmotion operator on certain finite partially-ordered sets is homomesy, where the average value of a statistic is the same for all orbits. To prove refin
We study the combinatorics of hyperplane arrangements over arbitrary fields. Specifically, we determine in which situation an arrangement and its reduction modulo a prime number have isomorphic lattices via the use of minimal strong $sigma$-Grobner bases. Moreover, we prove that the Teraos conjecture over finite fields implies the conjecture over the rationals.
In this paper we present a simple framework to study various distance problems of permutations, including the transposition and block-interchange distance of permutations as well as the reversal distance of signed permutations. These problems are very important in the study of the evolution of genomes. We give a general formulation for lower bounds of the transposition and block-interchange distance from which the existing lower bounds obtained by Bafna and Pevzner, and Christie can be easily derived. As to the reversal distance of signed permutations, we translate it into a block-interchange distance problem of permutations so that we obtain a new lower bound. Furthermore, studying distance problems via our framework motivates several interesting combinatorial problems related to product of permutations, some of which are studied in this paper as well.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
