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

• Давлетшин, Максим Николаевич
• кандидат физико-математических наук
• 2012

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

Содержание

Введение

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

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

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

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

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

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

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

К = вР{<1)

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

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

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

Литература

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,К).

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

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

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

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

Литература

1. Егорычев Г. П. Комбинаторное тождество из теории интегральных представлений в Сп./ / Известия Иркутского государственного университета серия "Математика Т.4, № 4, 2011. - с. 32-44.

2. Егорычев Г. П. , Левчук В. М. Перечислительные проблемы для групп и алгебр типа Ли// Докл. РАН, Т.ЗЗО, 1993. - с. 464-467.

3. Избранные задачи комбинаторного анализа / Леонтьев В. К.-Ш.: МГТУ им. Н.Э. Баумана, 2001.

4. Интегральные представления и вычисление комбинаторных сумм / Егорычев Г. П. - Новосибирск, Наука, 1977; English: Transl. of Math. Monographs 59, AMS, 1984, 2-nd Ed. in 1989.

5. Интегралы и ряды / Прудников А.П., Брычков Ю.А. Маричев О.И. - М.: Наука, 1981.

6. Комбинаторные тождества / Риордан Дж. - М.: Наука, 1982.

7. Кривоколеско В. П. Интегральные представления в линейно выпуклых полиэдрах и некоторые комбинаторные тождества// Журнал Сибирского федерального университета. Математика и физика, Т.2, № 2, 2009. - с. 176-188.

8. Левчук В. М. Подгруппы унитреугольных групп// Известия АН СССР, серия матем., Т.38, №6, 1974. - с. 1202-1220.

9. Левчук В. М. Связи унитреугольной группы с некоторыми кольцами// Алгебра и логика, Т.5, 1976. - с. 348-360.

10. Левчук В. М. , Сулейманова Г. С. Нормальное строение присоединенной группы в радикальных кольцах Rn(K,J)// Сиб. Матем. Ж., Т.43, №. 2, 2002. - с. 519-537

11. Почекутов Д.Ю. Диагонали рядов Лорана рациональных функций// Сиб. Матем. Ж., Т.50, №6, 2009. - с. 1370-1383.

12. Barry P. On integer-sequence-based constructions of generalized Pascal triangles// Journal of Integer Sequences, Vol.9, 2006. - p. 1-34.

13. Bona M., Sagan B.E. On divisibility of Narayana numbers by primes// arX-iv:math/05055382v.l [math.CO] 18 May 2005, 2005. - p. 1-5.

14. Combinatory analysis / MacMahon P.A. - Cambridge Univ. Press, 1915-1916, vol. I, II.

15. Divergent series / Hardy G.H. - Oxford: Clarendon Press, 1949.

16. Dubish R. , Perlis S. On total nilpotent algebras// Amer. J. Math., Vol.73, no.3, 1951,- p. 439-452.

17. Egorychev G.P. Algorithms of integral representation of combinatorial sums and their applications // Formal power series and algebraic combinatorics. Proc. of 12-th Intern. Conf. FPSAC'2000. - M., Russian, 2000,- p. 15-29.

18. Egorychev G.P. Method coefficients: an algebraic characterization and recent applications // Advances in combinatorial mathematics. Proceedings of the Waterloo Workshop in computer algebra 2008, devoted to the 70th birthday Georgy Egorychev, 2009. - p. 1-30.

19. Egorychev G.P. , Levchuk V.M. Enumeration in the Chevalley algebras// ACM SIGSAM Bulletin, Vol.35, 2001. - p. 20-34.

20. Egorychev G.P. , Levchuk V. M. Enumeration of characteristic subgroups of unipotent Lie-type groups // Algebra, Ed.: Yu.L. Ershov, E.I. Khukhro, V.M. Levchuk, N.D. Podufalov. - Walter de Gruyter: Berlin - New York, 1996. -p. 49-62.

21. Egorychev G.P. , Zima E. V. Decomposition and Group Theoretic Characterization of pairs of inverse relations of the Riordan type// Acta applicandae mathematicae, Vol.85, 2005. - p. 93-109.

22. Egorychev G.P. , Zima E. V. Integral representation and algorithms for closed form summation// Handbook of Algebra, Vol.5, 2008. - p. 459-529.

23. Finite operator calculus / Rota G.-C. - NY: Academic Press, 1975.

24. He T.X., Hsu L.C., Shiue P.J.-S. The Sheffer Group and the Riordan Group// Discrete Applied. Math., Vol.155, 2007. - p. 1895-1909.

25. Krattenthaler C. A new q-Lagrange formula and some applications// Proc. Amer. Math. Soc., Vol.90, 1984. - p. 338-344.

26. Krattenthaler C. Operator methods and Lagrange inversion, a unified approach to Lagrange formulas// Trans. Amer. Math. Soc., Vol.305, 1988. - p. 431-465.

27. Krattenthaler C. Advanced determinant calculus// Seminaire Lotharingien Combin, Vol.42, 1999. - p. 1-67.

28. Krivokolesko V. P. Integral representation of holomorphic functions in n-circu-lar linear convex domain with piecewise regular boundary// Математические ситемы, Вып. 10, 2011. - с. 95-107.

29. Krivokolesko V.P. , Tsikh А.К. Integral Representations in Linearly Convex Polyhedra// Сиб. Мат. Ж., T.46, №3, 2005. - с. 579-593.

30. Kuzucuoglu F. , Levchuk V. M. Ideals of some matrix rings// Commun. in Algebra, Vol.28, no.7, 2000. - p. 3503-3513.

31. Kytmanov A. M. , Myslivets S. G. On Asymptotic Expansion of the Conor-mal Symbol of the Singular Bochner-Martinelli Operator on the Surfaces with Singular Points// Журнал Сибирского федерального университета. Математика и физика, Т.1, №1, 2008. - с. 3-12.

32. Measure Theory / Halmos, P. i?.-Princeton: Van Nostrand, 1950.

33. The theory of groups / Hall, M.Jr.-NY: MacMillan, 1959.

34. Petrogradsky V. M. Growth of finitely generated polynilpotent Lie algebras and groups, generalized partitions, and functions analytic in the unit circle// Intern. J. Algebra Comput., Vol.9, 1999. - p. 179-212.

35. Shelkovich V.M. Algebra of distributions with a point singular support// ДАН СССР, T.267, №1, 1982. - с. 53-57.

36. Sprugnoli R. Riordanarrays and combinatorial sums// Discrete Math., Vol.132, 1994,- p. 267-290.

37. The Umbral Calculus / Roman S.M. - Academic Press, 1984.

38. Tolasov B.A. The number of normal subgroups of triangular group that are contained in the unitriangular subgroup// Algebra and Number Theory, Vol.2, 1977. - p. 122-126.

39. Wang W. , Wang T. Generalized Riordan arrays// Discrete Math., Vol.308, no.24, 2008. - p. 6466-6500.

40. Zeilberger D. On an Identity of Daubechies// Amer.Math. Monthly, Vol.100, 1983. - p. 487.

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

41. Davletshin M.N. Integral representation, decomposition and combinatorial identities of some classes of infinite lower triangular matrices. // Тезисы Международной конференции "Алгебра и ее приложения". Красноярск, 2007. - с. 35.

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

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

44. Давлетшип М.Н. Вычисление комбинаторных сумм в теории интегральных представлений голоморфных сумм в С3. // Тезисы международной конференции "Аналитические функции многих комплексных переменных" 12-18 августа, 2009. Красноярск, 2009. -с. 11-13.

45. Davletshin M.N., Egorychev G. P. Evaluation of the multiple combinatorial sums in a problem of enumeration of D-invariant ideals of a ring Rn{K, J) // Международная конференция "Мальцевские чтения - 2009"/ Новосибирск: ИМ СО РАН, 2009. - с. 105.

46. Davletshin M.N., Egorychev G.P., Zima E.V. Method of coefficients and its recent applications. // Синтаксис и семантика логических систем: Материалы 3-й Российской школы-семинара / Иркутск: ГОУ ВПО Восточно-Сибирская государственная академия образования , 2010. - с. 34-35.

47. Давлетшин М.Н., Егорычев Г. П. Перечисление ^-инвариантных идеалов кольца Rn{K,J). // Алгебра и математическая логика: Материалы международной конференции / Красноярск: СФУ , 2010. - с. 17-18.

48. Давлетшин М.Н., Егорычев Г.П., Левчук В.М. Комбинаторная формула для .D-инвариантных идеалов кольца Rn(K,J). // Алгебра, логика и методика обучения математике: материалы Всероссийской конференции, посвященной 100-летию со дня рождения C.JI. Эдельмана. г.Красноярск, 5-6 ноября 2010 г./ отв. ред. С.В. Ларин. Красноярск: КГПУ им. В.П. Астафьева, 2010.-е. 23-32.

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

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

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

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