Number of possible min heaps

Question

The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is --------------

According to me, the answer should be 48. The first element 1 is fixed as root. The next level contains elements 2 and 3. The third level contains 4,5,6,7. Therefore, the total no. of cases should be 4! * 2!=48.

But my solution manual says that the answer should be 80.

Am I correct? If not, what am I doing wrong?

Thanks in advance

Answer 1

The flaw in your approach is that you assume that the second level contains only $2$ and $3$. The following examples is min heap with $3$ not in the second level.

     1
   /    \
  2      5
 / \    / \
3   4  6   7

The solution is available here.

Solution: The root of the tree has to be the minimum element, therefore $1$ is at the root.

Now we need to find the possible ways to fill the left and right subtrees with the remaining $6$ elements. Each of the subtrees contain three elements. For the left subtree we can choose $3$ elements from $6$ elements in $\binom{6}{3}$ ways and the remaining three elements fill the right subtree.

Now in each of these subtrees the root would be the minimum of the three elements that comprise each of these subtrees. However, the two lowest elements in each of these subtrees can be interchanged. Therefore each of the subtrees can exists in two different configurations.

Therefore the total possible configurations would be:

$\binom{6}{3} \times 2 \times 2 = 80$.

Answer 2

The second level can contain other numbers than 2 and 3. See for example

      1
     / \ 
    2   5
   / \     
  3   7     
 / \  
4   6

It is also unclear if you count isomorphic trees. See this question for a related answer.