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

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

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

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