Limit theorems for the joint distribution of component sizes of a~random mapping with a~known number of components

A. N. Timashov

Diskretnaya Matematika, Tome 23 (2011) no. 1, pp. 21-27

Résumé

We consider the mapping $C_{N,n}$ of a set with $n$ numbered elements into itself, which has $N\le n$ connected components and is uniformly distributed on the set of all such mappings. We denote the number of such mappings by $a(n, N)$. In addition to the known estimates we derive some new estimates of the number $a(n, N)$ under the condition that $n\to\infty$ and $N=N(n)$. Let $\eta_1,\dots,\eta_N$ be the sizes of connected components of the random mapping $C_{N,n}$, numbered in one of the $N!$ possible ways. We obtain limit theorems estimating the distribution of the random vector $(\eta_1,\dots,\eta_N)$ as $n,N\to\infty$ including the domain of large deviations. A new asymptotic estimate of the local probabilities for a sum of independent identically distributed random variables which determine the corresponding generalised allocation scheme is obtained.