RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды по дискретной математике // Архив

Тр. по дискр. матем., 2000, том 3, страницы 215–234 (Mi tdm45)

Эта публикация цитируется в 1 статье

Группы подстановок и полугруппы преобразований с заданным числом образующих

В. Н. Сачков


Аннотация: В статье получены рекуррентные соотношения и асимптотические формулы для вероятности транзитивности группы $G=\langle s_1,s_2,\dots,s_m\rangle$, порожденной случайными подстановками $s_1,s_2,\dots,s_m$ степени $n$ из некоторых цикловых классов, и при $n\to\infty$ найдено предельное распределение числа орбит. Для вероятности $P(n,m)$ того, что при случайном выборе $s_1,s_2,\dots,s_m$ группа $G$ совпадает с симметрической или знакопеременной, при $m\ge2$ и $n\to\infty$ получена асимптотика
$$ P(n,m)=1-\frac1{n^{m-1}}+O\biggl(\frac1{n^{2(m-1)}}\biggr). $$
Показано, что если $\mathfrak{S}_n$ – симметрическая полугруппа преобразований $n$-множества, то при случайном выборе образующих $\sigma_1,\sigma_2,\dots,\sigma_m\in\mathfrak{S}_n$, вероятность $Q(n,m)$ того, что порожденная ими полугруппа совпадает с $\mathfrak{S}_n$, удовлетворяет предельному соотношению
$$ Q(n,m)\to1-(1+\alpha)e^{-\alpha}, $$
где $mn!/n^n\to\alpha$ при $n\to\infty$.



© МИАН, 2024