Комбинаторные полиномы разбиений и их приложения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение.

Глава 1. Комбинаторные числа.

1.1. Некоторые известные комбинаторные числа.

1.2. Построение комбинаторных чисел.

1.3. Числа Стирлинга, JIaxa и некоторые другие.

Глава 2. Комбинаторные полиномы разбиений одной последовательности переменных.

2.1. А- и В-полиномы.

2.2. Расщепленные А-полиномы.

2.3. Цикловые индикаторы симметрических групп.

2.4. Обобщенные А- и В-полиномы.

2.5. Многомерные полиномы разбиений.

Глава 3. Комбинаторные полиномы разбиений двух последовательностей переменных.

3.1. Т-полиномы Тушара.

3.2. Р-полиномы.

3.3. С-полиномы Тушара.

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

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

Понятие «полином разбиений» - полином от нескольких переменных, определяемый с помощью суммы по различным разбиениям значений его индексов - введено Беллом в [36]. Один из таких полиномов

Уп(1'->У\->'"->Уп), связанный с производными от композиции функций, Риордан в книге [29, с. 46] назвал полиномом Белла. Свойства коэффициентов п - го полинома Белла - так называемых однородных или частичных полиномов Белла Апк (х) изучались в работах

25],[27],[5],[11]. Сопряженные с ними полиномы Платонова Впк{рс) были введены в [25] и изучались в работах [5], [6], [8], [9], [33].

Обобщенными А- и В-полиномами А^тк(х) и соответственно в

6] названы обобщения А-полиномов, которые имеются, например, в [42], [45], и обобщения В-полиномов, введенные в [33]. Ряд свойств обобщенных А- и В-полиномов установлен в [6, 10, 33, 42, 45].

В связи с изучением некоторых циклических подстановок Тушар [53] ввел ряд обобщений полиномов Белла. Для одного из таких обобщений Т„к{х>У)> названшп> полиномами Тушара, в [40] получены экспоненциальные производящие функции и рекуррентные соотношения. В работе [39] рассматриваются свойства некоторых частных случаев полиномов Тпк (х,у) и вновь введенных полиномов Тушара Ctlk(x,y).

Полученные формулы используются при нахождении некоторых вероятностей в задаче флуктуации случайных блужданий. Отдельные свойства полиномов Тушара приводятся в [13], [16]. Полиномы Рп к (х, у), алгебраически и аналитически обратные полиномам Тпк(х,у), строятся в

14] и изучаются в [15].

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

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

Научная новизна. Основные результаты работы являются новыми: введены и изучены новые комбинаторные Р-полиномы, которые являются обобщениями известных комбинаторных объектов, построены алгоритмы взаимных преобразований комбинаторных Т- и Р- полиномов, при помощи С-полиномов объектов описана одноканальная система массового обслуживания.

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

Апробация. Результаты, приведенные в диссертации, докладывались на научно-технической конференции «Студент и научно-технический прогресс: Молодые ученые к 80-летию ИГУ» (Иркутск, 1998 г.), на Всероссийском научно-практическом молодежном симпозиуме «Экология Байкала и Прибайкалья» (Иркутск, 1998 г.), на Восточно-Сибирской зональной межвузовской конференции по математике и проблемам преподавания ее в вузе (Иркутск, 1999 г.), на конференции «Математика и ее приложения», посвященной памяти профессора А.И.Кокорина и 275-летию РАН (Иркутск, 1999 г.), на седьмом международном семинаре «Дискретная математика и ее приложения» (Москва, 2001 г.), на 12 Байкальской международной конференции «Методы оптимизации и их приложения» (Иркутск, Байкал, 2001 г.), на семинарах кафедры математической статистики и теории вероятностей ИГУ, на ежегодных научно-практических конференциях ИГЭА (1996-2001).

Результаты диссертации использованы в монографии [12].

Содержание работы. В параграфах 1-3 первой главы, носящей преимущественно реферативный характер, приводится описание известных комбинаторных объектов, которые используются в дальнейшем при исследованиях, приводимых во 2 и 3 главах.

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

Во втором параграфе приводится общая схема построения комбинаторных чисел в пространстве отображений, взятая из работы [27].

В третьем параграфе рассматриваются комбинаторные числа Стерлинга 1 и 2 рода, числа Лаха и некоторые другие комбинаторные объекты; устанавливается новая взаимосвязь между обобщенными числами Стерлинга и производящими функциями разбиений. Обсуждаются некоторые перечислительные интерпретации описанных комбинаторных объектов.

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

В первом параграфе приводится построение комбинаторных А- и В-полиномов в общей схеме построения комбинаторных чисел, когда в качестве элементов матрицы весов принимаются функции; приводятся производящие функции, рекуррентные формулы, справедливые для А- и В-полиномов. Для А-полиномов доказывается ряд рекуррентных соотношений [21]. Рассматриваются коэффициенты А- и В-полиномов, для которых получены рекуррентные соотношения, обсуждаются перечислительные интерпретации [18].

Во втором параграфе изучаются так называемые «расщепленные» А-полиномы, для них получена производящая функция и рекуррентное соотношение [21].

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

В четвертом параграфе рассматриваются обобщенные А- и В-полиномы, получены рекуррентные соотношения для коэффициентов этих полиномов. Обсуждаются перечислительные интерпретации изучаемых комбинаторных объектов [18].

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

В первом параграфе рассматриваются классические полиномы Тушара, которые названы Т-полиномами Тушара. Для этих полиномов найдены новые рекуррентные соотношения [13], [16], формулы, связывающие Т-полиномы Тушара с другими полиномами, предложена новая перечислительная интерпретация [16].

Во втором параграфе вводятся новые, более сложные Р-полиномы, которые составляют с Т-полиномами Тушара квазиортогональную систему. Установлена аналитическая сопряженность Т-полиномов Тушара и Р-полиномов. Для построенных полиномов найдены формула явного вида, производящая функция и различные рекуррентные соотношения. Предложен алгоритм преобразования Т-полиномов Тушара в Р-полиномы и ему обратный [15].

В третьем параграфе рассматриваются С-полиномы Тушара, введенные в работе [39], которые отличаются от классических полиномов Тушара способом разбиения индексов. Для С-полиномов Тушара найдены формула явного вида, производящая функция, различные рекуррентные соотношения. В качестве приложения предложено описание одноканальной системы массового обслуживания [18].

Основные результаты диссертации опубликованы в работах [13]

21].

1. Айгнер М. Комбинаторная теория. М.: Мир, 1982.

2. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. 2-е изд. М.: Наука, 1987.

3. Докин В.Н., Жуков В.Д., Колокольникова Н.А., Кузьмин О.В., Платонов M.JI. Комбинаторные числа и полиномы в моделях дискретных распределений. Иркутск: Изд-во Иркут. ун-та, 1990.

4. Егорычев Г.П. Интегральное представление и вычисление комбинаторных сумм. Новосибирск: наука, 1977.

5. Жуков В.Д. Производящий определитель // Асимптотические и перечислительные задачи комбинаторного анализа . Красноярск: изд-во Краснояр. Гос. Ун-та, 1976,- С. 47 58.

6. Жуков В.Д. Рекуррентные формулы для обобщенных А- и В-полиномов // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1983. Вып.66. С. 192 197.

7. Жуков В.Д. О связи В-полиномов с коэффициентами разложения операторов Ли // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1990. Вып.91. С. 220 223.

8. Кузьмин О.В. Взаимные преобразования некоторых полиномов разбиений // Алгоритмические и комбинаторные задачи дискретных систем и ЭВМ. Иркутск, Иркут. ун-т, 1990, с. 71 79.

9. Кузьмин О.В. Новые рекуррентные соотношения для полиномов разбиений // Алгоритм, и комбинат, задачи дискр. систем и ЭВМ. Иркутск: Иркут. ун-т, 1991, С. 74 82.

10. Кузьмин О.В. Обобщенные пирамиды Паскаля и их приложения. Новосибирск: Наука, 2000.

11. Кузьмин О.В., Леонова О.В. О полиномах Тушара. // Асимптотические и перечислительные задачи комбинаторного анализа.-Иркутск: Иркут. ун-т, 1997.-С. 101 -109.

12. Кузьмин О.В., Леонова О.В. О некоторых свойствах полиномов разбиений // Труды Восточно-Сибирской зональной межвузовскойконференции по математике и проблемам ее преподавания в вузе. -Иркутск: Изд-во Иркут. гос. Пед. Ун-та, 1999. С. 158 - 159.

13. Кузьмин О.В., Леонова О.В. Полиномы Тушара и им квазиортогональные.// Оптимизация, управление, интеллект. Вып. З.Иркутск, 1999,- С. 218 227.

14. Кузьмин О.В., Леонова О.В. Полиномы Тушара и их приложения.-Иркутский университет. // Дискретная математика. Том 12. Вып. 3,2000. С. 60-71.

15. Кузьмин О.В., Леонова О.В. Некоторые свойства полиномов Тушара // Труды 7-го международного семинара «Дискретная математика и ее приложения». Ч.Ш. Изд-во мат.- мех. фак-та МГУ,2001, С. 376-378.

16. Кузьмин О.В., Леонова О.В. О полиномах разбиений. // Дискретная математика. Том 13. Вып. 2, 2001. С. 144 158.

17. Леонова О.В. Описание одноканальной системы массового обслуживания при помощи полиномов Тушара // Студент и научно-технический прогресс.- Иркутск: Иркут. ун-т, 1998.- С. 56-57.

18. Леонова О.В. Рекуррентные соотношения для полиномов Тушара.// Материалы 59-й ежегодной научной конференции профессорско-преподавательского состава, докторантов, аспирантов, студентов. Изд-во ИГЭА, 2000, С.372-375.

19. Леонова О.В. О комбинаторных полиномах разбиений // Труды 12-й Байкальской международной конференции «Методы оптимизации и их приложения» Иркутск. 2001, с. 97 100.

20. Макдональд И. Симметрические функции и многочлены Холла. М.: Мир, 1985.

21. Петров В.В. Суммы независимых случайных величин. М.: Наука, 1972.

22. Платонов М.Л. Элементарные применения комбинаторных чисел в теории вероятностей. В кн.: Теория вероятностей и математическая статистика. Киев: Вшца школа, 1974, вып. 11, с. 127-135.

23. Платонов М.Л. Комбинаторные числа класса отображений // Комбинаторный и асимптотический анализ. Красноярск, 1975.- С. 8195.

24. Платонов М.Л. Обращения формулы Бруно // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1975 -Вып. 35. С. 32-38.

25. Платонов М.Л. Комбинаторные числа класса отображений и их приложения. М.: Наука, 1979.

26. Платонов M.JI. Комбинаторные полиномы в алгебре операторов, перестановочных со сдвигом // Дискретная математика, 1992. Том 4. Вып. 1,С. 33-49.29. Риордан Дж. Введение в комбинаторный анализ. М.: Иностр. Лит., 1963.

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

28. Рыбников К.А. Ведение в комбинаторный анализ. М.: Изд-во Моск. Ун-та, 1985.

29. Сачков В. Н. Комбинаторные методы дискретной математики. М.: Наука, 1977.

30. Селиванов Б.И. Комбинаторный подход к формуле обращения Бюрмана Лагранжа // Комбинат, и асимптотич. Анализ. Краснояр. Ун-т, 1977, С. 153-169.

31. Хомяков М.А. Обращение многомерной формулы Бруно относительно производных любой из внутренних функций // Алгоритм, и комбинат, задачи дискретных систем и ЭВМ. Иркутск: Иркут. ун-т, 1991, С. 139-147.

32. Эндрюс Г. Теория разбиений. М.: Наука, 1982.

33. Bell Е.Т. Exponential polynomials // Ann. Math. 1934. - Vol 35. - P. 258-277.

34. Carlitz L. Weighted Stirling numbers of the first and second kind. I // Fibonacci Quart., 1980 Vol. 18, № 2, P. 147-162.

35. Carlitz L. Weighted Stirling numbers of the first and second kind. II // Fibonacci Quart., 1980 Vol. 18, № 3, P. 242-257.

36. Charalambides Ch.A., Chrysaphinou O. Partition polynomials in fluctuation theory//Math. Nachr., 1982, 106, P. 89-100.

37. Chrysaphinou O. On Touchard polynomials // Discrete Math., 1985, 54, P. 143-152.

38. Comtet L. Polynomes de Bell et formul explicite des derives successive dune fonction implicite // C. R. Acad. Sci.- Paris, 1968. A 267, № 14. P. 457-460.

39. Comtet L. Analyse Combinatore. Paris: Unire de France, 1970.

40. Frucht R.W., Rota G.C. Polymios de Bell у partitiones de conjumtos finitos // Scientia. 1965. 32, № 126, P. 5-10.

41. Gould H.W., Hopper A.T. Operational formulas connected with two generalizations of Hermite polynomials // Duke Math. J. 1962, 29,

42. Howard F.T/ Bell polynomials and degenerate Stirling Numbers // Rend. Sem. Mat. Univ. Padova, 1979 (1980).- 61, P. 203-219.

43. Koutras M. Non-central Stirling numbers and some applications // Discrete Math. 1982, № p. 73-89.

44. Lah I. Eine neue Art von Zahlen, ihre Eigenschaften und Anvendungin der mathematiscen Statistik. Mitteilungsbl. Math. Statist., 1955, 7, №3, S. 203.

45. Spitzer F. A combinatorial lemma and applications to probability theory // Trans. Am. Math. Soc., 1956, 82, 323-339.

46. Stirling I. Methodus differentials. London, 1860.

47. Sylvester J. Note on Burmans law for the inversio n of the independent variable // Philos. Mag., 1854. 8, P. 535-540.

48. Tauber S. On quasi-orthogonal numbers. Amer. Math. Monthly, 1962, 69, p. 365-372.

49. Todorov P.G. New differential recurrence relation for Bell polynomials and Lie coefficients // Докл. Болг. АН, 1985. Vol. 38, №1,- P.43-45.

50. Touchard J. Sur les cycles des substitutions // Acta Math., 1939.- 70, №3-4.- P. 243-297.

51. Turowicz A.B. Sur les derivels dordre superieur dune fonction inverse// Coll. Math., 1959. Vol. 7, №1.-P. 83-87.