固定数量的"()"对的括号数

Question

假设我们想要计算n对括号的不同括号的数量,但是具有固定数量的"()"对.我们如何计算这些.

例如:对于n = 3.即3对括号,如果我们想要具有k = 2对"()"的父亲的数量,则路数为3.

()(())

(())()

(()())

对于n = 4,k = 2,它将是6

((()()))

()((()))

(())(())

(()(()))

((()))()

((())())

Answer 1

我很确定这是A001263，又名 Narayana 数，公式是

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

A001263 的一种解释是 T(n,k) 是恰好具有 k 个峰值的 Dyck n 路径的数量，您可以将每个 Dyck 步骤解释为 或 ，将(每个)峰值解释为()。