RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды Математического института имени В. А. Стеклова // Архив

Тр. МИАН СССР, 1986, том 177, страницы 75–104 (Mi tm2113)

Эта публикация цитируется в 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


 Англоязычная версия: Proceedings of the Steklov Institute of Mathematics, 1988, 177, 79–110

Реферативные базы данных:


© МИАН, 2024