Метод коэффициентов и его приложения тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Давлетшин, Максим Николаевич

Оглавление диссертации кандидат физико-математических наук Давлетшин, Максим Николаевич

Глава 1. Метод коэффициентов

1.1. Метод коэффициентов Егорычева для формальных степенных рядов

1.2. Метод коэффициентов для формальных рядов Фурье

1.3. Метод коэффициентов для д-рядов

Глава 2. Приложения метода коэффициентов в алгебре

2.1. Перечисление Р-инвариантных идеалов кольца Яп(К, 7)

2.2. Число всех идеалов алгебры МТп (К) над конечным полем

Глава 3. Применение метода коэффициентов для вычисления кратных комбинаторных сумм в теории голоморфных функций и комбинаторном анализе

3.1. Вычисления кратных комбинаторных сумм в теории голоморфных функций в Сп

3.2. Пары обратимых соотношений £-типа

Рекомендованный список диссертаций по специальности «Дискретная математика и математическая кибернетика», 01.01.09 шифр ВАК

Введение диссертации (часть автореферата) на тему «Метод коэффициентов и его приложения»

Актуальность работы. Проблема вычисления и оценки комбинаторных сумм возникает в различных разделах дискретной математики и компьютерной алгебры - комбинаторном анализе, теории графов, оценке сложности алгоритмов, а также в алгебре, теории функций, и других областях математики и статистической физики. Особый интерес представляет изучение этой проблемы при решении задач перечисления в рамках комбинаторного анализа. Здесь ряд замечательных результатов принадлежит П. Ферма, Б. Паскалю, Г.В. Лейбницу, Л. Эйлеру, К.Ф. Гиндебургу, Я. Бернулли, Я. Штейнеру, К.Ф. Гауссу, К.Г.Я. Якоби, А. Мёбиусу, Дж. Сильвестру, А. Кэли, П.А. Мак-Магону, С. Рамануджану, Г. Харди, Ф. Холлу, Дж. Пойя, Н. де Брёйну, Ф. Харари, П. Эрдешу, Дж.-К. Рота, Д. Зейлбергеру и другим ученым, многие из которых сыграли также выдающуюся роль в развитии алгебры и математического анализа.

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

инциденций и функции Мёбиуса на частично упорядоченных множествах (Дж.-Я. Рота, Р. Стенли и др.) и др.

В последние годы наблюдается интенсивное развитие комбинаторного анализа, во многом связанное с применением аналитических методов при изучении комбинаторных схем. Из достижений советских ученых можно отметить, например, систематическое использование аппарата производящих функций в теории вероятностей и математической статистике, особенно в комбинаторной теории случайных процессов, задачах размещения частиц по ячейкам и случайных разбиениях, а также задачах, связанных со случайными отображениями и графами (В.Л. Гончаров, Г.И. Ивченко, В.Ф. Колчин, В.А. Малышев, Б.А. Севастьянов, В.Е. Степанов, В.П.Чистяков и др.).

Результаты вычисления комбинаторных выражений порождают соответствующие комбинаторные тождества, которые, как правило, допускают содержательное истолкование на языке перечисляемого множества объектов. Интерес к изучению комбинаторных сумм и методов их вычисления заметно повысился в последнее время. Книги Дж. Риордана, Г. Гульда, Г.П. Егорычева, Й. Кауцки, В.К. Леонтьева, Д. Зейлбергера, Ф. Флайджелета и другие целиком посвящены этой области исследования, лежащей на стыке дискретной и непрерывной математики. В этих книгах сделаны попытки систематизации огромного материала, приведена история вопроса и различные методы вычисления комбинаторных сумм и доказательств комбинаторных тождеств, включая современные методы компьютерной алгебры для проверки справедливости комбинаторных тождеств (Б. Госпер, Д. Зейлбергер, и др.).

Цель диссертационной работы

• развитие метода коэффициентов Егорычева для вычисления комбинаторных сумм на различные типы производящих функций, включая ряды Фурье и д-ряды;

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

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

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

Положения, выносимые на защиту:

1. Построение метода коэффициентов (правила вывода, лемма о полноте) для рядов Фурье обычного типа и д-рядов.

2. Нахождение комбинаторного решения и явной формулы для числа идеалов кольца Кп(К, 7).

3. Решение проблемы обращения и нахождение в явном виде формулы для числа всех идеалов определенного типа для лиевой алгебры (кольца) N (Ф,К) классического типа Ф над конечным полем К —

4. Вычисление в замкнутом виде несколько новых и известных кратных комбинаторных сумм, и нахождение нового доказательства ряда комбинаторных тождеств из теории интегральных представлений в Сп; теории групп и колец, ц-рядов и рядов Фурье.

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

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

многих комплексных переменных" (Красноярск, 2009); международная конференция "Мальцевские чтения"(Новосибирск, 2009); 3-я Российская школа-семинар "Синтаксис и семантика логических систем"(Иркутск, 2010); международная научная конференция "Алгебра и математическая логика"(Красноярск, 2010); всероссийская конференция "Алгебра, логика и методика обучения математике"(Красноярск, 2010), а также на нескольких семинарах ведущих научно-исследовательских институтов и университетов.

Публикации. По теме диссертации опубликовано 6 научных публикаций, отражающих основное содержание диссертации, включая три работы (две в соавторстве) в журналах, рекомендованных ВАК РФ. Доля авторского участия в совместных публикациях составляет 50-70%, причем доказательство основных научных положений принадлежит лично диссертанту.

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

Первая глава посвящена построению в нескольких вариантах метода коэффициентов Егорычева интегрального представления и вычисления комбинаторных сумм (правила вывода, лемма о полноте).

В первом параграфе этой главы изложен метод коэффициентов Егорычева для степенных рядов и голоморфных функций в Сп, а также несколько примеров его применения.

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

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

Вторая глава посвящена приложениям метода коэффициентов в алгебре.

В первом параграфе рассматриваются некоторые перечислительные задачи в теории идеалов кольца Яп(К, 3).

Во втором параграфе решается задача нахождения в явном виде для числа всех идеалов определенного типа для лиевой алгебры (кольца)

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

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

Второй параграф посвящен изучению пар обратимых комбинаторных соотношений.