algorithm - 固定数量的“（）”对的括号数

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 步骤解释为(或)，每个峰值解释为()。