The asymptotic of the number of permutations whose cycle lengths are prime numbers

2022/04/15 by Ljuben Mutafchiev, Mutafchiev, Ljuben
Computer Science · Mathematics · #05A05 #05A16 #11A41 #11Y55 #Advanced Mathematical Identities #Analytic Number Theory Research #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.2204.07361

openalex publication_date 2022/04/15 · openalex created_date 2022/04/19 · openalex updated_date 2026/07/28

Abstract

Let A be a set of natural numbers and let S_n,A be the set of all permutations of [n]=\1,2,...,n\ with cycle lengths belonging to A. Furthermore, let | A(n)| denote the cardinality of the set A(n)=A∩ [n]. The limit ρ=lim_n→∞| A(n)|/n (if it exists) is called the density of set A. It turns out that, as n→∞, the cardinality | S_n,A| of the set S_n,A essentially depends on ρ. The case ρ>0 was studied by several authors under certain additional conditions on A. In 1999, Kolchin noticed that there is a lack studies on classes of permutations for which ρ=0. In this context, he also proposed investigations on certain particular cases. In this paper, we consider the permutations whose cycle lengths are prime numbers, that is, we assume that A=P, where P denotes the set of all primes. For this class of permutations, the Prime Number Theorem implies that ρ=0. In this paper, we show that, as n→∞, the ratio S_n,P/(n-1)! approaches a finite limit and determine its value explicitly. Our method of proof employs classical Tauberian theorems.

Related

• A Note on the Number of Permutations whose Cycle Lengths Are Prime\n Numbers
• Almost all permutations power to a cycle of prime length
• Counting pairs of cycles whose product is a permutation with restricted cycle lengths
• Cycles of random permutations with restricted cycle lengths
• Asymptotic analysis of the cyclic structure of permutations