Что общего между скобками, многоугольниками и деревьями?
Подумайте об этом.
А пока рассмотрим задачу.
Сколькими способами можно выпуклый n+2-угольник разрезать на треугольники непересекающимися диагоналями?
Для небольших значений n можно выписать решения в явном виде и посчитать.
Рисовать дальше имеет смысл только, если полно свободного времени. Пойдем более простым путем. Для любого многоугольника можно выбрать сторону и построить на ней треугольники всеми возможными способами. При этом многоугольник окажется разделен на несколько многоугольников с меньшим количеством вершин. Решения для них уже известны, суммируем их.
Например, для семиугольника получим следующую картину:
Для следующих n получим:
n = 6 132 способа;
n = 7 429 способов;
n = 8 1430 способов и т.д.
Перейдем к следующей задаче.
Сколькими способами можно расставить скобки, при условии, что каждая открывающаяся скобка имеет парную закрывающуюся и не может быть идти после нее?
Если пар скобок больше четырех лучше перестать выписывать решения и начать рассуждать. Выделим какую-то пару скобок и оставшиеся будем распределять относительно нее. Получим пять возможных вариантов: главная пара не содержит внутри себя других скобок, содержит одну пару, две пары, три пары или четыре пары. Посчитав количество вариантов для каждого случая выясним, что общее количество равно 42. Увеличивая число пар скобок будем получать 132, 429, 1430 и т.д. количество способов.
Рассмотрим задачу на подсчет количеств путей Дика.
Сколькими способами можно пройти из точки (0;0) в точку (2n;0) двигаясь только вдоль векторов (1;1) и (1;-1) при этом не покидая первую координатную четверть?
Для больших n будет разумнее не рисовать все варианты, а использовать промежуточные точки. При этом будет получаться 132, 429, 1430 и т.д. путей.
Пожалуй, пришло время поговорить про деревья. А точнее про двоичные деревья, то есть такие из каждого узла которых выходит только две ветви. Если из узла не выходит ветви, то он называется листиком. А задача следующая.
Сколько существует бинарных деревьев с заданным количеством листьев?
Полагаю, вы уже догадываетесь, что для следующего количества листиков будет 14, 42, 132, 429, 1430 и т.д. деревьев.
В математике известно более шестидесяти задач, решением которых будет эта числовая последовательность. Она получила свое название в честь французского математика-геометра Эжена Шарля Каталана. Они так и называются - числа Каталана. Авторство сомнительное, многие задачи были решены другими учеными. Но Эжен Шарль Каталан сделал для их изучения достаточно, чтобы они остались в истории под его именем.
На первый взгляд кажется, что в каждой задаче речь идёт про совершенно разные объекты. Но то, что решением является одна и та же последовательность чисел, говорит о том, что между всеми задачами можно установить соответствие. Например, так:
