Random permutations with prime lengths of cycles

A. N. Timashev

Teoriâ veroâtnostej i ee primeneniâ, Tome 61 (2016) no. 2, pp. 365-377

Résumé

A set of $n$th order permutations with prime lengths of cycles is considered. An asymptotic estimate for the number of all such permutations is obtained as $n\to\infty.$ Given a uniform distribution on the set of such permutations of order $n$, a local limit theorem is proved, evaluating the distribution of the number of cycles $\nu_n$ in a permutation selected at random. This theorem implies, in particular, that the random variable $\nu_n$ is asymptotically normal with parameters ($\log\log n$, $\log\log n$) as $n\to\infty$. It is shown that the random variable $\nu_n(p)$, the number of cycles of a fixed length $p$ in such a permutation ($p$ is a prime number), has in the limit a Poisson distribution with parameter ${1}/{p}.$ Assuming that a permutation of order $n$ is selected in accordance with the uniform distribution from the set of all such permutations with prime cycle lengths, each of which has exactly $N$ cycles $(1\le N\le[{n}/{2}]),$ limit theorems are proved, evaluating the distribution of the random variable $\mu_p(n, N),$ the number of cycles of prime length $p$ in this permutation. The results mentioned are established by means of the asymptotic law for the distribution of prime numbers and the saddle-point method as well as the generalized allocation scheme.