Метод коэффициентов и его приложения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Защита состоится 22 марта 2012 г. в 16.00 часов на заседании диссертационного совета ДМ 212.099.18 при Сибирском федеральном университете по адресу: 660074, г. Красноярск, ул. Киренского, 26, ИКИТ СФУ, ауд. УЛК-115.

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

Автореферат разослан "Л£" 2012 года.

доктор физико-математических наук, доцент, Сибирский федеральный университет, профессор кафедры теории функций;

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

Ведущая организация: Восточно-Сибирская государственная

академия образования (г. Иркутск).

Ученый секретарь диссертационного совета

Кириллов Кирилл Анатольевич

Общая характеристика работы

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

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

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

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

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

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

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

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

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

2. Нахождение комбинаторного решения и явной формулы для числа идеалов кольца 11птА (ги) е-гЫ = Сое ¡и, В (ад) е

Правило 2 (линейности). Если а,/3 € С, то

Для Р(х) € Ф определим понятие коэффициента

ск = СоеМ/(г)е-ік*>, к= 1,2.

Правило 3 (подстановки).

Правило 6 (Парсеваля). Если f конечная функция на интервале [О, Т], то Cn — j; j-0r/(i)e_,nTttdi, nSZ, и классическое правило Парсеваля

i + I E£i(<£ + Ь1) = ||/(г)||2прикгшает eud

В третьем параграфе первой главы рассматривается метод коэффициентов для g-рядов и указывается его связь с известным умбральным исчислением Рота-Стенли. Остановимся подробнее на описании результатов этого параграфа.

Пусть q - фиксированное действительное число, q ф 0,1. ; [п]? := (qn - l)/(g - 1), g-факториал [n]?! := (1 - д)пЩ=1(1

9J), g-биномиальный коэффициент обычного типа

g-числа Каталана Сд(п), п = 0,1. и q-числа Нарайяна Nq (п, к), п = 0,1. fc = 0,1. п — 1,

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

Y,Nq(n,k) = Cq(n), п = 0,1.

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

Решение перечислительных комбинаторных проблем в алгебре проводится достаточно давно. Точкой отсчета можно считать нахождение известных нижних оценок для числа подгрупп Силова, числа упорядоченных подгрупп в конечной р-группе (Г. Фробениус, Ф. Холл, и др.), и особенно вычисление ранга факторов Мд(п) для нижнего центрального ряда свободной группы Ф с q образующими М. Hall1:

'Hall M.Jr. The theory of groups. MacMillan, NY, (1959).

кольца К тоже конечна. Обозначим через П(п) число всех множеств углов (Ь, V) степени п, а через П+(п) число всех множеств углов (Ь, Ь') степени п с г > ] для всех (г, ]) 6 Ь.

П(п, 5) = я(2п - 1) + №+(п)1. 5 > 2- (!)

В этом параграфе путем перечисления путей определенного типа на решетках найдено комбинаторное выражение для чисел П+(п), и с помощью метода коэффициентов проведено его вычисление ([4], см. ниже, Теорема 4), что позволило в (1) завершить вычисление числа П(п, й).

^ (я) = £(£ £ 2Г_Е (£) ег) (V) (^-¿и-*)х Д

г—1 к\ 2г-к1-к2-2 рз-Ъг+кг+кг+Ъ , V4 /¡-1) П-г) [п

V ) ^ 2—1 2—! 4*1/4 3 А кз > 42г-«-^-к2-2/ л

fo — ki + 1 /2s-2r+ki+kj+2\\ _

Во втором параграфе второй главы решается задача нахождения в явном виде для числа всех идеалов определенного типа для лиевой алгебры (кольца) Ы(Ф,К). В 2001 году Г.П. Егорычевым и В.М. Левчуком2 была рассмотрена проблема нахождения числа всех идеалов лиевой алгебры (кольца) N (Ф, К) классического типа Ф над конечным полем К = ^(д), и доказано следующее утверждение: если К = СР^), то число ап(Ф,д) идеалов алгебры ЫТп (К) равно

где <3(0, д) := 1, а числа <3(т,д), п = 1,2. т = 1,2. п- 1, заданы системой линейных рекуррентных соотношений вида

В этом параграфе, исходя из (2), (3), с помощью матричных обращений различного типа и метода коэффициентов найдены [3]: явная формула, интегральное представление и несколько новых соотношений (тождеств) для чисел с*„(Ф,д) и Q