Эта публикация цитируется в
1 статье
Один класс случайных отображений
И. Б. Калугин
Аннотация:
Пусть
$R$ – подмножество, содержащее ноль, множества всех целых неотрицательных чисел. Рассмотрим множество
$\mathscr A_n(R)$ однозначных отображений
$n$ элементного множества в себя таких, что кратности всех вершин деревьев отображения принимают значения только из множества
$R$, и зададим на
$\mathscr A_n(R)$ равномерное распределение вероятностей. В работе изучается асимптотическое (при
$n\to\infty$) поведение высоты и числа вершин высоты
$t$ в нижних слоях случайного отображения из
$\mathscr A_n(R)$.
Известно, что когда множество
$R$ совпадает с множеством всех целых неотрицательных чисел, т.е. на кратности вершин не наложено никаких ограничений, число циклических точек и высота случайного отображения из
$\mathscr A_n(R)$ имеют порядок
$\sqrt n$. Оказывается, что если множество
$R$ не совпадает с множествами
$\{0,1,2,3,\dots\}$,
$\{0,2,3,4,\dots\}$, то структура графа отображения
из
$\mathscr A_n(R)$ совершенно иная: отображение имеет много (порядка
$cn$, где
$c$ – фиксированное число из
$(0,1)$) циклических точек и как следствие этого малую (порядка
$\ln n$) высоту и другое распределение вершин в нижних слоях. Если же множество
$R$ есть множество всех целых неотрицательных чисел с удаленной единицей, то случайное отображение из
$\mathscr A_n(R)$ подобно случайному отображению без ограничений на кратности вершин. Библиогр. – 8 назв.
УДК:
519.212.2