Числа Каталана и их применение в комбинаторике

XXVIII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке

Личный портфель

Числа Каталана и их применение в комбинаторике

Жамбалова А.Б. 1
1МОУ "Челутайская средняя общеобразовательная школа" Агинского муниципального округа
Дармаева Г.Н. 1
1МОУ "Челутайская средняя общеобразовательная школа" Агинского муниципального округа
Автор работы награжден дипломом победителя III степени
Диплом школьникаСвидетельство руководителя
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

Введение

Любому математику часто приходится сталкиваться с бесконечными последовательностями целых положительных чисел. Если последовательность простая, как например, последовательность удваивающихся чисел (1,2,4,8,16…) или последовательность квадратов (1,4,9,16,25…), то она распознается сразу же. Редкий математик не сможет узнать числа Фибоначчи (1,1,2,3,5,8..) или треугольные числа (1,3,6,10,15,21…). Если же последовательность не столь известна, то можно потратить много времени в поисках, задающего ее рекуррентного (если вычисление следующего члена требует знания предыдущих членов) или нерекуррентного закона (нереккурентная формула дает n-ый член, не требуя знания предыдущих). Данная работа посвящена числам Каталана, которые появляются в самых разных комбинаторных задачах. Эта последовательность названа в честь бельгийского математика Каталана (Catalan), жившего в 19 веке, хотя на самом деле она была известна ещё Эйлеру (Euler), жившему за век до Каталана.

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

Цель исследования: доказать эквивалентность способов определения числа Каталана на конкретных примерах.

Для достижения цели в работе поставлены следующие задачи:

  • раскрыть различные определения чисел Каталана

  • рассмотреть рекуррентную и аналитическую формулы определения чисел Каталана;

  • выстроить взаимнооднозначное соответствие между способами определения числа Каталана.

Гипотеза: различные способы получения чисел Каталана эквивалентны друг другу.

1. Теоретические аспекты исследования чисел Каталана

    1. Определения чисел Каталана исходя из способов их получения

Числа Каталана, которые обозначаются c0, c1, c2, c3 . . . . Вот некоторые значения чисел Каталана (таблица 1):

n

n 0

n1

n2

n3

n 4

n5

n 6

n 7

n 8

n 9

n 10

n 11

n 12

n 13

cn

1

1

2

5

14

42

132

429

1430

4862

16796

58786

208012

742900

Таблица 1 – Некоторые значения чисел Каталана

Имеется огромное количество разных определений чисел Каталана. Рассмотрим некоторые из них.

  1. Количество плоских корневых деревьев с n рёбрами

Вот полные списки при n ≤ 3 (рис.1)

Рисунок 1 – Полные списки плоских корневых деревьев с n рёбрами при n ≤ 3

2) Количество триангуляций (n + 2)-угольника с выделенной стороной

Полная запись чисел Каталана при n ≤ 3 (рис. 2):

Рисунок 2 – Полная запись чисел Каталана по определению триангуляций, при n ≤ 3

Исходя из рисунка 2, при n = 0 приходится иметь дело с пустой триангуляцией двуугольника.

3) Количество правильных скобочных слов с n парами скобок

Представим себе все правильно записанные алгебраические выражения, в которых скобки используются так, как учат в школе. Потом мысленно сотрём все знаки, кроме скобок. То, что останется, и называется правильными скобочными словами. Скобки окажутся разбитыми на пары: каждой открывающейся скобке соответствует закрывающаяся. При n = 0 нам придётся работать с пустым словом, которое будет обозначаться прочерком. – Полные списки (рис.3):

Рисунок 3 – Полная запись чисел Каталана по определению скобочных слов с n парами скобок, при n ≤ 3

4) Монотонные пути в квадрате

Это маршруты из левого нижнего угла квадрата в правый верхний, которые идут по линиям сетки вверх или вправо и не заходят выше диагонали. На рисунке все такие пути для квадрата 3x3.

Рисунок 4 – Полная запись чисел Каталана по способу монотонных путей в квадрате, для квадрата 3x3

5) Разбиение вершин многоугольника на пары

Четное число точек на окружности можно объединить в пары непересекающимися хордами. Число способов таких объединений также равно числу Каталана.

Рисунок 5 – Полная запись чисел Каталана по способу разбиения вершин многоугольника на пары

6) Таблица Юнга

Таблица Юнга – прямоугольник, заполненный последовательными числами так, чтобы они возрастали во всех строках и столбцах. Число таблиц Юнга размером 2xn также выражается числом Каталана.

Рисунок 5 – Полная запись чисел Каталана по способу таблиц Юнга

    1. Формулы определения чисел Каталана

Числа Каталана удовлетворяют рекуррентному соотношению (то есть соотношению, выражающему очередной член последовательности через предыдущие):

с0 = 1,

при n= 0,1,2,3…

Это соотношение легко получается из того, что любая непустая правильная скобочная последовательность однозначно представима в виде w = (w 1) w 2 , где w 1 , w 2 — правильные скобочные последовательности.

Есть еще одно реккурентное соотношение: .

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

Данную формулу также называют аналитической, где обозначен, как биномиальный коэффициент.

Кроме того, числа Каталана определяются реккурентным соотношением:

с0 = 1,

при n = 0, 1, 2, 3....

В последнем определении даётся просто формула для чисел Каталана.

Приводимый ряд можно рассматривать либо как формальный (для его понимания достаточно знать формулу Тейлора-Маклорена f(x) = f(0) + Или формулу Ньютона (1+t) α =1+at+ …), либо как сходящийся при .

Вывод по 1 главе: известно много определений числа Каталана, которые исходят из способов их появления чисел: правильные скобочные последовательности, двоичные деревья, монотонные пути в квадрате, триангуляции многоугольника, разбиение вершин многоугольника на пары. таблица Юнга. Имеется две формулы для чисел Каталана: рекуррентная и аналитическая.

2. Практическая часть

Пример решения комбинаторных задач с помощью чисел Каталана

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

Задача 1:

Имеются 12 карандашей попарно различной длины. Сколькими способами можно уложить их в коробку в два слоя по шесть карандашей так, чтобы в каждом слое карандаши были упорядочены по возрастанию длины (слева направо), а каждый карандаш верхнего слоя лежал строго над карандашом нижнего слоя и был короче его?

Решение:

Заметим, что такая укладка карандашей соответствует таблице 2*6 куда мы ставим числа от 1 до 12 так, чтобы во всех столбцах и строках числа шли по возрастанию (таблица — это коробка, число — это номер карандаша по возрастанию длины: 1 — самый короткий, 12 — самый длинный). Данная формулировка задачи является одним из определений чисел Каталана и очень легко сопоставляется правильной скобочной последовательности: число — номер скобки, положение числа (в верхней строке или в нижней) — открытая это скобка или закрытая, соответственно.

Ответ: 132

Задача 2.

У театральной кассы стоит очередь за билетами из 8 человек. Билет стоит пять рублей, а в наличии у каждого из стоящих в очереди есть ровно одна банкнота — либо пять, либо десять рублей, причем каждый из двух видов банкнот встречается ровно у 4 человек. У кассира в начальный момент нет пятирублевых банкнот. Каждый, стоящий в очереди, покупая билет, если дает десятирублевую банкноту, должен получить сдачу. Какова вероятность того, что на протяжении всей очереди у кассира всегда будет достаточный запас пятирублевых банкнот для сдачи, а в конце у него не останется пятирублевых купюр?

Решение:

Легко видеть, что всего существует возможных ситуаций (ровно столько есть способов распределить среди 2n любителей театра n человек, у которых на руках десятирублевая купюра и n человек с пятирублевыми купюрами на руках). Следовательно, для решения задачи нужно посчитать, в скольких случаях у кассира на протяжении всей очереди будут иметься в достаточном количестве пятирублевые купюры, причем в последний момент они у него закончатся. Полученное число случаев нужно разделить число случаев на .

Подсчет таких случаев для малых значений числа n приводит нас к знакомой последовательности: при n=1 это число равно единице, при n=2 — двум, далее пяти, четырнадцати, и т.д.

Задача 3:

Сколько существует правильных скобочных последовательностей из 4 пар скобок?

Решение:

Нам нужно найти C4​ — четвёртое число Каталана.

Используем явную формулу:

Cn​=n+11​(n2n​)=n!(n+1)!(2n)!​

Подставляем n=4:

C4​=51​(48​)=51​⋅4!4!8!​=51​⋅24⋅2440320​=51​⋅70=14.

Ответ: 14 последовательностей.

Проверка (кратко): для n=4 действительно существует 14 вариантов, например:
(((()))), ((()())), ((())()), ((()))(), (()(())), …, ()()()().

Задача 4:

На сколько способов можно разрезать выпуклый пятиугольник на треугольники с помощью непересекающихся диагоналей?

Решение:

  1. Пятиугольник — это (n+2)‑угольник при n=3.

  2. Число способов триангуляции равно Cn​, т. е. C3​.

  3. Вычисляем C3​ по формуле:

C3​=41​(36​)=41​⋅3!3!6!​=41​⋅6⋅6720​=41​⋅20=5.

Ответ: 5 способов.

Пояснение: каждый способ соответствует выбору двух непересекающихся диагоналей, разбивающих пятиугольник на 3 треугольника.

Задача 5:

 Сколько есть маршрутов из (0,0) в (6,0), если каждый шаг — (+1,+1) или (+1,−1), и путь не опускается ниже y=0? (Это пути Дика длины 6.)

Решение:

  1. Длина пути — 2n, значит 2n=6, откуда n=3.

  2. Число таких путей — это C3​.

  3. Уже вычислили выше: C3​=5. Ответ: 5 путей.

9

Примеры путей (U = вверх, D = вниз):

  • U U U D D D

  • U U D U D D

  • U U D D U D

  • U D U U D D

  • U D U D U D

Общий вывод

Во всех задачах ответ даётся числом Каталана Cn​, где n определяется условием.

Заключение

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

Помимо интереса это имеет и некоторую практическую ценность. Числа Каталана – это удобный инструмент для решения многих интересных задач комбинаторики простым и элегантным способом. Можно применять в задачах по вероятности, а также в олимпиадных задачах.

Список использованной литературы

  1. Доценко В.В. Числа Каталана и естественные отображения // Летние конференции Турнира городов: Избранные материалы. Вып. 1 / Под общ. ред. Н.Н. Константинова. Сост. Б.Р. Френкин. — М.: МЦНМО, С. 139-166.

  2. Онлайн – энциклопедия целочисленных последовательностей (OEIS) / Нил Слоун.

  3. Специальные числа: многоуровневая система творческих задач: учебно-методическое пособие / А.С. Ростовцев, Е.И. Деза, Т.А. Немкина, А.В. Эргешовав. – Москва: Белый ветер, 2020. – С. 8.

Интернет-ресурсы:

  1. http://www.e-maxx-ru.1gb.ru/algo/catalan_numbers

  2. https://habr.com/ru/post/165295/

  3. https://nnov.hse.ru/data/2016/10/19/1107972447/Числа%20Каталана-2.pdf

http://www.mi-ras.ru/~podolskii/files/lecture2.pdf

Приложение 1

Соответствие объектов для третьего числа Каталана

 
Просмотров работы: 3