Комбинаторные методы перечисления плоских корневых деревьев и путей на решетках

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

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

£ I. I.Общая схема построения комбинаторных чисел класса

отображений

§ 1.2. Комбинаторные полиномы разбиений

§ 1.3. Комбинаторная схема распространения последовательности до матрицы

§ 1.4. Обобщенные триномиальные коэффициенты

§1.5. Обобщения треугольника Паскаля

§1.6. Обобщенные числа Каталана

§ 1.7. Обобщенные числа Шрёдера

Глава 2. Перечисление плоских корневых деревьев

§2.1. Плоские корневые деревья

§ 2.2. Помеченные плоские корневые деревья Шредера
2.2.1. Классификация по количеству всех вершин в первом слое
2.2.2. Классификация по количеству внутренних вершин
§ 2.3. Плоские непомеченные корневые деревьяКаталана
2.3.1. Классификация по количеству всех вершин в первом слое
2.3.2. Классификация по количеству внутренних вершин
2.3.3. Классификация по высоте
§ 2.4. Плоские корневые деревья Моцкииа с петлями
2.4.1. Классификация по числу петель и ребер, выходящих из корпя
2.4.3. Классификация по числу петель
2.4.4. Классификация по высоте
Глава 3. Перечисление путей на решетках
^ 3. /. Пути Мак-Магона
§3.2. Пути Моцкииа
§3.3. Пути Дика
§3.4. Числа Шредера Кп и пути на плоскости
Заключение
Список литературы

В настоящее время в связи с развитием кибернетики и близких к ней разделов науки, существенно повысилась значимость дискретной математики в целом и комбинаторного анализа в частности.
Развитие комбинаторных методов обусловлено появлением разнообразных задач дискретной математики, связанных с существованием, алгоритмами построения и подсчетом числа некоторых конфигураций из элементов данного множества [1,2,7,8,10,34,35]. Конфигурации, построенные в соответствии с определенными правилами, называются обычно комбинаторными.
Настоящая диссертационная работа посвящена изучению комбинаторных чисел и полиномов, возникающих при решении перечислительных задач, т.е. задач, в которых необходимо определять число комбинаторных конфигураций данного класса или давать их классификацию, связанную с перечислением.
В работе разрабатываются комбинаторные методы перечисления плоских корневых деревьев и путей на решётках.
При решении указанных задач использованы комбинаторные полиномы - однородные полиномы Белла и Платонова, а также как известные комбинаторные числа, так и новые, введённые автором данной диссертационной работы.
Диссертация состоит из трёх глав, которые разбиты на 15 параграфов. В главе второй параграфы разбиваются на пункты.
Кратко охарактеризуем содержание отдельных глав диссертации.
В первой главе рассматриваются арифметические треугольники комбинаторного происхождения. Идеи построения и применения арифметических треугольников и пирамид, родственных широко известному

треугольнику Паскаля, высказывались многими авторами на протяжении ряда веков.
В 1665г. вышел в свет «Трактат об арифметическом треугольнике» Блеза Паскаля, посвящённый наиболее изящной численной схеме во всей математике - треугольнику Паскаля (см. [37]).
В книгах [4,17] изложены классические и новые арифметические, геометрические и комбинаторные свойства арифметических треугольников и пирамид Паскаля. В монографии [17], в частности, рассмотрены треугольники, построение которых связано с известными последовательностями однопараметрических комбинаторных чисел: треугольники Люка, Фибоначчи, Каталана, Моцкина, Трибоначчи (см* работы [5,39, 42, 46, 47, 50, 52, 53]) и др., а также треугольники, построенные из известных двупарамстрических комбинаторных чисел: Стирлинга первого и второго рода, Лаха, присоединённых чисел Стирлинга первого и второго рода и др. Элементы упомянутых выше арифметических треугольников определяются в соответствии с рекуррентными уравнениями и начальными условиями.
В данной диссертационной работе получила развитие идея М.Л. Платонова [30] распространения последовательности однопараметрических комбинаторных чисел до матрицы, составленной из соответствующих двупараметрических комбинаторных чисел.
Получены новые комбинаторные объекты, названные обобщенными числами, ряд свойств для которых устанавливается исходя из свойств Л - и Я-полиномов.
В параграфе 1.1 приводится описание общей схемы построения комбинаторных чисел класса отображений.
В параграфе 1.2 изучаются комбинаторные полиномы разбиений -однородные полиномы Белла и Платонова. Понятие «полином разбиения» -полином от нескольких переменных, определяемый с помощью суммы по

Во-вторых, из дерева Шредера Э с п-1 висячими и т-1 внутренними вершинами: или заменой одной из п-1 висячих вершин на т-ю внутреннюю с выходящими из нее двумя ребрами, при этом одна из двух висячих вершин получает метку п, а другая сохраняет метку замененной висячей вершины; или заменой корня на внутреннюю вершину с выходящим из нес ребром, висячая вершина которого - корень, добавляя к новому корню ребро, висячая вершина которого имеет метку п, при этом ранее имеющиеся пометки висячих вершин также не меняются. Число таких деревьев равно
{п + т-Х)КпЛт_у
Поскольку число деревьев, полученных первым и вторым способом, в сумме дают числа Кпт, то имеем соотношение (2.1).
Теорема доказана.
Известно (см., например [31]), что присоединенные числа Стирлинга второго рода Ь(п,!с) удовлетворяют следующему рекуррентному
соотношению:
Ь(п +1, к) = кЬ(п, к) + пЬ{п -1, к -1), (2.2)
где 6(0,0) = 1; Ь(п,0) = 0, п>0.
Из соотношений (2.1) и (2.2) следует, что
Кпт = Ь(п + т,т + 1), п> 2, 1 < т < п. (2.3)
Для чисел Шредера известно соотношение:

з „ = X Ь (п + к , к + 1), п > 2. (2.4)

Из формул (2.3) и (2.4) получаем
^ = ЇХ,„«>2. (2.5)
т=О
С учетом соотношения (2.5) числа Кпт названы в [22] расщепленными числами Шредера второго рода.
Первые значения чисел Кпт для 2 < п < 8 приведены в таблице 2.1.