Числа Каталана

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

Почему всегда получается правильная скобочная последовательность? По определению отображения, каждой закрывающей скобке соответствует своя открывающая, идущая перед ней, поэтому в любом префиксе открывающих скобок не меньше, чем закрывающих. Любую правильную скобочную последовательность можно лишь единственным способом разбить на пары так, чтобы часть последовательности, находящаяся внутри любой пары скобок, тоже была правильной, и именно такое разбиение дает определение отображения. Действительно, предположим противное: пусть существует пара чисел нарушающая это условие. Если бы все числа между и были бы разбиты на пары, то в любом префиксе последовательности открывающих скобок было бы хотя бы столько же, сколько закрывающих. Поэтому либо существует открывающая скобка с номером которая сопоставлена закрывающей либо закрывающая с номером сопоставленная открывающей Любая из этих ситуаций противоречит условию задачи.

Таким образом, разбиение чисел на пары из условия задачи однозначно определяет правильную скобочную последовательность, поэтому построенное отображение инъективно. При этом, нетрудно видеть, что оно и сюръективно: данную правильную скобочную последовательность разобьем на пары открывающих/закрывающих скобок, и соответственно разобьем числа от до на пары. Если при таком построении нарушилось условие задачи, то существует набор чисел такой, что в разбиение одновременно входят пары и но тогда подпоследовательность скобок с номерами не является правильной, что противоречит построению. Биективность доказана.

Переведем задачу на язык последовательностей: необходимо найти число последовательностей натуральных чисел где В одной из предыдущих задач мы поняли, что числа Каталана можно представить путями из в по линиям сетки, и не переступающими за Ясно, что если имеется подобный путь, и для каждого значения по от до мы выделим наибольшее значение по лежащее на пути до момента включительно, и прибавим к нему единицу, то мы получим последовательность из нашего условия. Разумеется, она будет неубывающей, и ее -ый элемент не будет превосходить И наоборот, по последовательности можно построить путь по решетке из в не пересекающий Его первый шаг всегда направо, а дальше для от 2 до сделаем последовательность из шага наверх и одного шага вправо. Из свойства последовательности, на своем пути мы ни разу не пересекли Ясно, что в конце мы находимся в точке с координатой по оси ниже прямой  – остается сделать необходимое число шагов, чтобы попасть в точку

Нетрудно видеть, что построенные отображения являются взаимно обратными. Значит, у нас есть биекция между двумя множествами объектов, откуда их размеры равны. Поэтому искомое количество способов из условия задачи равно

Скажем, что самый высокий школьник имеет номер следующий по росту — и так далее. Мы хотим расставить числа от до в таблицу так, чтобы в каждой ячейке число было больше, чем в ячейке выше и в ячейке левее неё. Давайте, вновь, рассмотрим пути Дика (пути по линиям сетки, не поднимающиеся выше ) из в Построим отображение, сопоставляющее пути Дика расстановку чисел в таблице: если в пути мы идём направо, то запишем номер хода в первую строку, а если вверх, то в нижнюю строку. Условие того, что каждое число больше, чем сосед слева, выполнено по построению, а условие того, что каждое число во второй строке больше, чем сосед сверху, равносильно тому, что в любой момент времени число шагов вверх не превосходит число шагов направо. Поэтому отображение возвращает правильную расстановку чисел в таблице, а обратное отображение возвращает путь Дика. Поскольку между множествами путей Дика и расстановок чисел в таблице существует биекция, их мощности совпадают, и ответом является

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

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

Доказательство. Скажем, что самый высокий школьник имеет номер следующий по росту — и так далее. Мы хотим расставить числа от до в таблицу так, чтобы в каждой ячейке число было больше, чем в ячейке выше и в ячейке левее неё. Давайте, вновь, рассмотрим пути Дика (пути по линиям сетки, не поднимающиеся выше ) из в Построим отображение, сопоставляющее пути Дика расстановку чисел в таблице: если в пути мы идём направо, то запишем номер хода в первую строку, а если вверх, то в нижнюю строку. Условие того, что каждое число больше, чем сосед слева, выполнено по построению, а условие того, что каждое число во второй строке больше, чем сосед сверху, равносильно тому, что в любой момент времени число шагов вверх не превосходит число шагов направо. Поэтому отображение возвращает правильную расстановку чисел в таблице, а обратное отображение возвращает путь Дика. Поскольку между множествами путей Дика и расстановок чисел в таблице существует биекция, их мощности совпадают, и ответом является

______________________________________________________________________________________________________________________________________________________

Посмотрим теперь на таблицу из леммы. Покажем как из такой таблицы получить расстановки учеников Анатолия и Василия. Вычеркнув из нее числа от до получим первую “таблицу” — расстановку учеников Анатолия. Если вычеркнуть, наоборот, числа от до повернуть “таблицу” на и заменить каждое число на то получим вторую “таблицу” — расстановку учеников Виталия. Ясно, что такое отображение биективно, поскольку очевидно как построить к нему обратное. Количество расстановок, тем самым, равно

Построим отображение из данного множества в множество правильных скобочных последовательностей. Для этого будем осуществлять алгоритм “поиск в глубину”, записывая открывающуюся скобку каждый раз, когда мы идём вниз, и закрывающуюся, когда идём вверх.

Замечание. Поиск в глубину по корневому дереву осуществляется следующим образом: мы идём каждый раз влево-вниз, пока не придём в лист, затем поднимаемся до ближайшей вершины с более чем одним потомком, «отрезаем» рёбра и вершины, по которым мы прошли дважды, и вновь идём всегда влево-вниз до листа, после чего повторяем алгоритм, пока не сотрём весь граф.

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

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