Введение к работе
Актуальность темы. В последние три десятилетия вероятностные методы занимают все большее место в исследованиях комбинаторного характера. Если на множестве изучаемых комбинаторных объектов задать равномерное распределение, то числовые характеристики этих объектов можно рассматривать как случайные величины и применять для их изучения хорошо развитые в теории вероятностей аналитические методы.
В данной работе используется возможность представления распределений характеристик комбинаторных объектов с помощью независимых случайных величин. Изложение опирается на связь случайных комбинаторных объектов с обобщенной схемой размещения частиц, в которой распределение заполнений ячеек представимо как условное распределение независимых случайных величин при условии, что их сумма принимает фиксированное значение. В диссертации этот подход применяется к изучению случайных подстановок с ограничениями на длины циклов и случайных гиперграфов. Представленные в диссертации результаты продолжают и развивают исследования этих объектов, проводимые другими методами как в нашей стране, так и за рубежом.
Внимание к рассматриваемым комбинаторным объектам, с одной стороны, является отражением общего повышения интереса к комбинаторным задачам, а с другой стороны, вызвано многочисленными применениями этих объектов в различных областях приложений математики." В связи с развитием вычислительной техники, знание свойств типичных представителей множеств < подстановок, деревьев, отображений приобретает особо важное значение, так как они широко используются при построении и анализе вычислительных алгоритмов.
Методы исследования. При решении поставленных задач применялись методы, сводящие их изучение к обобщенной схеме размещения частиц по ячейкам, а для ее изучения - аппарат локальных предельных теорем теории вероятностей для сумм независимых одинаково распределенных слагаемых и метод характеристических функций.
'Цель работы заключается в изучении свойств случайных подстановок с ограничениями на длины циклов, и исследовании на основе полученных результатов асимптотического поведения числа решений уравнений ь подстановках. Исследуется также асимптотическое поведение числа гиперлесов.
Научная новизна и практическая значимость. С помощью обобщенной схемы размещения найдено асимптотическое поведение числа подстановок степени л, длины циклов которых лежат в некотором конечном множестве R натуральных чисел, при п-со. На основе этих результатов-изучено асимптотическое поведение числа решений уравнений в подстановках при n~to. При этом для уравнений простой степени и фиксированной составнбй степени передоказаны ранее полученные другими методами результаты Л.Мозера и М.Вимана1', А.И.Павлова2 и Л.М.Волынец3, и для уравнения составной степени, стремящейся к бесконечности с ростом п, получен новый результат. Далее, получены новые' результаты об асимптотическом поведении распределения числа циклов в случайной подстановке степени п с ограничениями на длины циклов при п»га. Изучено асимптотическое поведение числа гиперлесов с заданными числами вершин и гипердеревьев при числе вершин, стремящемся к бесконечности.
Публикации и апробация работы. По теме диссертации опубликована I печатная работа. Результаты докладывались на заседании кафедры ' математической статистики факультета вычислительной математики и кибернетики Московского государственного университета.
Структура и объем работы. Диссертация состоит из введения, трех глав и списка литературы, изложенных на 89 страницах. Список литературы содержит 32 наименования.
^-L.Moser, M.Wyman. On solutions of x =1 in symmetric groups. // Canadian J. Math. - 1955. - Vol.7, P.159-168.
2A.И.Павлов. О подстановках с длинами циклов из заданного .. множества.//Теория вероятн. и ее примен.-І986.-Т.ЗІ, С.618-619.
3Л.М.Волынец. О числе решений уравнения xs=e в симметрической группе.//Матем.заметки.-1986.- т.40, С. 155-160.
