Как рассчитать все возможные комбинации порядка скобок

Question

Хотелось бы найти формулу для расчета максимально возможных комбинаций порядка скобок.

Прежде всего, есть несколько правил: - скобки должны быть действительными (каждая скобка имеет закрывающую скобку) - n% 2 == 0 (n = скобки, только пары) - Порядок чувствителен, например: a, b и b, a равняется 2 комбинациям

Что такое допустимая комбинация? Допустим, n - это наша переменная для количества скобок:

n = 2: () - Возможна только 1 комбинация

n = 4 () (), (()) - возможно только 2 комбинации

n = 6 ((())), () () (), (() ()), (()) (), () (()) - 5 возможных комбинаций

Теперь есть идеи, как рассчитать число комбинаций, когда у меня только n =?

Привет

Answer 1

Вы можете рассчитать количество допустимых комбинаций, используя табличный подход.

Одно измерение таблицы относится к общему количеству скобок в последовательности, второе измерение относится к числу левых скобок, поэтому ячейка таблицы может быть обозначена как F(a, l).

Вы можете добавить правую скобку в последовательность, если 2 * l > a

Вы можете добавить левую скобку в последовательность, если 2 * l < n

Так заполните ячейку таблицы за ячейкой и получите результат какF(n, n/2)

Существует известная формула (каталанский) для числа допустимых последовательностей скобок, но я полагаю, что вы должны рассчитать ее с помощью простой математической логики.