Задача
COM-B2-M03-P019 Каталановы объекты
Постройте биекцию между правильными скобочными последовательностями из \(n\) пар скобок и разбиениями выпуклого \((n+2)\)-угольника на треугольники, если разрешено использовать рекурсивное описание: первая пара скобок задаёт треугольник, прилегающий к фиксированной стороне.
Используйте одинаковую рекурсию: объект распадается на левую и правую части.
Фиксируем сторону многоугольника. В любой триангуляции есть единственный треугольник, прилегающий к этой стороне; его третья вершина делит многоугольник на две меньшие части. Аналогично правильная скобочная последовательность единственно записывается как \((A)B\), где \(A\) и \(B\) — правильные последовательности. Сопоставим третью вершину так, чтобы число пар в \(A\) равнялось числу треугольников в левой части, а \(B\) — в правой. Рекурсивно применяя то же правило, получаем взаимно однозначное соответствие. База \(n=0\) очевидна.
Не требуется рисовать все случаи; важно увидеть одинаковую рекурсивную структуру.