Олимпиадное задание по комбинаторике
У меня вопрос на счет возможных вариантов размещения скобок разными способами. В чем суть: У меня дано N открытых и N закрытых скобок. Нужно посчитать количество разных вариантов закрытия скобок, при том, что возможно K разных стилей скобок((), [], {} т.д.)
Например:
N = 2, K = 2; — ([ ]), [()], т.д. - как результат мы получили такие варианты (всего их 8))
Вопрос к вам: Какая формула решения этой задачи или вообщем алгоритм?
Ответы (1 шт):
Если не ошибаюсь, то исходим из того, что правильных скобочных расстановок из N пар скобок можно сделать в количестве чисел Каталана:
Если разновидностей скобок K, то для каждой расстановки мы их можем расставить 
способами.
Итого общее количество -
способов правильных расстановок.
Для N=2, K=2: 2^2*(6-4)=4*2=8...
"По-моему, так." (с) Пух
Литература: Д.Кнут, Искусство программирования, т.4а, раздел 7.2.1.6.
Поскольку вопрос о генерации всех расстановок скобок не ставился, код не писал.