Введение 3
I глава. Производящие функции 5
§1. Основные определения и свойства 5
§2. Производящие функции для известных последовательностей 6
2.1. Геометрическая прогрессия 6
2.2. Последовательность Фибоначчи 7
2.3. Числа Каталана 9
II глава. Классические определения чисел Каталана 13
§3. Разрезания на треугольники 13
§4. Вычисления произведений 15
§5. Деревья с п листьями 18
§6. Деревья с п вершинами 19
§7. Числа Белла и плоские рифмовки 20
§8. Пути Дика 21
§9. Треугольник Каталана 22
III глава. Различные комбинаторные интерпретации
обобщённых чисел Каталана 26
§10. Большие и малые числа Шрёдера 26
§11. «Разноцветные» интерпретации обобщенных чисел Каталана 31
11.1. Деревья с п вершинами 31
11.2. Двоичные деревья с 2 п + 1 вершинами 32
11.3. Пути Дика 33
11.4. Разбиение вершин многоугольника на пары 36
11.5. Таблица Юнга 37
11.6. Скобочные структуры 37
11.7. Соединения 2п точек на плоскости 38
IV глава. Применение программного пакета Maple при решении задач 39
§12. Решение задач на применение классических определений чисел Каталана 39
§13. Решение задач на применение формулы для обобщенных чисел
Каталана 42
Заключение 46
Список литературы
Числовая последовательность Каталана встречается во многих задачах комбинаторики. Числа этой последовательности названы в честь бельгийского математика 19 века Эжена Шарля Каталана, хотя сама последовательность была известна ещё Л. Эйлеру.
Видоизменение комбинаторных задач, рассмотренных Каталаном, приводит к появлению числовых последовательностей с близкими свойствами. Эти комбинаторные задачи и новые числовые последовательности условно называют каталановскими структурами и обобщенными числами Каталана. В качестве примера упомянем известную комбинаторную задачу Шрёдера разрезания многоугольника с помощью непересекающихся диагоналей. Ее решение представляет собой обобщение классической последовательности Каталана; числа этой последовательности называют малыми числами Шрёдера.
Актуальность темы состоит в том, что числа Каталана, являясь специальными числами натурального ряда, возникая из комбинаторных задач, порождают своим существованием целый ряд других комбинаторных проблем, требующих решения.
Цель квалификационной работы — изучение свойств обобщённых чисел Каталана и их применение при доказательстве различных комбинаторных тождеств, применение аппарата производящих функций в задачах перечисления обобщённых классических комбинаторных объектов.
Задачи работы:
- изучить свойства производящих функций, привести примеры использования производящих функций в задачах генерации комбинаторных объектов;
- рассмотреть классические определения чисел Каталана и исследовать обобщенные числа Каталана, объединив эти структуры;
- изучить различные комбинаторные интерпретации обобщённых чисел Каталана и получить некоторые комбинаторные соотношения для этих чисел;
- решить комбинаторные задачи на вычисление обобщённых чисел Каталана и с помощью системы компьютерной алгебры Maple проверить эти вычисления.
Теоретическая и практическая значимость темы состоит в возможности использования материалов квалификационной работы для проведения кружков и факультативов, а также для подготовки к олимпиадам по информатике и математике.
Таким образом, числовая последовательность Каталана интересна прежде всего тем, что появляется очень часто, самым неожиданным образом во многих задачах из различных областей математики, в первую очередь — при решении комбинаторных проблем.
В ходе исследования было рассмотрено несколько определений чисел Каталана и в результате объединения этих структур были получены обобщенные числа Каталана, рассмотрены их взаимосвязи. Нами было приведено несколько интерпретаций обобщенных чисел Каталана, последовательность обобщенных чисел Каталана; была получена производящая функция и формула для вычисления этих чисел.
Нами было подобрано и решено большое количество комбинаторных задач, в которых обнаруживаются обобщенные числа Каталана. Решения были проверены с помощью системы компьютерной алгебры Maple.
Таким образом, цель работы достигнута. Анализируя различные источники литературы, мы пришли к выводу, что числа Каталана актуальны и очень популярны в современной математике. Они часто встречаются на математических олимпиадах. К сожалению, выбранная тема зачастую остаётся за страницами школьного учебника, хотя она очень интересна и многогранна. Хочется отметить, что данная тема требует очень серьезного внимания и является не до конца изученной, несмотря на большое количество публикаций.
