Изменения

Сначала пусть допустимы только скобки '''одного''' типа. Заведём счётчик $\rm depth$ глубины вложенности в скобки, и будем двигаться по последовательности слева направо. Если текущий символ $s[i] (i=0 \ldots 2n-1)$ равен '(', то мы увеличиваем $\rm depth$ на $1$ и переходим к следующему символу. Если же текущий символ равен ')', то мы должны прибавить к ответу $d[2n - i - 1][\rm depth + 1]$, тем самым учитывая, что в этой позиции мог бы стоять символ '(' (который бы привёл к лексикографически меньшей последовательности, чем текущая); затем мы уменьшаем $\rm depth$ на единицу.

Пусть теперь разрешены скобки '''нескольких''' $k$ типов. Тогда при рассмотрении текущего символа $s[i]$ до пересчёта $\rm depth$ мы должны перебирать все скобки, которые меньше текущего символа, пробовать ставить эту скобку в текущую позицию (получая тем самым новый баланс $\rm ndepth = \rm depth \pm 1$), и прибавлять к ответу количество соответствующих "хвостов" - завершений (которые имеют длину $2n - i - 1$, баланс $\rm ndepth$ и $k$ типов скобок). Утверждается, что формула для этого количества имеет вид: