Метод коэффициентов и его приложения

Давлетшин, Максим Николаевич

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

Давлетшин, Максим Николаевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Красноярск МЕСТО ЗАЩИТЫ

2012 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

Автореферат диссертации на тему "Метод коэффициентов и его приложения"

Давлетшин Максим Николаевич

Метод коэффициентов и его приложения

01.01.09 - дискретная математика и математическая кибернетика

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

1 2 мд?

Красноярск - 2012

005012002

Работа выполнена на кафедре математического обеспечения дискретных устройств и систем Института фундаментальной подготовки Сибирского федерального университета

Научный руководитель: доктор физико-математических наук,

профессор Егорычев Георгий Петрович

Официальные оппоненты: Лейнартас Евгений Константинович,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание работы

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

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

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

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

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

Пусть Ф - множество формальных рядов Фурье вида Г(х) = спе-тх с комплексными коэффициентами. Величина Сп называется коэффициентов Фурье функции /(х) и определяется по формуле

Два ряда А(ги) = акеШк и В {уз) = из Ф равны тогда и

только тогда, когда а^ = Ь^ для всех к. Мы можем ввести в Ф операции сложения, умножения, подстановки, обращения, дифференцирования и интегрирования.

Из определения оператора Сое}г и свойств операций над формальными рядами Фурье вытекают следующие простые свойства (правила вывода) для этого оператора.

Правило 1 (снятия).

Сое}тА (ги) е-гЫ = Сое ¡и, В (ад) е~{Ы для всех к А(т) = В{ш).

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

а СоеЛ И е~ік№ + /3 СоеиВ (гу) = Сое/і{(аА(і) + рв{і))е~ш).

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

со = | = СоеЛ[/(г)],

то есть

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

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

£ е*ыСоеМА (г) е~ік*] = Щг)]^ = А{ы).

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

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

то

£ |Сое/г[/ (2) e-lb]|2 = ||/(i)||2-

П=—DO

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

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

, п,к = 0,1,...,

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

С,(п) =

[п +1],

2 п п

, Nq (п, к) :=

п к + 1

„к+к2

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

Лемма ([3]).

п-1

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

к=0

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

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

Miin) =

d\n

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

В первом параграфе второй главы рассматриваются некоторые перечислительные задачи в теории идеалов кольца Нп(К,3), где Ип(К, 3) - кольцо всех п х п матриц над ассоциативным кольцом К с элементами из идеала 3 на К выше главной диагонали. Автоморфизмы для различных К и идеалов 3 кольца Нп(К, 3) давно привлекали внимание исследователей. Так Р. Дюбиш и С. Перлис дали однородную конструкцию идеалов алгебры МТП{К) над конечным К, где ЫТП(К) - кольцо (нижних) нильтреугольных матриц степени п над К. Позднее, В.М. Левчук описал все идеалы кольца Яп{К, 3) над произвольным полем К, и рассмотрел случай ^(К, 3) = ЫТП(К). Это позволило ему при \К\ > 2 дать комбинаторное описание всех идеалов, инвариантных относительно подгруппы Б всех диагональных автоморфизмов, а Г.П. Егорычев дал комбинаторное описание и указал, что их число равно (1/п) в случае ЯП(К,3) = МТП(К). Если коммутативное кольцо главных идеалов кольца МТП(К) есть область целостности, то каждый максимальный идеал этого кольца строго максимален. С другой стороны, если множество ПП(Я,всех £>-инвариантных идеалов кольца 11п(К, 3) (п > 2) конечно, то решетка всех идеалов кольца К тоже конечна. Число конечно тогда и только тогда, когда решетка всех идеалов

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

Г.П. Егорычев и В.М Левчук рассматривали проблему нахождения числа всех £)-инвариантов идеалов кольца Яп{К, 3) (и > 2), где К есть локальное кольцо с главным максимальным идеалом 3, который нильпотентен ступени е. В результате ими была получена формула

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

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

Теорема 4.

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

г>1 £1=0*2=0 8=г-к2-1

г—1 к\ 2г-к1-к2-2 рз-Ъг+кг+кг+Ъ , V4 /¡-1) П-г) [п~]\ ( а ^

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

кг=0кг=0 з=г—кг—1 8

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

= 22"-1

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

1 n_1 ( m=1 \

Q(m,q), (2)

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

т к

(3)

fc=0

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

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

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

В. П. Кривоколеско и А.К, Цих3 нашли интегральное представление для голоморфных функций в ограниченных линейно-выпуклых областях

2Egorychev G.P., Levchuk V.M. Enumeration in the Chevalley algebras, ACM SIGSAM Bulletin, 35, (2001), 20-34.

3Krivokolesko v., Tsikh A. Integral Representations in Linearly Convex Polyhedra, Siberian Mathematical Journal, 46(3), (2005), 579-593.

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

Лемма. Следующее тождество справедливо

SM ( к 1 = (^т^г + го)!^!

ml m\(si + s2 + 1)Г

Теорема 6. ([6]) Для dj е С; Sj 6 Z+,j = 1,2,3, то верно следующее тождество

(1 - о,

/с=0 ¡=0

1=0 1=0 *=0|=0

(s2 + 53 + 1)! А (-1Г М |7l_ S2+m+1 _ ( \52+m+1

s2!s3! ~'0s2 + rn +1 I ml \Д 1 — Qi/ \1 —

(Sl + 53 + 1)! ^ (-1Г (tSi\ ( Л _ _«з\i3+m+1 _ /_ai_\ 53+m+1\

siles! ¿£s3 + m+1 \т/ \V 1~<*J \1-<*9) )

x(l-a2)—+ « +

(Д1+ДД + 1)! v^ (-1Г M _a1_V1+m+1 _ / Ql y.+m+i\ si!s2! ¿¿si+m+1 Vmj'^V 1 - <*J \1"«зУ J

4Krivokolesko V. Integral Representations for Linearly Convex Polyhedra and Some Combinatorial Identities, Journal Siberian Federal University. Mathematics & Physics, 2(2), (2009), 176-188 .

В этом параграфе с помощью метода коэффициентов также найдено новое короткое доказательство следующего комбинаторного тождества

у/ nfcM(2n-2-fc)!z=(2n-2-i)! 4 \к) (п-1-fc)! (га — 1 — j)! '

ранее найденного A.M. Кытмановым и С.Г. Мысливец 5(Lemma 4) из теории интегральных представлений в Сп.

Второй параграф третьей главы посвящен изучению пар обратимых комбинаторных соотношений. В 1977 году Г.П. Егорычеву67 удалось впервые полностью решить трудную проблему Риордана (1968) о классификации известных пар обратных комбинаторных отношений с помощью матриц £-типа.

Определение. Бесконечная нижняя треугольная матрица С = (CmiOm.fceo^S " или что то же> типа £(ат: ft; <р, /, ф), если ее общий

член задан следующей формулой

ат

где ат) ft Ф 0 комплексные числа, и ряды <p(z), f(z), 0, ip(z) € Lq.

Г.П. Егорычевым показано, что £-матрицы образуют группу по умножению матриц.

Утверждение3.12.

а) Группа Шефера и группа Риордана изоморфны 89.

б) Группа Шефера - подгруппа Е-группы.

Конструкция £-матрицы может быть обобщена в нескольких направлениях. В диссертации рассматривается следующее возможное обобщений конструкции £ -матрицы.

Определение. Если элементы бесконечной нижней треугольной матрицы С = {Cmk} с комплексными членами могут быть представлены в

"Kytmanov, Alexander М.; Myslivets, Simona G. On Asymptotic Expansion of the Conormal Symbol of

the Singular Bochner-Martinelli Operator on the Surfaces with Singular Points. Journal of Siberian Federal

University. Mathematics Sz Physics, 1, (2008), 3-12

6Egorychev, G. P. Integral Representation and the Computation of Combinatorial Sums, Nauka,Novosibirsk, 1977 (in Russian); Transl. of Math.Monographs, Vol. 59, Amer.Math. Soc., 1984, 2nd edn in 1989 (in English).

7Egorychev G.P. Method of coefficients: an algebraic characterization and recent applications, in: Labours Waterloo Workshop on Computer Algebra, Waterloo, 5-7 May 2008, Springer Verlag, 2009, pp. 1-33.

8 He Т. X., Hsu L. C., and Shiue P. J.-S.. The Sheffer Group and the Riordan Group. Discrete Applied.

Mathematics, 155 (2007) 1895-1909.

9 Wang W., Wang Т., Generalized Riordan arrays, Discrete Mathematics (2008),

doi:10.1016/j.disc.2007.12.037

следующем виде

^=^кі /(2) Рт {*] 1к (2) г~т+к'1<1^ Г(р)

= ^-гевЛу (*) Рт (*) /* іг)

0£т

где {Рт (г)} есть последовательность весовых полиномов степени т, числа ат, Дь ф 0, / (г) - функция отображения, (0) / (0) ф О, то мы будем говорить, что матрица С является матрицей типа (ат, /3^; <р, і, Рт).

Теорема 10 (декомпозиции). Пусть щ,ір2,Ч>г & Ьо,<р = уі^г^Зі <^1(0)952(0)^3(0) ф 0, а {7т}, {А*}, - произвольные последовательности чисел, отличных от нуля. Тогда выполнимо следующее разложение

(ат, <Р,І,Рт) = ("т.7/ь; ІД.Рщ) Х (7т,/^Ь ¥>1,1, 1) х Рк] ¥>3,М)-

Автор глубоко признателен своему научному руководителю, профессору, доктору физико-математических наук Георгию Петровичу Егорычеву за постановку задач и постоянное внимание к работе.

Основные результаты

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

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

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

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

Публикации автора по теме диссертации

1. Davletshin M.N. Method of coefficients for difference operators and its some applications. // Математические системы / Красноярск: КрасГАУ, Вып. 8, 2009. - с. 13-28.

2. Davletshin M.N., Egorychev G.P. E-matrices and the approximation theory. // Математические системы / Красноярск: КрасГАУ, Вып. 8, 2009. - с. 29-39.

3. Давлетшин М.Н., Егорычев Г.П. Перечислительные проблемы в некоторых матричных кольцах и конечных группах. / / Известия Иркутского государственного университета. Математика, Т.З, №4, 2010. - с. 21-32.

4. Давлетшин М.Н. Перечисление Д-инвариантных идеалов кольца Rn(K,J). // Журнал Сибирского федерального университета. Математика и физика, Т.4, №3, 2011 - с. 10-26.

5. Davletshin M.N., Egorychev G.P., Krivokolesko V.P. About the method of coefficients for trigonometrically series. // Математика, моделирование и оптимизация сложных систем и процессов, методические аспекты преподавания математики в высшей школе: Межвузовский сборник научных трудов/ Красноярск: СибГТУ, Вып.2, 2011. - с. 3-6.

6. Davletshin M.N., Egorychev G.PKrivokolesko V.P. Calculation of multiple combinatorial sums in the theory of holomorphic functions in Cn. I/ Advances in Applied Mathematics, Vol. 48, 2012. - p. 446-456.

Подписано в печать 16.02.2012 Формат 60x84/16. Усл. печ. л. 0,8 Тираж 110 экз. Заказ 6413

Отпечатано полиграфическим центром Библиотечно-издательского комплекса Сибирского федерального университета 660041 Красноярск, пр. Свободный, 82а Тел/факс (391)206-26-58,206-26-49 E-mail: print_sfii@mail.ru; http://lib.sfu-kras.ru

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Давлетшин, Максим Николаевич, Красноярск

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО

ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ "СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ"

61 12-1/739

На правах рукописи

ДАВЛЕТШИН МАКСИМ НИКОЛАЕВИЧ

Метод коэффициентов и его приложения

01.01.09 - дискретная математика и математическая кибернетика

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель д. ф.-м. н., проф. Егорычев Георгий Петрович

Красноярск - 2012

Содержание

Введение ......................................................................3

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

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

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

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

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

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

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

К = вР{<1)..............................52

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

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

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

Литература..................................77

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,К).

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

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

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

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

Метод интегральных представлений и вычисления комбинаторных сумм (метод коэффициентов) был разработан Г. П. Егорычевым в конце 1970-х годов [4]. Основой этого метода является теория вычетов многих комплексных переменных и классический метод производящих функций (производящих интегралов), рассмотренный им впервые как метод суммирования (правила вывода, лемма о полноте) для различных классов производящих рядов. Метод позволил его автору и многим другим исследователям коротко вычислить множество известных и новых сумм различного типа по единой комбинаторной схеме (см., например, [3] и др.). В [4] Г.П. Егорычевым предложена новая обширная программа исследований, которая систематически корректировалась и дополнялась по мере её выполнения [18, 21, 22]. Так в [18] автором сформулирован следующий общий тезис к проблемам суммирования:

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

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

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

Пусть Ь — множество формальных рядов Лорана над С с конечным числом членов с отрицательными степенями. Порядок монома СкШк есть к. Степень ряда С{ю) = ]Г)к Скгик из Ь есть минимальная степень монома с ненулевым коэффициентом. Пусть - множество рядов порядка к. Ь = Ьк- Два ряда А(ии) = ^2какюк и В{™) = из Ь равны тогда

и только тогда, когда = Ък для всех к. Мы можем ввести в Ь операции сложения, умножения, подстановки, обращения и дифференцирования.

Пусть /(ги), ф (гу) <Е Ниже мы будем использовать следующие обозначения: 1г(и)) = Е 1(ии) = ии/тр^) Е Ьъ г'(ио) = ^г(ги),

к = Н (г) Е Ь\ - обратный ряд к ряду г = Н (ги) Е Для С(т) Е Ь определим формальный вычет

г е8тС(и]) = с_ 1. (1.1)

Пусть А(и)) = ак'шк ~ производящая функция для последовательности {а^}. Тогда

ак = геЪщА^и))™'1*'1, к = 0,1,.... (1.2)

Например, представление для биномиального коэффициента

^ :=ге8и;(1 + ги)пги-к-\ к = 0,1,.., п. (1.3)

Приведем несколько свойств (правила вывода) для оператора геэ, которые непосредственно следуют из определения и свойства операций с

формальными степенными рядами Лорана над С. Пусть A(w) — Ylk akWk и B(w) = Yhk^k^ - производящие функции из L. Правило 1 (снятия оператора).

гeswA(w)w~k~1 = reswB(w)w~k~l для всех к iff A(w) = B(w). (1.4)

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

areswA(w)w^1^/3reswB(w)w~k~1 = resw((aA(w)^j3B(w))w~k~1). (1.5)

Из (1.5) следует, что операторы ^ и res коммутативны.

Правило 3 (подстановки), а) Если w G (k > 1) и A(w) G L, или b) A(w) - полином и w G L, включая константу, то

]Г ^resz (A(z)z~k-1) = [AWW = (1-6)

Правило 4 (обращение). /(ги) G Lq, mo

X>fcresw {AMfWw-"-1) = [A^J/ZW^W]^, (1.7)

где 2 = h(w) = wf(w) G L\.

Правило 5 (замены переменных). Если f(w) G Lq, mo

resw (AM/M*«;-*"1) = resДА(т)/f(w)h'(w)]w=W) z'^1), (1.8)

где z — h(w) = wf(w) G Li.

Правило 6 (дифференцирования).

k reSwA^w^1 = reswA'~k. (1.9)

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

Проблема А. Пусть ряд S(w) = Yhk skwk из L представляется членами рядов A(w) = "52kakwk> B(w) = Ьктк,..., D(w) = ^2kdkWk из

L с помощью операций с формальными степенными рядами Лорана над С, то есть выражается формулой

S(w) = F(A(w), B(w),..., D(w)). (1.10)

Тогда для каждого к найти формулу

** = /(Ы,{Ь*Ь ■••»•№}), (1.И)

в которой члены последовательности {s^} есть функция от элементов последовательностей {а^} , , • • •, {dk}-

Определение. Последовательность {s^} называется

последовательностью A-типа, если она определяется по формуле (1.11).

Проблема В. Пусть члены последовательности {s^} А-типа для каждого к определяются формулой Sk = / ({а/с} > {bk} 5 • • •, {dk})-Необходимо найти формулу S(w) = F(A(w), B(w),..., D(w)) для производящих функций последовательностей {s^}, {ak} , {bk} ,■■■■> {dk}-

Определение. Система правил для оператора res называется полной, если решена проблема В.

Теорема 1 (лемма о полноте, [18]). Система правил 1-6 для оператора res с формальными рядами Лорана полна [17]. Доказательство. В [4, 17] Г.П. Егорычев использует индукцию по числу последовательности операций для функций в (1.11), порождающих заданную последовательность {s*;}. На первом шаге ряд S(w) получается с помощью рядов A(w) и B(w) из L для одной операции над формальными степенными рядами Лорана (сложения, умножения и др.). Решение рекурсивных отношений, которые соответствуют каждой из операций, рассмотрены в [4, 17, 22]. ■

Общая схема метода интегральных представлений сумм может быть разбита на следующие шаги [4]:

1. Используем таблицу интегральных представлений комбинаторных чисел. Например, биномиальный коэффициент п, к = 0,1,...,

\n.-k-1 1

= resw (1 + w)n w~

(1 + w)nw~k~1dw, q> 0, (1.12)

к J ЪH

\w\=g

ra + fc-Л ^ „ _к_г 1

= resw (1 — w) п w~

(l-w)-nw-k-1dw, О < Q < 1.

\ к J 2т

\w\=e

(1.13)

Числа Стирлинга второго рода ^(n, fc), п, к — 0,1,...([4], р. 273):

52(0,0) := 1, И

S2(n, к) = resw{(-l+expw;)ni(;"&"1} 1

2тг г

\w\=Q

(—l+exptf;)nw; к ldw, £ > 0.

(1.14)

Символ Кронекера 5{п, k), п, к = 0,1,...,

5(n,Jfe) = res^/uT^"1. (1.15)

2. Представление общего члена (сумманда) исходной суммы Xwb через сумму произведений известных комбинаторных чисел.

3. Замена комбинаторных чисел их интегралами.

4. Сведение произведения интегралов к кратному интегралу.

5. Изменение порядка суммирования и интегрирования. Это преобразование дает интегральное представление исходной суммы, ядро которого задано в виде ряда. При этом, если возможно, часто используется преобразование области интегрирования таким образом, чтобы не меняя величины интеграла, получить под знаком этого интеграла равномерно сходящийся ряд.

6. Суммирование ряда под знаком интеграла. Как правило, этим рядом оказывается (конечная или бесконечная) геометрическая прогрессия {см.

[15]). Это преобразование дает интегральное представление для исходной суммы, ядро которого задано в замкнутом виде.

7. Вычисление (асимптотика, оценки сверху и снизу, и т.д.) полученного интеграла с помощью таблиц интегралов, повторного интегрирования, теории одномерных и кратных вычетов, либо новых методов (см., например, [4], лемма о расщеплении).

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

Рассмотрим примеры применения метода коэффициентов, первые два из которых носят иллюстративный характер.

Пример 1.1. Вычислить сумму Халмоша Щ

т , ч

к=0 ^ '

Решение. Так как = resw (1 + w)n w~k~l, то в соответствии со схемой вычислений метода коэффициентов мы получаем

s = y, (-1)*res™ (i+wT =

A;=0

(правило линейности оператора res )

к=О

(формула конечной геометрической прогрессии)

= resw{(l + w)nw~l (l - (1 - (-w)-1)'1} =

(сокращение числителя и знаменателя выражения под знаком res на (1 + w))

ге8гД (1 + u;)"-1 (1 + (-1 )mw~m~l)} =

[снова правило линейности)

resw (1 + w)n-1 + (—l)mresw{(l + wf~L w~m-L} =

„,.—m—1"

по определению оператора res)

0+(-ir(n-1Wir(n-iy

\ m J \ m J

Таким образом, в результате коротких вычислений мы получили новое, прямое доказательство известного тождества Халмоша [32]

Е (-!)*(")=(-!г(П:1\ш<г,\

fc=о ^ '

Пример 1.2. Вычислить сумму Харди [4]

[т/2]

L1"-/ 1 /

м m"fcV

т — к

к\ к

?, т £ 1, сю.

Решение проводится по общей схеме вычислений метода коэффициентов. После элементарных преобразований об