Суммы независимых случайных величин и некоторые комбинаторные задачи тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

Московский государственный университет имени М.В.Ломоносова ' факультет вычислительной математики и кибернетики кафедра математической статистики

РГб о

1 1 MAP Wi

ь на правах рукописи

КОЛЧИН Андрей Валентинович

УЖ 519.2

стш нтшсиш случайных величин и

НЕКОТОРЫЕ ШЛБИНАТОРНЫЕ ЗАДАЧИ

01.01.05 - Теория вероятностей и математическая статистика

Автореферат

диссертации на соискание ученой•степени кандидата физико-математических наук

Москва. 1994 г.

Работа выполнена на кафедре математической статистики факультета вычислительной математики и кибернетики Московского государственного университета имени Ы.В.Ломоносова.

Научный руководитель: Официальные оппоненты:

д.ф.-н.н., профессор КРУГЛОВ В.М. д.ф.-н.н., профессор ГРУШ A.A. к.ф.-ы.н., доцент ХОХЛОВ Ю.С.

Ведущая организация:

Математический Институт имени В.А.Стеклова Российской Академии наук.

в II часов в ауд.685 2-го учебного корпуса МГУ на заседании Специализированного совета Д 053.05.36 при МГУ имени М.В.Ломоносова (119899, ГСП-З, Москва В-234, Воробьевы горы, МГУ, факультет ВМиК). "

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Автореферат разослан "_"_ 1994 г.

Защита состоится "

в

1994 г.

Ученый секретарь Специализированного совета, профессор

Трифонов Н.П.

ВВЕДЕНИЕ

Актуальность темы. В последние три десятилетия вероятностные методы занимают все большее место в исследованиях комбинаторного • характера. Если на множестве изучаемых комбинаторных объектов задать равномерное распределение, то числовые характеристики этих объектов можно рассматривать как случайные величины и применять для их изучения хорошо развитые в теории вероятностей аналитические методы.

В данной работе используется возможность представления распределений характеристик комбинаторных объектов с помощью независимых случайных величин. Изложение опирается на связь случайных комбинаторных объектов с обобщенной схемой размещения частиц, в которой распределение заполнений ячеек представимо как условное распределение независимых случайных величин при условии, что их суша принимает фиксированное значение. В диссертации этот подход применяется к изучению случайных подстановок с ограничениями на длины циклов и случайных гиперграфов. Представленные в диссертации результаты продолжают и развивают исследования этих объектов, проводимые другими методами как в нашей стране, так и за рубежом.

Внимание к рассматриваемым комбинаторным объектам, с одной стороны, является отражением общего повышения интереса к комбинаторным задачам, а с другой стороны, вызвано многочисленными применениями этих объектов в различных областях приложений математики." В связи с развитием вычислительной техники, знание свойств типичных представителей множеств I-подстановок, деревьев, отображений приобретает особо важное значение, так как они широко используются при построении и анализе вычислительных алгоритмов.

Методы исследования. При решении поставленных задач применялись методы, сводящие их изучение к обобщенной схеме размещения частиц по ячейкам, а для ее изучения - аппарат локальных предельных теорем теории вероятностей для сумм независимых одинаково распределенных слагаемых и метод характеристических функций.

з

'Цель работы заключается в изучении свойств случайных подстановок с ограничениями на длины циклов, и исследовании на основе полученных результатов асимптотического поведения числа решений уравнений ъ подстановках. Исследуется также асимптотическое поведение числа гиперлесов.

Научная новизна и практическая значимость. С помощью обобщенной схемы размещения найдено асимптотическое поведение числа подстановок степени л, длины циклов которых лежат в некотором конечном множестве Л натуральных чисел, при п-со. На основе этих результатов-изучено асимптотическое поведение числа решений уравнений в подстановках при п-*сэ. При этом для уравнений простой степени и фиксированной составной степени передоказаны ранее полученные другими методами результаты Л.Мозера и М.Вимана1', А.И.Павлова2 и Л.М.Волынец3, и для уравнения составной степени, стремящейся к бесконечности с ростом п, получен новый результат. Далее, получены новые' результаты об асимптотическом поведении распределения числа циклов в случайной подстановке степени п с ограничениями на длины циклов при п»оэ. Изучено асимптотическое поведение числа гиперлесов с заданными числами вершин и гипердеревьев при числе вершин, стремящемся к бесконечности.

Публикации и апробация работы. По теме диссертации опубликована I печатная работа. Результаты докладывались на заседании кафедры ' математической статистики факультета вычислительной математики и кибернетики Московского государственного университета.

Структура и объем работы. Диссертация состоит из введения, трех глав и списка литературы, изложенных на 89 страницах. Список литературы содержит 32 наименования.

^-L.Moser, M.Wyman. On solutions of xd=I in symmetric groups. // Canadian J. Math. - 1955. - Vol.7, P.159-168.

2A.И.Павлов. О подстановках с длинами циклов из заданного „ множества.//Теория вероятн. и ее примен.-1986.-Т.31, С.618-619.

3Л.М.Волынец. О числе решений уравнения xs=e в симметрической группе.//Матем.заметки.-1986.- Т.40, С.155-160.

СОДЕРЖАНИЕ РАБОТЫ

Во введении даются определения изучаемых объектов, постановка задач, излагается история рассматриваемых вопросов и результаты, полученные. ранее другими авторам, приводится сводка всех результатов работы.

В первой главе изучаются подстановки с ограничениями на длины циклов, именно, подстановки, длины циклов- которых принимают конечное число значений. Изучение подстановок с ограничениями на длины циклов сводится к исследованию свойств сумм независимых случайных величин. Указана связь с простейшими уравнениями, содержащими подстановки, и получена асимптотика числа решений уравнения

d

X = е,

где е - тождественная подстановка степени п, х - неизвестная подстановка, d - либо фиксированное натуральное число, либо d - оо так, что d in in n/in n -0 в общем случае или d/n - о, если d - простое число.

Подстановкой элементов данного множества из п элементов называется взаимно однозначное отображение этого множества на себя. Для пары подстановок определяется операция их умножения, которая состоит в последовательном применении этих подстановок. (Вообще говоря, при умножении подстановок не выполняется закон коммутативности.) Тогда все подстановки из п элементов образуют '"группу s , называемую ' симметрической . группой степени п. Подстановку из sn можно наглядно представить в виде ориентированного графа с п вершинами, , обладающего тем свойством, что из каждой его вершины выходит ровно одна дуга, и в каждую вершину входит ровно одна дута. Подстановка, циклически переставляющая некоторое множество элементов, а остальные элементы оставляющая на месте, называется циклом; число переставляемых элементов называется длиной цикла (в представлении в виде графа цикл представляется как контур, длина цикла подстановки есть длина этого контура).

Исследования подстановок вероятностными методами были начаты В.Л.Гончаровым в 40-х годах. Им рассмотрено множество 5п всех подстановок степени п с равномерным распределением, и для случайной подстановки • из этого множества найдены предельные распределения при п - со числа циклов фиксированной длины и общего числа циклов, а также распределение длины максимального цикла.

Рассмотрим множество вп к всех подстановок степени п, длины циклов которых лежат в некотором множестве л натуральных чисел. Интерес к изучению таких подстановок частично объясняется их связью с простейшими уравнениями, содержащими неизвестные подстановки. Например, множество всей решений уравнения

Р

X = е (1)

в симметрической группе в , где е - тождественная подстановка, ар- простое число, совпадает с множеством где к=(1,р}.

Если й - составное число и 1=сг0<^<.. .«гг=а - все различные делители числа а, то подстановка х является решением уравнения

<1

X = е (2)

тогда и только тогда, когда длины циклов х принадлежат множеству л={сг0«г;1<.. .<аг).

Изучение числа решений уравнения (г) можно свести к исследованию сумм независимых случайных величин.

Обозначим число решений уравнения (2), и пусть а„ „ -

П г^t а

число элементов множества 5„ Асимптотика чисел а „

П, А П, 1\

изучалась многими авторами: Ю.В.Болотниковым, В.Н.Сачковым и В.Е.Таракановым, Л.М.Волынец, А.А.Груш, А.И.Павловым, Ю.Л.Павловым, А.Л.Якымивым, Л.Мозером и М.Виманом. Использовались метод перевала и метод тауберовых теорем.

Пусть на н задано равномерное распределение и д -число циклов в случайной подстановке из этого множества. Введем независимые одинаково распределенные случайные величины с распределением

б

к В(х)

л-.-..

где

3(х) = ) — . ; к к€Я

С помощью этих случайных величин можно записать, что

Ш (В(х))'

Я! хп а

п, к

Суммируя последнее соотношение по я, находим, что

2 у. *

хП

К=Х

Таким образом, для нахождения асимптотики чисел ап я достаточно выбрать подходящее значение параметра х и получить локальную теорему для суммы независимых одинакозо распределенных случайных величин с указанным выше распределением. С использованием этого подхода в первой глазе доказаны следующие утверждения.

Теореиа 1.2.1. Если, п-га и ¡*={1,2), то

П/2

е п (1+о(1)).

Теорема 1.2.2. Если п~<л и к={ !,<!}, где ¿»з фиксировано, тс

1

„ - — е п. Я ^

(Х+о(1)).

Теорема 1.3.1. Если ггы и к={1,с!>, где так, что

по

п(1-1/й) 03 Х/А ,

Г-; ~ (п ( 1+Й/П) )

-1с1 -7Г-7ГГ-.- -1-о{1)),

к=о

(пн-к<1):

гЗе а=п-<2[п/3] - остаток от деления п не й. В частности, если сГ2п1/(*-><», тс

n, R -

а если сГ-'-п^-о, то

n(i-i/d)

d-i/2 еп J (1+о(1))(

1n(l_l/d) m/d

а

л, К

пш/ (l+d/n)

Если d=p - простое число, то r*d)=an где R=[itp), и

теоремы 1.2Л, 1.2.2 и 1.3.I дают асимптотику числа решений уравнения (I).

Основным результатом первой главы является, следующее утверждение.

Теорема 1.4.1. Если п~а> и четные d ленятся таким образом, что d in in п/in n - о, по

(l+o(l)),

r<d> = a

n-n/d JL exp1

•id

Jld

(l+o(l))

где суммирование проводится по всел различным делителям числа d.

Во второй главе на основании формулы (3) и результатов первой главы получены асимптотические выражения для распределения числа -циклов у „ в случайной подстановке с

Х1> А

ограничениями я на'длины циклов.

Теорема 2.2.1. Если пчя и к={1,2), то

ехр

2 (N-B)'

(1+о(Х))

равномерно относительно целых N, для которых

N-B

лежит в любом конечном интервале, где

п -Гп В = - + — . 2 2

Теорема 2.2.2. Если п*™ и Л=(1,с1), где ¿>з фиксировано, то

п-и

£¡-1

= к

¡¡яп^5

ехр-

(М-п-п1^)2

2П

г/л

(1+о(1))

равномерно относительно.целых к, для которых

„1/(2(1)

лежит, в любол конечном интервале.

Теорема 2.2.3. Если я={1,<*} и п,<г-*т шк, что с2/п~о, то

,ан-кй

+т+к(<г-1)

(т+кД); 00

(1+о(1))

равнолерно относительно целых

к «

1/3

(лн^)!

гйе т=п-<1[п/<1]- остаток от деления п на а и.

\ = п1^

сг

1 + -п

Теорема 2.2.4. Яусть п-оо и яис^,^,...,«^}, где ¿0=1, с1х=2, <1г=с1, и (¡0,с11,... ,<хг - все различные делители кисла <г. '' Если

Й 1п 1п п 1п п

- о,

то

Я

ехр

К

(1+о(1))

равномерно относительно целых к, для которых

-Г5(У-В)

п1'4

лежит в любол конечном интервале, где

гг

п

3 = - +

J м

- I л*

и. сулшрование проводится по всея различным делителял числа й.

Пусть задано некоторое множество у и семейство его различных подмножеств £=<£,...,£г). -Пару (Р,£) называют гиперграфом, при этом V - множество вершин, . £ - множество ребер. Если 1^1=2, 1=1,...,г, то понятие гиперграфа совпадает с хорошо .известным .понятием графа. Гипердеревом называется, связный гиперграф без циклов. Гипердерево называется ш-деревом,■ если- каждое его ребро содержит и вершин. Гиперграф, все компоненты .связности'которого являются п-деревьями, называется о-лесом. •

В третьей главе рассматриваются ш-леса с п занумерованными вершинами, состоящие из и гипердеревьев. Обозначим г число ребер в таком гиперлесе. Нетрудно видеть, что в и-лесе с я деревьями п = Г(и-1> '+ и. Обозначим множество всех таких,

лесов,' и пусть = - число элементов в ' этом

Пр П Т1, п

множестве. '

При ®=2 множество представляет собой множество лесов из N некорневых деревьев с п занумерованными вершинами.

-Случайные леса из этого множества с равномерным распределением подробно изучены.

Для произвольного ш»2 точная .формула для числа' ш-лесов получена Б.И.Селивановым4:

, Т-к

р(») _ (Г(д-1)+У)1 - , т-к

п,К ~ т ^ (_1>

1/» / / ~ \ I \ .

N

Т-к

К-1

( (Ш-Х> ! к=0

х ( '(Т-к) (гв-1)+//).

К1

д-1

4Б.И.Селиванов. Перечисление однородных гипергг цикловой структурой.// Комбинаторный анализ.-!"

эв с простой С.60-67.

Введем производящую функцию

" (г(т-1)+1)г~2 хг(»-1>+1

Vх' = I -;--<4>

г=0 г! ((й-1)!)

Заметим, что радиус сходимости ряда Бт(х) равен ((га-2)! е-1)1/(и-1).

В третьей главе анализ ш-лесов сводится к исследованию сумм независимых случайных величин.

Введем независимые одинаково распределенные случайные величины ,...,с^ с распределением

(г(П-1)+1)г"2

Р{С1=г(ш-1)+1) = - , г=о,1,...,

г! ((и-1)!)г Вл(*)

где нормирующая функция вт(х) определена формулой (4) и положительный параметр х может быть выбран произвольно из области сходимости ряда (4).

В третьей главе показано, что

Ш (Ви(х))" п,Н Н1 хП 1 N

где х - любое положительное число из области сходимости ряда

Таким образом, для того, чтобы найти асимптотику достаточно выбрать подходящее значение параметра х и доказать локальную предельную теорему для суммы независимых одинаково распределенных случайных величин с указанным выше распределением.

Доказав соответствующую локальную теорему, мы получаем следующий результат.

Теорема 3.2.2. Пусть т фиксировано и так, что

1/(П-1)

А =

и! 7

п

лежит в произвольном интервале вида

и

О < \0 « Я € < ((Ш-2)П1/(Ш-1),

- 7

Тогда

где \Q и - постоянные

„тТ

FC) = _И

п,Ы т

(.ml)1 Т!

m(m-l)T

1 - —-— (1+о(1))

равномерно относительно л в интервале [А0, я1].

Заметим, что при ш=2 эта теорема доказана В.Е.Бритиковым5.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Колчин А.В. Уравнения, содержащие неизвестную подстановку. // Дискретная математика. - 1994. - Т.6, JH, С.69-84.

2. Kolchin A.V. Equations in unknown permutations. // Discrete Mathematics and Applications. - 1994. - V.4, No.l, P.61-74.

5В.Е.Бритиков. Асимптотика числа лесов из некорневых деревьев. // Матем.заметки.-1988.-Т.43, С.387-394.

__Тир ^ОО Зак._Л__

Предприятие «ПАТЕНТ». Москва, Г-59, Бережковская наб., 24