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

can u explain

---

Answered !

---

For this question, I am trying distribution from combinatorics. But it's not working, I tried my best to figure out the reason but couldn't see any mistake, plz tell me what wrong I am doing.

Out of $13$ numbers, root is fixed as minimum (for root i have no choice but to select minimum only.)
Now i have $12$ elements and want to divide into $3$,$3$ and $6$.
Number of ways of doing that = $\frac{12!}{3!\text{ }6!\text{ }3!}$ and i need to multiply with $\frac{3!}{2!}$ to count all combinations of $3$, $6$ and $3$. But i will multiply with $2!$ only because position of $6$ elements is fixed (I can not take distribution like $3$, $3$, $6$ into account). Hence it becomes = $\left \{ \frac{12!}{3!\text{ }6!\text{ }3!} \right \}\times2!$
Now lets work subtrees:-

• For first subtree i have $3$ elements, here also for root no choice but to select minimum out of these $3$ and I left with $2$ elements which can be distributed into $1$ and $1$ in = $2$ ways only.
• Middle Subtree- $6$ elements, Root is fixed, Need to distribute $5$ into $1$, $3$ and $1$. = $\left \{ \frac{5!}{1!\text{ }3!\text{ }1!} \right \}\times2!$. (again i have multiplied with $2!$, Not with $\frac{3!}{2!}$, as positon of $3$ elements is fixed i.e. for this $1$, $1$, $3$ is not valid distribution.).   Now we have to work for inner subtree with $3$ elements of middle tree, for this again root is fixed and I need to divide $2$ elements = $2$ ways.

Total distribution of elements possible for middle tree = $\left \{ \frac{5!}{1!\text{ }3!\text{ }1!} \right \}\times2! \times2$.

• For last subtree: $3$ elements, root is fixed, $2$ ways to divide $2$ elements.

Total number of distribution possible = $\left \{ \frac{12!}{3!\text{ }6!\text{ }3!} \right \}\times2! \times \underbrace{2}_{\text{for first subtree}} \times \underbrace{\left \{ \frac{5!}{1!\text{ }3!\text{ }1!} \right \}\times2! \times 2}_{\text{for middle subtree}}\times \underbrace{2}_{\text{for last subtree}}$

For probability, I need to divide by $13!$, that becomes =

$ \frac{\left \{ \frac{12!}{3!\text{ }6!\text{ }3!} \right \}\times2! \times 2 \times \left \{ \frac{5!}{1!\text{ }3!\text{ }1!} \right \}\times2! \times 2\times 2}{13!} =\frac{12!\times2\times2\times5!\times2\times2\times2}{13!\times3!\times6!\times3!\times3!}=\frac{1}{13}\times\frac{1}{6}\times\frac{1}{3^3}\times4$

Can anyone tell me, why i am getting $4$ extra multiplier ?, where i went wrong ?

---

what is the formula you used for distributing 12 into groups of 6,3, and 3?

---

sir in genral it should be $\frac{12!}{3!\text{ }6!\text{ }3!}\times \frac{3!}{2!}$. bcoz i have to count all permutations of $3$, $6$ and $3$. like -
3, 6, 3
3, 3, 6
6, 3, 3

 omg...I just realized my mistake there while writing this comment. I thought that instead of multiplying by $\frac{3!}{2!}$ i need to multiply by $2$ because position of $6$ is fixed.
But if i fix the position of $6$ then only one combination possible that is $\text{3,6,3}$.
I permuted leftmost and rightmost 3 also :(
got it sir :)
and similarly i am getting one more factor of 2 for middle tree :(
thnks a lot.

---

I still not get the formula- 12 distinct balls to 3 distinct bins problem rt?

---

yes sir, distinct to distinct.
$10$ into 2, 3, 5 then = $\frac{10!}{2!\text{ }3!\text{ }5!}\times 3!$. because we have 3! combinations possible.

but if $10$ to 3,3,4 (here two groups have same number "$3$" ) =  $\frac{10!}{3!\text{ }3!\text{ }4!}\times \frac{3!}{2!}$.

PS:- sir while commenting we never get Latex editor or equation edition, its always simple textbox. Please fix it if possible :)

---

oh okay. yes, by default for comments also its the same editor- may be it is not loading due to slow internet/ browser issue?

---

No sir, Its not for browser or internet. I never got this. But if i edit comment then i always get this.

---

oh. not on mobile rt? I'm geeting it :) and there is no user specific setting for editor on the site.

---

No sir...Its on laptop with chrome browser.
And i talked to one more friend she too always have same issue

---

Tried on chrome too its working for me- but yes, browser can cause that issue. Anyone else facing this? This part is from Q2A core -- so most probably there shouldn't be a bug and secondly if there is, it is much harder to fix.

---

I will see sir, may be some specific problem with my browser only :)

---

If only probability is asked then we can do it directly instead of counting all possible trees.
Probability of getting minimum for root = $\frac{1}{13}$.
Now 3 elements are for leftmost subtree, Minimum will be root. probability of getting minimum out of $3$ is = $\frac{1}{3}$.
6 elements are for middle subtree, probability of getting minimum out of $6$ is = $\frac{1}{6}$.
3 elements are for inner tree of middle subtree, probability of getting minimum out of $3$ is = $\frac{1}{3}$.
3 elements are for rightmost subtree, Minimum will be root. probability of getting minimum out of $3$ is = $\frac{1}{3}$.

combined probability = $\frac{1}{13}\times \frac{1}{3}\times \frac{1}{6} \times \frac{1}{3} \times \frac{1}{3}$

But the problem is more intresting/tough if they ask total number of such trees are possible.

---

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