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

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

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

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

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

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

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

Это соотношение легко получить, заметив, что любая непустая правильная скобочная последовательность ω однозначно представима в форме ω = (ω₁)ω₂, где ω_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) = \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 существует k различных вариантов её выбора. Выбор закрывающей скобки однозначно определён уже выбранной парной ей открывающей и не учитывается.

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

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

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