1..n之间的二叉堆数量

Question

给定从1到n的整数，确定可以用这些数字构建多少个有效的二叉堆。

Example: 1 2 3 4

有效的最小堆包括：{1 2 3 4}，{1 3 2 4}，{1 2 4 3}，

因此答案是3。

- candyman

---

有趣的问题...你能给我们展示一下你目前为止尝试过什么吗？如果你分享你的工作，我们更有可能找到一个解决方案。 - Kevin

不是很多...我尝试过将其与二叉树的数量联系起来，即卡特兰数，但迄今为止没有成功。 - candyman

如果你在 http://mathworld.wolfram.com/ 上进行了一点搜索... - lavin

搜索整数数列在线百科全书，以查找http://oeis.org/A056971。 - Colonel Panic

Answer 1

提示：

二叉堆拥有预定义的节点数量和完整树结构。 关于这个问题，可以采用递归思想。 选择非根节点中哪些属于左子树，哪些属于右子树，并对子树进行递归操作。

f(1) = 1 //no sons
f(2) = f(1) * 1 //one son and a root
//chose which element will go to the left sub-tree, and recursively invoke.
f(3) = Chose(2,1)* f(1) * f(1) * 1 
f(4) = Chose(3,2)*f(2) * f(1) * 1 //chose which 2 elements will go to the left sub tree
...

这个问题标记为作业，所以我将寻找一般情况的确切数字留给您。

- amit