Here i m generalizing it with an example....
suppose i have a min heap like this
assume root at level zero hight of this heap is k=3
The smallest element has to be placed at the root of the heap. After that we split up the remaining elements into the two subtrees and recursively compute the number of binary heaps that they can make. The trickiest part here is that the two subtrees don't have necessarily have the same number of nodes (unless N is 1 less than a power of two).
We fill the tree in breadth first order which means that nodes in the lowest level will go to the left subtree first and then any excess nodes will be in the right subtree.
suppose that at last level there r m nodes nd total nodes=n
hence n=2k-1 +m
in above tree k=3 m=7 so n=2k-1 +m=8-1+7=14
or we can say that m=n-2k+1
now calculate number of elements in the left subtree as L ?
we now that before last level every level is complete and nodes r equally distributed into left subtree nd .right subtree.
so no of nodes befor last level in left subtree or.right subtree.=p
now we know that befor last level total nodes=2k-1 now leave root now total nodes=2k-2
these total nodes 2k-2, is equally distributed into left subtree nd .right subtree.
hence p=(2k-2)/2=2k-1 -1
now suppose number of elements in the left subtree as L and number of elements in the right subtree as L
L=p+min(2k-1,m ) R=p+max(0,m-2k-1)
expalanation for L=p+min(2k-1,m ) R=p+max(0,m-2k-1)
For L=p+min(2k-1,m ) R=p+max(0,m-2k-1)
there r 2 cases
case-1
if our lst part is not complete then it ll surely have m elements in left sub tre part=no of nodes at last level so if all nodes at last level comes in lst part so there r o nodes in rst part it gives
L=p+min( ,m ) R=p+max(0, )
case 2
if our lst part is complete nd there r some nodes also in rst part
so for lst part 2k/2=2k-1 nodes in lst part at last level nd rest nodes out of m ie m-2k-1 will be on rst part at last level
L=p+min(2k-1, ) R=p+max( ,m-2k-1)
now by cobining case 1&2
L=p+min(2k-1,m ) R=p+max(0,m-2k-1)
Returning to the original problem you can calculate f(n), the number of binary heaps with n distinct elements, as f(n)
f(0)=1, f(1)=1
f(n)=n-1CLf(L)f(R)
this is generating series (1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600)
http://oeis.org/A056971
f(7)=80
p.s. https://www.quora.com/How-many-Binary-heaps-can-be-made-from-N-distinct-elements
----------------------------------------------------------------------------------------------------------------------------------------------------------------
if we have our min heap as complete binary tree then this method makes it mor simpler bcoz for a complete binary tree for every node its left sub tree nd right sub tree is also complete binary tree with same no of nodes in lst and rst nd they have also same no of binary min heaps means f(L)=f(R)
suppose n=15 means it is complete as 24-1=15, k=3
L=R=2k-1=7
f(15)=14c7 *(f(7))2
f(7)=6c3*(f(3))2
f(3)=2c1*(f(1))2
f(1)=1