How many different heaps can we build from $n$ elements?

Question

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!

Answer 1

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

Answer 2

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