RUS  ENG
Full version
JOURNALS // Teoriya Veroyatnostei i ee Primeneniya // Archive

Teor. Veroyatnost. i Primenen., 1972 Volume 17, Issue 4, Pages 679–694 (Mi tvp4341)

This article is cited in 23 papers

Mappings of a finite set with limitations on contours and height

V. N. Sachkov

Moscow

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

Received: 24.12.1970


 English version:
Theory of Probability and its Applications, 1973, 17:4, 640–656

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025