WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}}}$

При этом ${\displaystyle C_{n}=R(0,2n).}$

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

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

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

Для улучшения этой статьи желательно: Исправить статью согласно стилистическим правилам Википедии. Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное. Проверить достоверность указанной в статье информации.