Обобщенные пирамиды Паскаля и комбинаторные формулы обращения

• Автор: Балагура, Анна Александровна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Иркутск
• Количество страниц: 110 с. : ил.

Глава 1. Обобщенные треугольники Паскаля и частично упорядоченные множества

1.1. Частично упорядоченные множества

1.2. Геометрические интерпретации обобщенных треугольников Паскаля

1.3. Определители обобщенных треугольников Паскаля

из биномиальных коэффициентов

1.4. Частично упорядоченные множества обобщенных треугольников Паскаля

Глава 2. Обобщенные пирамиды Паскаля и им обратные

2.1. Обобщенные триномиальные коэффициенты первого и второго рода

2.2. Обращение А- и В-пирамид

2.3. Трехмерные обобщенные числа Стирлинга, Уитни, Лаха

2.4. Обращение типа Мебиуса

Глава 3. Комбинаторные полиномы и их приложения
3.1. Перечисление помеченных корневых деревьев
3.2. Комбинаторное построение А- и В-полиномов
3.3. Комбинаторные полиномы в модели управления рисками
Заключение Приложения Список литературы

Актуальность темы. Со второй половины XX века наблюдается-интенсивное развитие комбинаторики — одной из основных частей современной дискретной математики [1, 19, 48, 51, 54]. Важная, но не единственная, роль в этом принадлежит изменению статуса дискретной математики в связи с развитием информационных технологий и возрастанием возможностей дискретных методов исследования [55]. Внутренние причины изменений в комбинаторике связаны с объединением^ . и согласованием ее разделов и проникновением идей комбинаторного анализа в смежные разделы математики и другие области науки [23, 38, 49, 50]. Одно из перспективных направлений исследований -комбинаторика на частично упорядоченных множествах [49].
Настоящая диссертационная работа, принадлежащая области комбинаторного анализа, посвящена построению и изучению комбинаторных чисел и полиномов, описываемых обобщенной пирамиды Паскаля.
Комбинаторные числа и различные способы их классификации известны давно. Наряду с общими подходами к построению комбинаторных чисел, берущих свое начало в работах P.A. Мак-Магона и А. Кэли, можно отметить теорию перечисления Дж. Пойа [6, 45] и Дж. Г. Редфилда [46]. M.J1. Платонов [38] предложил и разработал общую схему построения комбинаторных чисел класса-отображений, по построению близкую к схеме Пойа. Достаточно общий подход к изучению и построению комбинаторных объектов, основанный на анализе свойств обобщенной пирамиды Паскаля, был разработан 0:В. Кузьминым сравнительно недавно [23].
Классическими методами комбинаторного анализа являются, в частности, методы производящих функций и рекуррентных соотношений, геометрические и асимптотические методы. Можно указать две причины, по которым применение методов теории частично упорядоченных множеств позволяет исследовать комбинаторные объекты «изнутри». Во-первых, при данном подходе комбинаторное число рассматривается как вес множества перестановок особого
вида - таким образом, мы у истока задач перечисления. Во-вторых, обращение

Мебиуса проясняет строение объектов, поскольку большинство семейств дискретных структур, которые часто лишены каких-то алгебраических законов композиции, тем не менее, обычно снабжены естественным частичным порядком. Это обусловливает актуальность темы исследований.
Изучение решеток и частично упорядоченных множеств имеет свое начало в работах Г. Буля, Ч.С. Пирса, Е. Шредера и Р. Дедекинда. Развитие этой теории началось в 1930-х годах с работ Г. Биркгофа (см. например, библиографию в [4]). Идея алгебр инцидентности восходит к Р. Дедекинду и Е.Т. Беллу. В общем виде формула обращения Мебиуса была впервые получена независимо друг от друга Л. Вайснером и Ф. Холлом. Дж.-К. Рота в [92] показал важность теории обращения функций Мебиуса в современной комбинаторной математике. Одним из наиболее полезных методов перечисления в дискретных задачах теории вероятностей и комбинаторного анализа является принцип включения-исключения. Идея этого метода встречается в работах нескольких математиков XIX века, но, по-видимому, наиболее ясно была сформулирована А. Пуанкаре. Следует отметить, что на практике не всегда легко заметить возможность применения данного метода. Часто множество перечисляемых объектов обладает некоторым естественным порядком (в общем случае частичным). Вместо того, чтобы вводить, на таком множестве линейный порядок, во многих случаях бывает полезнее применить технику, учитывающую его естественный (комбинаторный) порядок. Данный подход позволяет решить задачу обращения некоторых комбинаторных сумм. Такое обращение можно выполнить, определив функцию Мебиуса для частично упорядоченного множества. Статья Рота положила начало целому циклу работ, объединенных общим названием «Об основах комбинаторной теории» [3, И] и состоящему из работ как самого Рота, так и его учеников и сотрудников. О значении обращения Мебиуса в комбинаторной математике сказано очень много последователями и учениками Рота, а также российскими математиками [7].
Частично упорядоченные множества обобщенных треугольников Паскаля
изучались в частности Р. Стенли [49, 95], им было сформулировано определение

Глава 2. Обобщенные пирамиды Паскаля и им обратные
2.1. Обобщенные триномиальные коэффициенты первого и второго рода
Обобщенной пирамидой Паскаля [24] называется трехгранный пирамидальный массив, элементы которого удовлетворяют следующим рекуррентным соотношениям:
V (и, k,l) = a„k,xl V(n-l,k-l,/) + pnkJ.y V(n -1 ,к, l — 1) + упк, V(n~,k,l), (2.1)
с граничными условиями П(0,0,0) = F0; V(n, к, 1)=0, если min(n, к, I, п-к-[)<0.
Следуя [23, 24], рассмотрим важные частные случаи обобщенной пирамиды Паскаля - А- и В-пирамиды, в каждом сечении которых расположены обобщенные триномиальные коэффициенты второго и первого рода соответственно.
Пусть а={а,}"0,/7={Д}”0, у ={'/<}"0 - последовательности, которые назовем базовыми последовательностями или базами.
Положим в формуле (2.1) V0 = 1, тогда при
а„.к-и =«„-!> Дам = Д-l > А.*,/ = A-i. » * 1» 0 < /с < п, 0 < / < п - к имеем V(n, к, I) = В"к , и из соотношения (2.1) следует рекуррентная формула
Я" =а Я"“1 +й Я"-' +у R"-1 ^ AVl "*,/-1 п- к,1 >
определяющая обобщенные триномиальные коэффициентами первого рода.

Да.ы = А » =А, 0 < Æ < л, 0<1<п-к,
V(n, к, 1) = Ак/, а из соотношения (2.1) имеем рекуррентную формулу
Д./ =ак- Д-1,/ А А./-1 +7* А,/ >
определяющую обобщенные триномиальные коэффициенты второго рода.
Из рекуррентных соотношений также могут быть получены следующие разложения:
X!ËAV**-y =П(«а+А7+а), и~1,
/с=0 /=0 »