Задача
COM-B2-M03-P015 Скобки и пути
Постройте биекцию между правильными скобочными последовательностями из \(n\) пар скобок и путями из \((0,0)\) в \((n,n)\), не поднимающимися выше диагонали \(y=x\).
Закрывающую скобку удобно считать шагом вправо, открывающую — шагом вверх или наоборот; выберите соглашение и проверьте условие префикса.
Возьмём открывающую скобку как шаг \(R\), закрывающую как шаг \(U\). В правильной скобочной последовательности в каждом префиксе открывающих скобок не меньше, чем закрывающих, то есть число \(U\) не превосходит числа \(R\). Это ровно условие \(y\le x\). Всего открывающих и закрывающих скобок по \(n\), значит путь идёт в \((n,n)\). Обратно, путь с \(y\le x\) даёт последовательность, в каждом префиксе которой открывающих не меньше закрывающих, то есть правильную скобочную последовательность.
Важно согласовать направление с неравенством.