Random Mappings with a Given Number of Cyclical Points

Abstract

In this paper, we consider a random mapping, ${\hat{T}}_n$, of the finite set $\{1,2,\dots ,n\}$ into itself for which the digraph representation ${\hat{G}}_n$ is constructed by:$(1)$ selecting a random number, ${\hat{L}}_n$, of cyclic vertices,$(2)$ constructing a uniform random forest of size $n$ with the selected cyclic vertices as roots, and $(3)$ forming `cycles’ of trees by applying a random permutation to the selected cyclic vertices.We investigate ${\hat{k}}_n$, the size of a `typical’ component of ${\hat{G}}_n$, and, under the assumption that the random permutation on the cyclical vertices is uniform, we obtain the asymptotic distribution of $k$, conditioned on ${\hat{L}}_n=m(n)$. As an application of our results, we show in Section $3$ that provided ${\hat{L}}_n$ is of order much larger than $\sqrt{n}$, then the joint distribution of the normalized order statistics of the component sizes of ${\hat{G}}_n$ converges to the Poisson-Dirichlet $(1)$ distribution as $n\to \mathrm{\infty }$. Other applications and generalizations are also discussed in Section $3$.