use*_*663 5 math combinations catalan
我有一个有趣的组合问题,我有点卡住了
让我们定义一个函数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\n您可以选择 n-1 个求和中的任意一个作为根节点。让我们选择第 k 个求和。根的左侧有 k 个变量，因此可以以 P(k) 种方式组织左子树。右边有nk个变量，所以右子树可以用P(nk)种方式组织。因此，总的来说，您可以以 P(k)P(nk) 种不同的方式组织树。
\n\n由于您可以从 1 到 n-1 中自由选择 k，因此您可以组织具有 n 个叶子的表达式树的总数为：
\n\nP(n) = P(1)P(n-1) + P(2)P(n-2) + \xc2\xb7\xc2\xb7\xc2\xb7 + P(n-2)P(2) + P(n-1)P(1)\n正如 @DSM 在评论中指出的，这种递归关系生成加泰罗尼亚数字。有一个封闭形式的解决方案，但从递推公式推导有点棘手。您可以在维基百科的加泰罗尼亚数文章中找到该公式的几个证明。解决办法是：
\n\nP(n) = C(2n,n)/(n+1) where C(n,k) = n! / (k!(n-k)!)\n