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

Пра́вильная ско́бочная после́довательность (ПСП) — символьная последовательность, составленная в алфавите, состоящем из символов, сгруппированных в упорядоченные пары (типы скобок, графически обозначаемые "(" и «)», "[" и «]», «/*» и «*/» и т. п.), удовлетворяющая определённым правилам, обеспечивающим последовательную вложенность подпоследовательностей, обрамлённых открытой и закрытой скобкой одного типа.

Правильные скобочные последовательности образуют язык Дика и формально определяются следующим образом:

пустая строка — правильная скобочная последовательность;
правильная скобочная последовательность, взятая в скобки одного типа — правильная скобочная последовательность;
правильная скобочная последовательность, к которой приписана слева или справа правильная скобочная последовательность — тоже правильная скобочная последовательность.

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

Число правильных скобочных последовательностей из [math]\displaystyle{ 2n }[/math] скобок ([math]\displaystyle{ n }[/math] открывающих и [math]\displaystyle{ n }[/math] закрывающих) одного вида равно числу Каталана [math]\displaystyle{ C_n }[/math], что можно вывести несколькими способами:

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

[math]\displaystyle{ C_0 = 1 }[/math] и [math]\displaystyle{ \qquad C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i} }[/math] для [math]\displaystyle{ n\ge 1. }[/math]

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

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

[math]\displaystyle{ C_n = \frac{1}{n+1}{2 n \choose n} = \frac{(2n)!}{n!(n + 1)!} = {2 n \choose n} - {2 n \choose n-1}. }[/math]

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

[math]\displaystyle{ R(o,n) = \begin{cases} 1,&o = 0\,\,\mbox{and}\,\,n = 0;\\ 0,&n = 0\,\,\mbox{or}\,\,o \gt n\,\,\mbox{or}\,\,o \lt 0;\\ R(o + 1, n - 1) + R(o - 1, n - 1),& \mbox{otherwise}.\\ \end{cases} }[/math]

При этом [math]\displaystyle{ C_n = R(0,2n). }[/math]

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

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

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