Mappings of a finite set with limitations on contours and height

V. N. Sachkov

Teoriâ veroâtnostej i ee primeneniâ, Tome 17 (1972) no. 4, pp. 679-694

Résumé

Mappings $\sigma\in\mathfrak{S}^h_n(A)$ of a finite set $\mathfrak{A}$ of $n$ elements into itself are considered under the conditions that the orders of the contours of corresponding graphs $\Gamma (\mathfrak{A},\sigma)$ are elements of a set $A$ and the trees $\Gamma(\mathfrak{A},\sigma)$ have the height not exceeding $h$. The generating functions of different characteristics of such mappings as well as the exact and asymptotic number of such mappings as $n\to\infty$ are found. For the uniform distributions on $\mathfrak{S}^h_n(A)$ with $A$ finite and $n\to\infty$ the distributions of the number of cyclic elements and components in a random mapping are proved to be asymptotically normal. It is shown that the number of free trees in a random forest with the numbers of vertices in trees which are elements of a finite sequence $A$ and the number of cycles in a random solution of the equation $X^d=E$ in the symmetrical group $S_n$ are also asymptotically normal.