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

Teor. Veroyatnost. i Primenen., 1971 Volume 16, Issue 4, Pages 676–687 (Mi tvp2326)

This article is cited in 1 paper

The distribution of the number of fixed points corresponding to elements of a symmetric semigroup with the condition $\sigma^{h+1}=\sigma^h$, and the number of trees with the altitudes less or equal to $h$

V. N. Sačkov

Moscow

Abstract: A one-to-one correspondence is set between elements $\sigma$ of the symmetric semigroup $\sigma_n$ with the condition $\sigma^{h+1}=\sigma^h$ and graphs $\Gamma_h$ consisting of root trees with the altitudes less or equal to $h$. The number of fixed points of elements $\sigma\in\sigma_n^h$ chosen at random and the number of components of the graphs $\Gamma_h$ are shown to be asymptotically normal as $n\to\infty$. When no restriction is laid on the altitude of trees, the number of components in corresponding graphs is proved to be asymptotically (as $n\to\infty$) distributed according to Poisson law. Asymptotic formulas are derived for the number of root trees with enumerated vertices with the altitudes less or equal to $h$ and for the number of graphs composed of such trees.

Received: 24.12.1969


 English version:
Theory of Probability and its Applications, 1971, 16:4, 661–673

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025