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

Diskr. Mat., 2001 Volume 13, Issue 2, Pages 99–110 (Mi dm280)

On the semigroup of transformations of a finite set generated by random generators

M. V. Fedyukin


Abstract: We consider the semigroup generated by random mappings and random bijective mappings of a finite set $\Omega_n$ of cardinality $n$ into itself. We study the question when this semigroup includes all mappings of $\Omega_n$ into itself with a fixed cardinality $k$ of the image of the set $\Omega_n$. As $n\to\infty$, the ranges of $k$ are given where this inclusion holds with probability tending to zero or one, and two domains of values of $k$ where the inclusion holds with intermediate probability.

UDC: 519.2

Received: 19.12.1997
Revised: 12.07.1998

DOI: 10.4213/dm280


 English version:
Discrete Mathematics and Applications, 2001, 11:3, 291–302

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024