RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2011 Volume 23, Issue 1, Pages 21–27 (Mi dm1127)

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

A. N. Timashov


Abstract: 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.

UDC: 519.24

Received: 10.06.2008

DOI: 10.4213/dm1127


 English version:
Discrete Mathematics and Applications, 2011, 21:1, 39–46

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024