A Note on the Number of Permutations whose Cycle Lengths Are Prime Numbers

• Published in: arXiv.org 2021-10
• Main Author: Mutafchiev, Ljuben
• Format: Article
• Language: English
• Subjects: Asymptotic properties; Density; Number theory; Permutations; Prime numbers; Theorems
• ISSN: 2331-8422

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\). For \(A(n)=A\cap [n]\), the limit \(\rho=\lim_{n\to\infty}\mid A(n)\mid/n\) (if it esists) is usually called the density of set \(A\). (Here \(\mid B\mid\) stands for the cardinality of the set \(B\).) Several studies show that the asymptotic behavior of the cardinality \(\mid S_{n,A}\mid\), as \(n\to\infty\), depends on the density \(\rho\). It turns out that the asumption \(\rho>0\) plays an essential role in the asymptotic analysis of \(\mid S_{n,A}\mid\). Kolchin (1999) noticed that there is a lack of studies on classes of permutations satisfying \(\rho=0\) and proposed investigations on certain particular cases. In this note, we consider the permutations whose cycle lengths are prime numbers, that is, we assume that \(A=\mathcal{P}\), where \(\mathcal{P}\) denotes the set of all primes. From the Prime Number Theorem it follows that \(\rho=0\) for this class of permutations. We deduce an asymptotic formula for the summatory function \(\sum_{k\le n}\mid S_{k,\mathcal{P}}\mid/k!\) as \(n\to\infty\). In our proof we employ the classical Hardy-Littlewood-Karamata Tauberian theorem.