Число Parenthesizations для фиксированного числа пар «()»

Скажем, мы хотели бы подсчитать количество различных скобок из n пар скобок, но с фиксированным числом пар «()». Как их считать.Число Parenthesizations для фиксированного числа пар «()»

например: для п = 3. то есть 3 пары parenthesizations, если мы хотим, чтобы число parenthizations с к = 2 пар "()" число способов равно 3.

() (())

(())()

(()())

при п = 4, к = 2, то это будет 6

((()()))

() ((()))

(()) (())

(() (()))

((()))()

((())())

источник

2013-10-10 kash

, но каталанский дает общие способы вставить в скобки n пар скобок. Я ищу специальный тип скобок. i.e имеет фиксированное число пар «()». Посмотрите примеры, которые я привел. – kash

Я думаю, что для этого есть аккуратная формула. Я предложил что-то раньше, но это было неправильно. Я работаю над этим, хотя. – Shashank

даже я так думаю. и предыдущий ответ ur предоставили хороший способ взглянуть на проблему. – kash

Я довольно уверен, что это A001263, он же числа Нараяна, и что формула

T(n,k) = C(n-1,k-1) C(n,k-1)/k with 1<=k<=n

Одна из интерпретаций A001263 состоит в том, что T (n, k) - это число n-путей Dyck с ровно k пиками, и каждый шаг Dyck можно интерпретировать как ( или ), и каждый пик как ().

источник

2013-10-11 00:25:27 DSM

Кажется правильным ответом. Можете также спросить, как мы это получим? или вы можете сообщить мне ссылку, в которой объясняется, как эта закрытая форма найдена. – kash

Число Parenthesizations для фиксированного числа пар «()»

ответ

Смежные вопросы