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

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

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

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

Число правильных скобочных последовательностей из ${\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}}$.

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

<?php  function generateBracketsSequence(     int $length,     int $countOpenBrackets = 0,     int $countCloseBrackets = 0,     string $sequence = '', ): void {      if (mb_strlen($sequence) < $length * 2) {          if ($countOpenBrackets < $length) {             generateBracketsSequence(                 $length,                 $countOpenBrackets + 1,                 $countCloseBrackets,                 $sequence . '(',             );         }          if ($countCloseBrackets < $countOpenBrackets) {             generateBracketsSequence(                 $length,                 $countOpenBrackets,                 $countCloseBrackets + 1,                  $sequence . ')',             );         }      } else {         echo $sequence.' - '."\r\n";     }  }  generateBracketsSequence(4);