algorithm - 来自 1..n 的二进制堆数

Question

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

Example: 1 2 3 4

有效的最小堆是：{1 2 3 4}, {1 3 2 4}, {1 2 4 3},

因此答案是 3

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
...

这个问题被标记为家庭作业，所以我将由你来寻找一般情况的确切数字。