TIFR CSE 2014 | Part B | Question: 19

Question

Consider the following tree with $13$ nodes.

Suppose the nodes of the tree are randomly assigned distinct labels from $\left\{1, 2,\ldots,13\right\}$, each permutation being equally likely. What is the probability that the labels form a min-heap (i.e., every node receives the minimum label in its subtree)?

• A. $\left(\frac{1}{6!}\right)\left(\frac{1}{3!}\right)^{2}$
• B. $\left(\frac{1}{3!}\right)^{2}\left(\frac{1}{2!}\right)^{3}$
• C. $\left(\frac{1}{13}\right)\left(\frac{1}{6}\right)\left(\frac{1}{3}\right)^{3}$
• D. $\frac{2}{13}$
• E. $\frac{1}{2^{13}}$

Comments

jatin khachane 1

no its not but then how can it be a min heap?

---

@Pranavpurkar It is not standard min-heap they defined their min-heap in the question

min-heap (i.e., every node receives the minimum label in its subtree)

---

Aditya_

ohhh okay got it ! Thanks :)

Answer 1

(C) is Correct - 

Probability = $\frac{Number \ of \ Favorable\ Outcomes(min heaps)}{ Total \ Trees(13!) }$

Now, total Min-Heaps :

Firstly we select minimum element i.e. $1$  for root = 1 way

We have $3$ subtrees  of $3,6,3$ sizes respectively

---

First Subtree with 3 elements:

Steps:

1.  Choose $3$ elements =$^{12}C_3$  ways
2.  Give minimum to root = 1 way
3.  $2$ elements , $2$ children(left & right) = 2 ways { Any of the $2$ elements can be given to left or right child}

---

Second Subtree with 3 elements :

 Steps:

1.   Choose $3$ elements from $9$ left elements = $^{9}C_3$  ways
2.   Similar to above assign these = 2 ways

---

Subtree with 6 elements:{ We already have $6$ elements left now}

$1$ Root , $1$left_most child , $1$ right_most child , $3$ in middle **

Steps:

1. Choose root = 1 way {minimum}
2. Now $5$ elements left, choose leftmost child = 5 ways (choose anyone )
3. Now $4$ elements left, choose right_most child = 4 ways (choose anyone )
4. Now $3$ elements left  for middle :

           a) assign root = 1 way 

           b) assign left and right anyone = 2 ways

---

For, Total Heaps multiply all ways above.

Total probability = $\frac{ Total\ Heaps}{Total\ Trees(13!)}$ 

                          = $\frac{12! \ * \ 2\ *\ 9!\ * \ 2\ *\ 5\ * \ 4\ *\ 2}{13!\ *\ 3!\ *\ 9!\ *\ 3!\ *\ 6!}$

                          = $\left(\frac{1}{13}\right)\left(\frac{1}{6}\right)\left(\frac{1}{3}\right)^{3}$

Comments

I am choosing subtrees of main tree in the following order :1st left subtree then middle subtree and then right subtree

In that case:

1.) $\binom{12}{3} * 2$ (left subtree)

 2.) $8 * 7$ (middle subtree's immediate left and right as only 8 are left after choosing root) and $5 * 4$ (choosing left and right of middle subtree's subtree as only 5 are left after choosing its root)

3.)Now the right subtree of main tree have 3 elements left which can be done in 2 ways after choosing root.

The total comes out : $\frac{1}{3}*\frac{1}{6}*\frac{1}{{3}^{3}}$ (option C is correct this way also)

---

himanshu sir bahut pyara explain kiya hai shukriya

---

sachin sir, the method that you are using is taught in coaching.

i have seen that video of distributions.

it was amazing

wow

Answer 2

OPTION C IS CORRECT.

Lets apply (divide and conquer ) to this problem.

First divide this problem into sub problems. like 

---

Caption

Answer 3

Since its a min heap the root will always have the smallest element possible which is 1 here . Now we see there are 3 subtrees , out of which the leftmost and right most can have any of the 12 elements arranged in this order :  Say we chose L1,L2,L3 for first time since they are unique integers there is only one way to arrange them in ascending order L1>L2>L3 . In this case L1 becomes the root , L2 and L3 are the children . Since L2 and L3 can interchange their position we have 2 choices for L2(left) , L3(right) OR L2(right) , L3(left) .

So it becomes 12C3*2

For the Second subtree we apply the same thing : 9C3*2

We are now left with 6 more element for the middle subtree .

Now again the root of the middle subtree will contain the minimum element among all the 6 which we can choose in 1 way only . Now we are left with 5 elements.

               Leftmost and rightmost child  of the middle subtree can contain any of the 5 elements in 5C2 * 2 ways .

                We are left with only 3 elements in which root is again assigned minimum among 3 nodes in 1 way and the

                 children can interchange in 2 ways .

So total becomes : (12C3 * 2) * (9C3 * 2) * (5C2*2) * 2 = 2956800 combinations will have min heap structure .

Total possible permutation is 13!.

So the probability becomes : 2956800/(13!) = 0.00047483 .  which matches with option C . Hence option C is the answer.

Answer 4

Total = 13!

G1 (given to 1st subtree) =¹²C₃

G2 = ⁹C₆

G3= ³C₃

Required= 1* ¹²C₃ * ⁹C₆ * ³C₃ * A1 * A2 * A3

A1 ( Arrange 1st subtree) = 2

A2= 1* ⁵C₃ * 2 * 2 

i.e. A2 = 1 * G22 * (A21,A23) * A22

A3 =2

Ans = (C)

Comments

for A2 it will be 5c1*4c3*2*1