|
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.
Received: 19.12.1997 Revised: 12.07.1998
Citation:
M. V. Fedyukin, “On the semigroup of transformations of a finite set generated by random generators”, Diskr. Mat., 13:2 (2001), 99–110; Discrete Math. Appl., 11:3 (2001), 291–302
Linking options:
https://www.mathnet.ru/eng/dm280https://doi.org/10.4213/dm280 https://www.mathnet.ru/eng/dm/v13/i2/p99
|
|