Эта публикация цитируется в
6 статьях
О числе компонент случайного $A$-отображения
А. Л. Якымив Математический институт им. В. А. Стеклова РАН
Аннотация:
Пусть
$\mathfrak{S}_n$ — полугруппа отображений множества из
$n$ элементов в себя,
$A$ — некоторое фиксированное подмножество множества натуральных чисел
${\mathbf N},\ V_n(A)$ — множество отображений из
$\mathfrak{S}_n$, размеры контуров которых принадлежат множеству
$A$. Отображения из
$V_n(A)$ принято называть
$A$-отображениями. Рассмотрим случайное отображение
$\sigma_n$, равномерно распределенное на
$V_n(A)$. Предполагается, что множество
$A$ имеет асимптотическую плотность
$\varrho>0$. Пусть
$\nu_n$ — число компонент связности случайного отображения
$\sigma_n$. В настоящей статье показано, что случайная величина
$\nu_n$ асимптотически нормальна со средним
$a(n)=\sum_{k\in A(\sqrt{n})}1/{k}$ и дисперсией
$\varrho\ln(n)/2$, где
$A(t)=\{k: k\in A,\ k\leq t\}$.
Ключевые слова:
случайные $A$-отображения, случайные $A$-подстановки, циклические точки, контуры, деревья, компоненты случайных отображений, тауберова лемма. Поступила в редакцию: 28.03.2011
Исправленный вариант: 10.11.2013
DOI:
10.4213/tvp4551