Counting pairs of cycles whose product is a permutation with restricted cycle lengths

2024/07/13 by Miklós Bóna, Bona, Miklos, Boris Pittel +1
Computer Science · Engineering · #05E10 #60C05 #Bayesian Methods and Mixture Models #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2407.10024

openalex publication_date 2024/07/13 · openalex created_date 2024/07/17 · openalex updated_date 2026/07/28

Abstract

We find exact and asymptotic formulas for the number of pairs (p,q) of N-cycles such that the all cycles of the product p⋅ q have lengths from a given integer set. We then apply these results to prove a surprisingly high lower bound for the number of permutations whose block transposition distance from the identity is at least (n+1)/2.

Related

• On plane permutations
• The Number of k-Cycles In a Family of Restricted Permutations
• Adjacent q-cycles in permutations
• Two Enumerative Results on Cycles of Permutations
• Permutations, cycles, and the pattern 2-13