Комбинаторные полиномы разбиений и их приложения тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Леонова, Ольга Васильевна
- Специальность ВАК РФ01.01.09
- Количество страниц 78
Оглавление диссертации кандидат физико-математических наук Леонова, Ольга Васильевна
Введение.
Глава 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. С-полиномы Тушара.
Рекомендованный список диссертаций по специальности «Дискретная математика и математическая кибернетика», 01.01.09 шифр ВАК
Обобщенные пирамиды Паскаля и их приложения2002 год, доктор физико-математических наук Кузьмин, Олег Викторович
Комбинаторные методы перечисления плоских корневых деревьев и путей на решетках2004 год, кандидат физико-математических наук Тюрнева, Татьяна Геннадьевна
Обобщенные пирамиды Паскаля и комбинаторные формулы обращения2008 год, кандидат физико-математических наук Балагура, Анна Александровна
Применение произведения Адамара степенных рядов в комбинаторных и вероятностных задачах2016 год, кандидат наук Потехина, Елена Алексеевна
Комбинаторные свойства (0,1)-матриц и взвешенные пути на решетках2009 год, кандидат физико-математических наук Кроткин, Владислав Сергеевич
Введение диссертации (часть автореферата) на тему «Комбинаторные полиномы разбиений и их приложения»
В связи с развитием кибернетики и близких к ней разделов науки, в настоящее время существенно возросла значимость дискретной математики в целом и комбинаторного анализа в частности. Развитие компьютерных технологий резко расширило возможности перебора и повысило интерес к дискретным моделям, что обусловило повышение интереса к задачам комбинаторного анализа. Комбинаторные методы применяются как в самой математике, так и вне ее - теория кодирования, планирование эксперимента, топология, конечная алгебра, математическая логика, теория игр, кристаллография, биология, статистическая физика, экономика и т.д.
В данной работе, принадлежащей области комбинаторного анализа, разрабатывается ряд вопросов теории комбинаторных полиномов разбиений и комбинаторных чисел; при помощи комбинаторных чисел и полиномов осуществляется описание производящих функций для разбиений различных типов, одноканальной системы массового обслуживания.
Понятие «полином разбиений» - полином от нескольких переменных, определяемый с помощью суммы по различным разбиениям значений его индексов - введено Беллом в [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].
Похожие диссертационные работы по специальности «Дискретная математика и математическая кибернетика», 01.01.09 шифр ВАК
Алгоритмические исследования комбинаторных чисел и полиномов2005 год, кандидат физико-математических наук Баранчук, Антон Леонидович
Комбинаторные свойства сечений обобщенных пирамид Паскаля2011 год, кандидат физико-математических наук Серегина, Марина Валерьевна
Комбинаторные числа и взвешенные траектории на решетках2007 год, кандидат физико-математических наук Соловьева, Людмила Александровна
Алгоритмы и программный модуль получения явных выражений коэффициентов производящих функций2017 год, кандидат наук Перминова Мария Юрьевна
Метод получения явных выражений полиномов на основе степеней производящих функций2016 год, кандидат наук Кручинин Дмитрий Владимирович
Список литературы диссертационного исследования кандидат физико-математических наук Леонова, Ольга Васильевна, 2001 год
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.
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.