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

这个问题被标记为家庭作业，所以我要找到一般情况下的确切数字由您来决定。