On permutations with cycle lengths from a random set

A. L. Yakymiv

Diskretnaya Matematika, Tome 12 (2000) no. 4, pp. 53-62

Résumé

Let $\xi_1,\dots,\xi_n,\dots $ be a sequence of independent Bernoulli random variables which take the value 1 with probability $\sigma\in (0,1]$. Given this sequence, we construct the random set $A\subseteq\mathbf N=\{1,2,3,\dots\}$ as follows: a number $n\in\mathbf N$ is included in $A$ if and only if $\xi_n=1$. Let $T_n=T_n(A)$ denote the set of the permutations of degree $n$ whose cycle lengths belong to the set $A$. In this paper, we find the asymptotic behaviour of the number of elements of the set $T_n(A)$ as $n\to\infty$. For any fixed $A$, the uniform distribution is defined on $T_n(A)$. Under these hypotheses, limit theorems are obtained for the total number of cycles and the number of cycles of a fixed length in a random permutation in $T_n(A)$. Similar problems were earlier solved for various classes of deterministic sets $A$. This research was supported by the Russian Foundation for Basic Research, grants 00–15–96136 and 00–01–00090.