Правильная скобочная последовательность

Пра́вильная ско́бочная после́довательность (ПСП) — частный случай скобочной последовательности. Правильные скобочные последовательности образуют язык Дика и формально определяются следующим образом:

• "" (пустая строка) — ПСП
• ПСП, взятая в скобки одного типа — ПСП
• ПСП, к которой приписана слева или справа ПСП — тоже ПСП

Количество правильных скобочных последовательностей

Количество правильных скобочных последовательностей из $2n$ скобок ($n$ открывающих и $n$ закрывающих) одного вида выражается равно числу Каталана $C_n$, что можно вывести несколькими способами:

• Рекуррентное соотношение:

$C_0 = 1\,\!$ и $\qquad C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i}$ для $n\ge 1.\,\!$

Это соотношение легко получить, заметив, что любая непустая правильная скобочная последовательность $\omega$ однозначно представима в форме $\omega=(\omega _{1})\omega _{2}$, где $\omega _{1, 2}$ — правильные скобочные последовательности.

• Выражение через биномиальные коэффициенты:

$C_n = \frac{1}{n+1}{2 n \choose n} = \frac{(2n)!}{n!(n + 1)!} = {2 n \choose n} - {2 n \choose n-1}.$

• Ещё одно рекуррентное соотношение:

$R(o,n) = \begin{cases} 1,&o = 0\,\,\mbox{and}\,\,n = 0;\\ 0,&n = 0\,\,\mbox{or}\,\,o > n\,\,\mbox{or}\,\,o < 0;\\ R(o + 1, n - 1) + R(o - 1, n - 1),& \mbox{otherwise}.\\ \end{cases}$

При этом $C_n = R(0,2n).$

Легко показать, что если в скобочной последовательности имеется $k$ типов скобок, то количество возможных правильных скобочных последовательностей с $n$ открывающими скобками равно произведению $C_n$ на $k^n$. Действительно, для каждой открывающей скобки из $n$ существует $k$ различных вариантов её выбора. Выбор закрывающей скобки однозначно определён уже выбранной парной ей открывающей и не учитывается.

Генерация правильных скобочных последовательностей

Введём теперь лексикографический порядок на скобочных последовательностях. В первую очередь заметим, что открывающая скобка идёт раньше, чем закрывающая; так как скобочная последовательность, начинающаяся с закрывающей скобки, не является правильной. Теперь каждому из $k$ типов скобок присвоим свой лексикографический приоритет. Выбор этого приоритета не принципиален и ни на что не повлияет в ходе дальнейших рассуждений. Поэтому будем считать, что i^й тип скобок находится на i^й позиции в лексикографическом порядке. Очевидно, что первой последовательностьтью с $n$ открывающими скобками будет последовательность вида $(_1(_1...(_1 )_1)_1...)_1$. Теперь рассмотрим задачу о получении следующей скобочной последовательности после данной.

Получение следующей правильной скобочной последовательности