Limit theorems for the logarithm of the order of a random $A$-mapping

A. L. Yakymiv

Diskretnaya Matematika, Tome 29 (2017) no. 1, pp. 136-155

Résumé

Let $\mathfrak S_n$ be a semigroup of mappings of a set $X$ with $n$ elements into itself, $A$ be some fixed subset of the set $N$ of natural numbers, and $V_n(A)$ be a set of mappings from $\mathfrak S_n$, with lengths of cycles belonging to $A$. The mappings from $V_n(A)$ are called $A$-mappings. We suppose that the set $A$ has an asymptotic density $\varrho>0$, and that $|k\colon k\leq n,\ k\in A,\ m-k\in A|/n\to\varrho^2$ as $n\to\infty$ uniformly over $m\in[n,Cn]$ for each constant $C>1$. A number $M(\alpha)$ of different elements in a set $\{\alpha,\ \alpha^2,\ \alpha^3,\dots\}$ is called an order of mapping $\alpha\in\mathfrak S_n$. Consider a random mapping $\sigma=\sigma_n(A)$ having uniform distribution on $V_n(A)$. In the present paper it is shown that random variable $\ln M(\sigma_n(A))$ is asymptotically normal with mean $l(n)=\sum_{k\in A(\sqrt{n})}\ln(k)/{k}$ and variance $\varrho\ln^3(n)/24$, where $A(t)=\{k\colon k\in A,\ k\leq t\},\ t>0$. For the case $A=N$ this result was proved by B. Harris in 1973.

Détail

Keywords: random $A$-mappings, order of $A$-mapping, cyclic points, contours, trees, height of random\linebreak$A$-mapping, random $A$-permutations.