我有一个有趣的组合问题，我有点卡住了
让我们定义一个函数 p(xn)，它返回方程 x 的 '()' 的数量 现在 x 只能是 x1 + x2 + x3 ... xn 这个函数定义为 n >=2
例子：
P(x2) = (x1 + x2) = 1
p(x3) = ((x1 + x2) + x3) 和 (x1 + (x2 + x3))
p(x4) =
((x1 + x2) + (x3 + x4))
((((x1 + x2) + x3) + x4)
((x1 + (x2 + x3)) + x4)
(x1 + ((x2 + x3) + x4))
(x1 + (x2 + (x3 + x4)))
等等 注意 (x1 + (x2 + x3) + x4) 不是一个有效的例子，每个 + 必须有一个 ()
现在，我试图想出一个 P 的公式来确定组合的数量我不确定是否有一个固定的公式或依赖于其先前术语的递归定义。各位大佬能帮我看看公式吗？
基本上，您正在寻找唯一的二叉表达式树的数量，其中节点是求和，叶子是 x 1到 x n。我们称这个数为 P(n)。
您可以选择任何 n-1 个求和作为根节点。让我们选择第 k 个求和。根的左边有 k 个变量，所以你可以用 P(k) 的方式组织左子树。右边有 nk 个变量，所以右子树可以用 P(nk) 种方式组织。因此，总的来说，您可以以 P(k)P(nk) 不同的方式组织树。
由于您可以从 1 到 n-1 自由选择 k，因此您可以用 n 个叶子组织表达式树的总数为：
P(n) = P(1)P(n-1) + P(2)P(n-2) + ··· + P(n-2)P(2) + P(n-1)P(1)
正如@DSM 在评论中指出的那样，这种递归关系生成了加泰罗尼亚数字。有一个封闭形式的解决方案，但从递归公式推导出来有点棘手。您可以在加泰罗尼亚数字的 Wikipedia 文章中找到该公式的几个证明。解决方案是：
P(n) = C(2n,n)/(n+1) where C(n,k) = n! / (k!(n-k)!)