The number of binary heaps from 1..n

Question

Given integers from 1 to n, determine how many regular binary heaps can be built with these numbers.

Example: 1 2 3 4 

valid minimum heaps: {1 2 3 4} , {1 3 2 4} , {1 2 4 3} ,

So answer 3

Answer 1

hint

:

A binary heap has a predetermined number of nodes and a well-defined structure (full tree)
Think of this problem recursively.

"Choose" which of the numbers other than the roots goes into the left subtree, and from the right - and recursively call on the subtrees.

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

The question is marked as homework, so I leave the exact numbers for the general case to you.