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

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