1个回答
-
卡特兰数,也称为加泰罗尼亚数,是一系列经常出现在组合数学中各种计数问题中的数字。 以比利时数学家欧仁·查理·加泰罗尼亚(1814-1894)的名字命名。
设 h(1) 1, h(0)=1,加泰罗尼亚数满足递归公式:
h(n) = h(0)*h(n-1)+h(1)*h(n-2) + h(n-1)h(0)(其中 n>=2)。
替代递归:
h(n)=((4*n-2)/(n+1))*h(n-1);
这种递归关系的解是:
h(n)=C(2n,n)/(n+1) (n=1,2,3,..用给定节点组成二叉树的问题。
给定 N 个节点,可以形成多少个不同的二叉树? (可构成h(N))。
相关回答