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

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

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

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

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

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

$C_{0}=1\,\!$ и $\qquad C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}$ для $n\geq 1.\,\!$

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

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

Помимо уже приведённых есть ещё одна формула, определённая ниже:

$R(o,n)=\left\{{\begin{array}{llcccc}0,&o=0&and&n=0\\1,&n=0&or&o>n&or&o<0\\r(o+1,n-1)+r(o-1,n-1),&else\\\end{array}}\right.$

Для получения $C_{n}$ достаточно вычислить $R(0,2n)$.

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

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

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