How many different heaps can we build from $n$ elements? We the group $[n]=\{1,2,....,n\}$.
How many heaps can we build for $n=4,5,6,7$??
Important: The question is not about the building heap algorithm, is about how many heaps can we built for each number of elements.
Thank you! 
 A: $3,8,20,80$  These are given in OEIS A0506971 which is the first result if you search for heap.  An algorithm is given for calculating the numbers.
A: Iv'e come to something like this...
Let's start with n = 6.
you have 6 in the root, you have heap of size 3 as the left child of the root, and a heap of size 2 as the right child of the root.
if you choose 3 elements of the 5 remaining (6 is in the root) for the left heap, you have
(5 choose 3) options, from each set you can build 2 heap.
so that's (5 choose 3) * 2 = 20
Now notice that for the 2 remaining elements for the right heap. there's only one option so that doesn't add options..
for n=7: same thing.. (6 choose 3) *2 for the left heap..
now you have 3 elements remaining. There are only 2 options to build this heap..
so (6 choose 3) *2 * 2 = 20 *4 = 80.
I think the recurrence is: 
(n-1 choose number of elements in left heap) * (number of heaps you can build from these elements) * (number of heaps in the right sub tree)..
or something like this it's not 100%...
good luck..
