94
правки
Изменения
Нет описания правки
== Лексикографический порядок порядок правильных скобочных последовательностей ==
Для того чтобы определить лексикографический порядок для правильных скобочных последовательностей будем интерпретировать открывающуюся скобку как "$0$", а закрывающуюся как "$1$"(**). Тогда первая последовательность с n открывающимися скобками будет иметь вид:
{| border="1" cellpadding="3"
что соответствует самому большому возможному числу.
Для последовательностей с разным типом скобок надо определять свой порядок, например "$($"<"$[$"<"$)$"<"$]$".
''Примеры лексикографического порядка для $n$ и $k$, где $n$ - число открывающихся скобок, а $k$ - число видов скобок''
$C_0 = 1$; {{---}} так как существует только одна скобочная последовательность с 0 открывающихся скобок - пустая
$C_n = \sum_{i = 1}^{n - 1} C_i * C_{n - 1 - i}$.
Это соотношение легко получается из (*). Для этого надо перебрать все возможные последовательности $d_1$ и $d_2$, являющиеся правильными скобочными последовательностями, такие, что $(d_1)d_2$ образуют новые правильные скобочные последовательности необходимой нам длины.
== Алгоритмы для генерации следующей правильной скобочной последовательности в лексекографическом порядке и самого лексикографического порядка ==
