Арифметические задачи комбинаторики Павлов, Александр Иванович

Введение к работе

;

Актуальность- темы. Серьезная "арифметика" для коибинаторики, по-видимому, началась в 1918 году с публикации эпохальной работы Г.Харди и С.Раианудзана ї]. В этой работе исследуется асимптотика при У\-> со числа Р(п) разбиений числа ft,, на натуральные .части X_fc , )1=-1,2,... і т-el Р(Н) - число решений в натуральных числах уравнения ^^+^3.+ ,.,- Y<- . Если в наборе C^L *а.>... ) имеется y_s чисел, равных S_t JL S S 6 ^ .'« указанное уравнение можно записать так X S У = h » где V .-целое неотрицательное число. Используя равенство

I р(М2^И - П (1-2 ) \№*У, |2.|<1.

и учитывая вклад в асимптотику P(V>) только окрестности точки-2г ^ , Харди и Раиануджан получили равенство

->.

где Ж~Ту4- ,А_и=тДі.— ~ . ^из которого, в

частности следует равенство

_{р^4гг^'^Ь}

со

Работа lj знаменита теп, что в ней впервые был применен круговой иетод, открытый (изобретенный)автораии этой работы. В свое очередь круговой метод опирается на иетод производящих функций, восходящий, как известно, к Р.Лейбницу и П.Лапласу. Этот метод наряду, с другими аналитическими методами, по-видииоыу, является основный

- 4 -в комбинаторике.

Основным объектом комбинаторики является симметрическая груп- . па р степени It , т.е. мнодество всех подстановок или перестановок Vt различимых символов. Значение этой группы для комбинаторики подчеркивает высказывание Г.Вейля ([2]): "может оыть простейшей единицей в коиоинаторике является группа И. [ подстановок Уь предметов. Эта группа имеет различное строение для каздого числа h... Вопрос заключается в том, имеется ли, однако, некоторое асимптотическое единооораэие, преооладащее для больших И~ или для_# некоторого определенного класса больших 1П. . Математика все еще не дает ответа на такие вопросы".

>Тем. не.менее- в работах [з]-[б] подтвервдается "асимптотическое единообразие" в структуре группы $ при и->»о . Именно атому, в -частности, посвящена настоящая диссертационная работа.

Цель работы. І. Наяти асимптотику числа подстановок с заданным множеством длин циклов. 2. Найти аоимптотику числа решении классов уравнений в подстановках.

Общая методика исследования.- Нри реиении задачи об асимптотике числа подстановок с заданным множеством длин циклов разработан метод, подобный круговому методу Харди-литтявуда-Рамаиуджана в классической проблеме о разбиении чисел.

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

Научная новизна. Основные результаты диссертации валяются новыми."

Практическая ценность.. Работа носит теоретический' характер. Её результаты могут быть использованы в теории чисел, аналитической комбинаторике, вероятностной комбинаторике, комбинаторной тео-

- 5 -рий групп.

Аппробапия. Результаты работы докладывались на следующих семинарах и конференциях:

1. первая всесоюзная конференция "Вероятностные методы в дискретной математика!' (г.Петрозаводск, 1983г.);

2. всесоюзная конференция "Теория чисел и её' приложения" (г.Тбилиси, 1986 г.);

3. вторая всесоюзная конференция "Вероятностные методы'в дискретной математике" (г.Петрозаводск, 1988 г.);

*. международная конференция "Современные проблемы теории чисел" (г.Тула, 1993 г.);

5. семинар кафедры теории чисел в МГУ им М.В.Ломоносова (1986г.)

6. семинау профессора А.А.Карацубы по аналитической теории-чиоал в МГУ им. М. В. Ломоносова (1983-1993гг.).

Публикации. Основные результаты диссертации опубликованы в^і}-[б]работах (I из них в соавторстве), список которых приведен .в конце автореферата.

Структура и обьеи-.работ.ч. Диссертация состоит из введения, двух глав и списка литературы. Объем работы - 135 страниц, машинописного текста, список литературы содержит 39 названий.