Heaps

Question

How many Binary Max-Heaps can be constructed from the elements {1,1,2,2,3,3,4,4} ?

Comments

$\frac{8!}{8.4.3.2.1.1.1.1}=210$

---

But answer given is 44

---

here 4,4 cannot permuted
but 4,3 can be permuted as root of second highest subtree
but in case of 3,4 children also restricted

---

for (1,1) there will be 1 tree

for (2,2,1,1) there will be 2 trees

for (3,3,2,2,1,1) there will be 6 trees

for (4,4,3,3,2,2,1,1) there will be (4,4,3,3,2,2,1,1)

(4,4,3,2,3,2,1,1),(4,4,3,3,1,-,-,-),(4,4,3,1,3,-,-,-),(4,4,3,2,1,-,-,-),(4,4,3,1,2,-,-,-),(4,4,3,2,2,-,-,-)

Now also in 2nd highest level there are also 3 combinations

(4,3,4,-,-,-,-,-)

(4,4,2,-,-,-,-,-)

So, I think it will be more than 44

---

@ma'am i think question asks for possibilities of heap considering all elements together.

---

im getting 40

Answer 1

Possible max heaps are 44

So as we have 4 nodes , those can be arranged in 4! ways but 2 similar nodes are their (2,2 and 1,1)

so total number of ways =4!/2!*2!   =  6 ways  

Node 3 can be placed in 3 positions 

For 2,1,1 we have 3 nodes(positions) after placing Node 3 and they can be arranged in 3!/2! ways because we have similar node 1

So totally we have 3* 3!/2! = 9 ways 

If 1 is left child of 4 then other 1 must be child of node 1 as we cant place 2 or 3 in that position

So we have 3 positions

2,2,3 can be arranged in 3!/2!  = 3 ways    

Total possibilities =6+9+3 =18 ways

All these above ways can also be for this heap

6+9+3 ways   =18 ways 

In this we are left with 3 positions for 2,1,1 this can be arranged in 3!/2! =3 ways 

Same as above In this we are left with 3 positions for 2,1,1 this can be arranged in 3!/2! =3 ways 

generally as we have 3 positions and 2,1,1 is to placed we consider 3!/2! = 3 ways but 2 cant be child for 1 so we avoid this possibility then we are left with 2 ways   

By adding all these possibilities we get 18+18+3+3+2 =44 ways

Comments

ma'am in first figure 2nd part.. 3 can be paced in upper 3 positions so 3 possibility but why 2! . Doesn't it will be like this.. now we left with 2,1,1 so it will be 3!/2!

---

yes ur correct thank u let me change

in next one where 1 is left child of 4 then we have only 3 posibilities

Let me know if im wrong

---

@shivani

why 4!/2! at first

elaborate more in words

---

@sresta I tried to explain in detail you can check it now and let me know if anything wrong

---

I agree with u :)

---

@ Balaji Jegan