Математика · объяснение и практика

Как отражение плохого пути считает допустимые скобочные структуры

Как префиксное условие правильных скобок превращается в ограничение пути, а отражение первого плохого участка даёт формулу числа Каталана.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

В маршруте Счёт через устройство объектов · 10 тем

Главная мысль

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

Равного количества скобок недостаточно

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

Без ограничения высоты путей C(2n,n): выбираем позиции открывающих скобок. Нужно удалить плохие пути, которые хотя бы раз достигают высоты −1. Для каждого такого пути существует первый момент этого нарушения. Выбор именно первого момента делает последующую конструкцию однозначной, а не зависящей от произвольного места отражения.

Отразить участок до первого нарушения

В плохом пути поменяем вверх и вниз на участке до первого достижения −1 включительно. На этом участке было на один шаг вниз больше, поэтому после отражения весь путь содержит n+1 шаг вверх и n−1 вниз. Его конец теперь имеет высоту два. Таких неограниченных путей C(2n,n−1).

Преобразование обратимо: у любого пути с конечной высотой два найдётся первое достижение высоты один. Отражение начального участка до него возвращает плохой сбалансированный путь. Поэтому плохие пути посчитаны точно, без повторов. Вычитание даёт C(2n,n)−C(2n,n−1)=C(2n,n)/(n+1).

Пример

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

Всего сбалансированных по количеству C(6,3)=20. Плохим соответствуют C(6,2)=15 отражённых путей. Разность 5 — это число правильных последовательностей, включая вложенные и последовательные пары.

Что изменяется при другом запрете

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

При n=0 есть одна пустая правильная последовательность. Это полезное основание для рекурсии: после первой открывающей скобки её парная закрывающая отделяет внутренний правильный блок от оставшегося правильного хвоста. Подсчёт по размерам этих двух блоков даёт ту же последовательность чисел Каталана, но использует другое разбиение объектов.

От чтения к действию

А теперь — вы

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

Частые вопросы

Почему выбирают первое достижение отрицательной высоты?

Это делает отражаемый участок однозначным и позволяет построить обратное преобразование по первому достижению положительной высоты.

Достаточно ли одинакового числа открывающих и закрывающих?

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться