MadeEasy Test Series: Combinatory - Permutations And Combinations

Question

MY SOLUTION :

Fix the root

then next level 2 elements ( 2! possibilities)

next level 4 elements( 4! possibilities)

last level 2 elements ( 2! possibilities)

total possibility = 2! * 4! * 2! = 2 * 24 * 2 = 96

what went wrong ?

just in case if the question in image is not clear

question -which of the follwing represents the total number of ordering possible with elements 12,10,8,5,3,2,1,7,9 such that if node of above graph is filled with these elements it satisfies max heap property

a)96

b)896

c)2688

d) none

Comments

https://stackoverflow.com/questions/11845126/number-of-binary-heaps-from-1-n

---

@higgs

not clear....can you explain a bit more

---

somebody answered it please check -->  https://www.facebook.com/photo.php?fbid=165962520700365&set=gm.740331136172099&type=3&theater

---

I'm just elaborating the ans. given here: https://stackoverflow.com/questions/11845126/number-of-binary-heaps-from-1-n

---

n=1: {1}                                                 1  Max heap possible.

---

n=2   {1,2}                2 (parent)             1 Max heap possible.         

                                   |

                                  |

                                 1 (child)

---

n=3 {1,2,3}              3                                 3                                2 Max heaps possible

                              /      \                          /         \

                           1         2                     2            1

We can observe largest element will always be present at the root.

---

n=4 {1,2,3,4}             Let's pay a bit attention to the structure of the max heap with 4 nodes.

                                   It will be something like this:

                                               O

                                           /        \

                                       O            O

                                    /

                                 O

From our observations we have seen that the largest element will be placed at the root.

Therefore, we are sure that heap will be something like this:

                                              4

                                           /        \

                                       O            O

                                    /

                                 O

---

---

(contd.)

What to do next??

    --- We know that, If M is a Maxheap, then its left and right subtrees also need to be max heaps.

Let's focus on left subtree now.

                                              4

                                           /        \

                                       O            O

                                    /           

                                 O             

We have 3 elements remaining {1,2,3} //4 has been already been selected as the root of the original tree.

Our subtree is madeup of 2 elements.

We already know, max heaps possible with 2 elements  = 1

Let's put all this together.

           We need 2 elements to construct our left subtree.

           we have 3 elements.

           We have $\binom{3}{2} ways$ of choosing 2 elements from 3 elements and build our left subtree.

          (Only condition on left subtree is that it should be a max heap itself.)

          i.e. no. left subtrees that are max heaps = $\binom{3}{2} ways$ . No. of max heaps with 2 elements.

                                                                            = $\binom{3}{2} ways$ . f(2)

                                                                            = $\binom{3}{2} ways$ . 1

                                                                            = 3

       i.e. our 3 possible left subtrees are:

                                                       3                   3                2

                                                      /                     /                /

                                                   1                    2                1

---

---

---

(contd.)

---

Now we are left with one element only.

       No. of possible right subtrees = $\binom{1}{1} ways$ . No. of max heaps with 1 elements.

                                                       = 1 . 1

                                                       = 1

---

i.e. No. of max heaps with 4 elements = 1 . $\binom{3}{2}$ . f(2) . $\binom{1}{1}$ . f(1)

                                                                  ^        ^      ^

              1 way to  Choose root _________|          |        |

 No. of ways to choose elements in left subtree|        |

            No. of max heaps possible in left subtree____|         and so on.....

i.e. 3 possble max heaps with 3 elements are:

            4                                               4                                        4                                                                                   

         /     \                                          /    \                                     /   \                                

      3        1                                     2       3                                3     2                                        

    /                                                /                                           /                                       

 2                                                1                                          1                               

---

(contd.)

---

n = 5 {1,2,3,4,5}     We know maxheap with 5 nodes will be something like this:

                                               5   //we know largest element will be selected as root.

                                           /        \

                                       O            O

                                    /    \

                                 O      O

No. of max heaps = 1 . $\binom{4}{3}$f(3) . f(1)

                              = 4 . 2. 1

                              = 8

---

n = 6 {1,2,3,4,5,6}     We know maxheap with 6 nodes will be something like this:

                                               6   //we know largest element will be selected as root.

                                           /        \

                                       O            O

                                    /    \           /

                                 O      O       O

No. of max heaps                                  = 1 . $\binom{5}{3} .  $f(3) . f(2)

                                                                  ^   ^       ^       ^
                                                                           \
              1 way to  Choose root _________|        |      |        |

No. of ways to choose elements in left subtree|    |        |

       No. of max heaps possible in left subtree____|         |

            No. of max heaps possible in right subtree__ ___|

                              = 1. 10 . 2. 1

                              = 20

and so on....
 

---

Can you solve the given problem now??

---

@higgs

beautiful :) thanks

---

@ A_i_$_h  What is the anwer given?

---

@ Higgs

Explanation is too good...thanks...

---

vishal...896 is correct

---

@hs_yadav

How it is correct ?

---

i think u got it?

---

It does not have explanation. I know answer i need explanation.

---

Answer: 896

---

I got 200

what's the answer given ?

---

896

---

i m getting 224 ?

---

$\frac{9!}{9*5*3*3*1*1*1*1*1}=896$

https://www.youtube.com/watch?v=1U3loHkX5XE&feature=youtu.be&t=2260

follow this he derived this formula beautifully. 

---

@Shubhgupta

Can you share exact time in video its 1hr video

---

just play brother it will play from that point only and watch from 40:00.

---

@ShubhguptaBut why isn't 2018 question following this logic as for that also we could have only 1 structure but the ans for it is 80

 

---

just check the beautiful explanation by KAPIL sir https://gateoverflow.in/102171

if you have still doubt then comment !

---

@Markzuck

it is working for 2018 examples also they asked # of min heaps ..so we have to consider CBT structure with 7 nodes

                    O

           O                  O

O                O   O                O

7! / 7*3*3*1*1*1*1 = 80

---

@Shaik Masthan sir,
So is Kapil sirs solution always results same as the above logic?
Means write n!/ N1*n2 and so on
Means dividing with the product of all the size of each node subtree?

---

https://gateoverflow.in/199006/max-heap-counting

---

just wow for this guy

Answer 1

Given Elements : 12,10,8,5,3,2,1,7,9

1) Maximum of all these will be root i.e. Root = 12 ---->1 way --->(1)

2) Remaining : 8 elements

Out of 8 choose 5 for left subtree in 8C5 ways and 3 for right subtree in 3C3 ways. --->(2)

3)Left Subtree :

Out of 5, maximum element is the root.

Out of remaining four , choose 3 for left subtree in 4C3 ways , Out of 3 elements chosen, max is root and rest 2 can be in any of the 2 leaf nodes.

#Heaps possible in Left Subtree= 4C3 * 2 --->(3)

3)Right Subtree :

Out of 3, maximum is root.

Remaining 2 elements can be arranged in 2 leaves in 2 ways.

#Heaps possible in Right Subtree=  2 --->(4)

Hence From (1) to (4) , Total # heaps possible = 1 * ( 8C5 * 4C3 *2 )  * (3C3 * 2 )

=56 * 4 * 2 * 2 =896 (ANS)

Answer 2

The total number of ways we can arrange data in 9 nodes = 9!

Divide it be the number of descendants each node has including itself.

Like root has 8 descendent + itself so we have divided by 9. 

Source: https://youtu.be/1U3loHkX5XE?t=2260

Comments

Thanks

Really helpful source.

Answer 3

Given Elements : 12,10,8,5,3,2,1,7,9

1) Maximum of all these will be root i.e. Root = 12 ---->1 way --->(1)

2) Remaining : 8 elements

Out of 8 choose 5 for left subtree in 8C5 ways and 3 for right subtree in 3C3 ways. --->(2)

3)Left Subtree :

Out of 5, maximum element is the root.

Out of remaining four , choose 3 for left subtree in 4C3 ways , Out of 3 elements chosen, max is root and rest 2 can be in any of the 2 leaf nodes.

#Heaps possible in Left Subtree= 4C3 * 2 --->(3)

3)Right Subtree :

Out of 3, maximum is root.

Remaining 2 elements can be arranged in 2 leaves in 2 ways.

#Heaps possible in Right Subtree=  2 --->(4)

Hence From (1) to (4) , Total # heaps possible = 1 * ( 8C5 * 4C3 *2 )  * (3C3 * 2 )

=56 * 4 * 2 * 2 =896 (ANS)

Answer 4

 Consider element 12,10,8 and given B-tree. Find no.  of possible max-heap possible.                                                                                         

 

We have to find no. of possible max heap in this tree.We know that arrangements are 10,12,8 and 8,12,10    Mathematically, it should have been 3!, but what we are doing is  we are fixing 12 at position 2nd of array.

 ∴ We have to divide it by 3 to reduce what we earlier have multiplied to each element as we have now fixed one of them.

∴ no. of total possible arrangement after fixing = 3!/3 = 2

          

 Again we will take 4 elements 10, 3, 4, 8 and a B-tree Find  no. of max-heap possible.

 

 

 

sol :  We will our intuition and logic as this problem is problem is small to draw all possible b-tree to be able to fill our max-heap requirements.

      So, given is our three required Max-heap.     Mathematically, we will try. For 4 element total arrangement is 4!

   Now, in max-heap at any subtree root must have highest of all it’s node. So first we will fix largest of all element i.e. ‘10’ to top. Which make us divide by 4 to earlier 4! as element 10 must have multiplied to give 4! arrangements. But note 10 is fixing at a particular position in normal array it is position 3 which lead to 2 subarray. One having 2 element and second having 1 element. Now again we have 2 seat to left of element 10. Position 2 seat i.e. just left of root (10) will again occupy the bigger among two. So again we have to divide by 2 to above 4!. Now we are left with 2 subtree with each 1 element.

So. Total possible max-heap in this arrangement = 4!/4.2.1.1 = 3

So, Concept is in this type of question that first take n! then divide by n and then keep dividing by no. of nodes in subtree of each node starting from root.

So coming back to our question we will get :

          ∴    Possible no. of Max-Heap possible =     9! / 9.5.3.3 = 896