Комбинаторные полиномы разбиений и их приложения

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

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

Понятие «полином разбиений» — полином от нескольких переменных, определяемый с помощью суммы по различным разбиениям значений его индексов — введено Беллом в [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.