Количество способов правильно организовать скобку

Question

Я думал некоторое время об этой проблеме:

Что число способов правильно * устраивая 2 * п скобкой.
* Правильно подобранная последовательность скобок имеет равное количество открытых и закрытых круглых скобок на ее конце и большее или равное количество открытых круглых скобок, чем закрытые по всей последовательности.

Например, для n=3, есть 5 пути: ((())),()(()),()()(), (())(), (()()).

Я думал о том, чтобы представлять вложенные круглые скобки как деревья, но далеко не ушел.

Answer 1

Ваш пример эквивалентен количеству Dyck words, которые можно пересчитать с комбинаторикой и будет равно Catalan number: