Русская Википедия:Правильная скобочная последовательность
Пра́вильная ско́бочная после́довательность (ПСП) — символьная последовательность, составленная в алфавите, состоящем из символов, сгруппированных в упорядоченные пары (типы скобок, графически обозначаемые "(" и «)», "[" и «]», «/*» и «*/» и т. п.), удовлетворяющая определённым правилам, обеспечивающим последовательную вложенность подпоследовательностей, обрамлённых открытой и закрытой скобкой одного типа.
Правильные скобочные последовательности образуют язык Дика и формально определяются следующим образом:
- пустая строка — правильная скобочная последовательность;
- правильная скобочная последовательность, взятая в скобки одного типа — правильная скобочная последовательность;
- правильная скобочная последовательность, к которой приписана слева или справа правильная скобочная последовательность — тоже правильная скобочная последовательность.
Число правильных скобочных последовательностей
Число правильных скобочных последовательностей из <math>2n</math> скобок (<math>n</math> открывающих и <math>n</math> закрывающих) одного вида равно числу Каталана <math>C_n</math>, что можно вывести несколькими способами:
- <math>C_0 = 1</math> и <math>\qquad C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i}</math> для <math>n\ge 1.</math>
Это соотношение легко получить, заметив, что любая непустая правильная скобочная последовательность <math>\omega</math> однозначно представима в форме <math>\omega=(\omega _{1})\omega _{2}</math>, где <math>\omega _{1, 2}</math> — правильные скобочные последовательности.
- Выражение через биномиальные коэффициенты:
- <math>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>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}</math> При этом <math>C_n = R(0,2n).</math>
Легко показать, что если в скобочной последовательности имеется <math>k</math> типов скобок, то число возможных правильных скобочных последовательностей с <math>n</math> открывающими скобками равно произведению <Math>C_n</math> на <math>k^n</math>. Действительно, для каждой открывающей скобки из <math>n</math> существует <math>k</math> различных вариантов её выбора. Выбор закрывающей скобки однозначно определён уже выбранной парной ей открывающей и не учитывается.
Генерация правильных скобочных последовательностей
Введём теперь лексикографический порядок на скобочных последовательностях. В первую очередь заметим, что открывающая скобка идёт раньше, чем закрывающая; так как скобочная последовательность, начинающаяся с закрывающей скобки, не является правильной. Теперь каждому из <math>k</math> типов скобок присвоим свой лексикографический приоритет. Выбор этого приоритета не принципиален и ни на что не повлияет в ходе дальнейших рассуждений. Поэтому будем считать, что iй тип скобок находится на iй позиции в лексикографическом порядке. Очевидно, что первой последовательностью с <math>n</math> открывающими скобками будет последовательность вида <math>(_1(_1...(_1 )_1)_1...)_1</math>.
