made easy 2018

Question

How many permutations can be obtained in the output using a stack assuming that the input 1,2,3,4,5,6 such that 3 will be popped out from stack at 3rd position ?

3 will be popped out from stack at 3rd position

 what does this mean?? 

1) third pop operation performed should be of 3

2)3 is at third position while pushing into the stack

really confused , pls help

Comments

If the abswer is 120, then it must be wrong... due to with 6 elements we get 132 stack orders, in that 120 orders have 3 as their third element is impossible

---

this is what they have given.

---

the explanation which they provided is entirely wrong... check my approach !

Answer 1

3 should be at third pop, before that we have to do two pop operations.

I) fix the first pop operation as 1, then

            i) fix the second pop operation as 2, ===> remaining three elements i.e., 4,5 and 6 lead to $\frac{\binom{2n}{n}}{n+1} = \frac{\binom{6}{3}}{4} = 5 $

            ii) fix the second pop operation as 4, ===> remaining three elements i.e., 5,6, and 2

                  5 and 6 yet to be pushed but remember 2 is in stack ===> lead to $\frac{\binom{2n}{n}}{n+1} = \frac{\binom{6}{3}}{4} = 5 $

 

           iii) fix the second pop operation as 5, ===> if 2$^{nd}$ pop is 5, then third pop should be 4 ===> invalid case

                  WHY ?

                     4 is pushed after 3, 5 is pushed after 4 ===> 4 is lie between 3 and 5, then without poping 4, you can't pop 3.

           iv) fix the second pop operation as 6, ===> if 2$^{nd}$ pop is 6, then third pop should be 5 ===> invalid case

 

II) fix the first pop operation as 2, then

            i) fix the second pop operation as 1, ===> remaining three elements i.e., 4,5 and 6 lead to $\frac{\binom{2n}{n}}{n+1} = \frac{\binom{6}{3}}{4} = 5 $

            ii) fix the second pop operation as 4, ===> remaining three elements i.e., 5,6, and 1

                  5 and 6 yet to be pushed but remember 1 is in stack ===> lead to $\frac{\binom{2n}{n}}{n+1} = \frac{\binom{6}{3}}{4} = 5 $

 

           iii) fix the second pop operation as 5, ===> if 2$^{nd}$ pop is 5, then third pop should be 4 ===> invalid case

                  WHY ?

                     4 is pushed after 3, 5 is pushed after 4 ===> 4 is lie between 3 and 5, then without poping 4, you can't pop 3.

           iv) fix the second pop operation as 6, ===> if 2$^{nd}$ pop is 6, then third pop should be 5 ===> invalid case

 

III) fix the first pop operation as 4, then

            i) fix the second pop operation as 5, ===> remaining three elements i.e., 1,2 are in stack and 6 is yet to be pushed

                     then possible, 1 should be after 2 and 6 can be any where ===> 3 orders

                     i.e., 2 1 6  ,  2 6 1  and  6 2 1

          iv) fix the second pop operation as 6, ===> if 2$^{nd}$ pop is 6, then third pop should be 5 ===> invalid case

   Note you can't pop either 2 or 1 as second pop, due to 3 is pushed on those 2 elements

 

IV) fix the first pop operation as 5, then second pop operation should be 4, to get third pop operation is 3

            ===> remaining three elements i.e., 1,2 are in stack and 6 is yet to be pushed

                     then possible, 1 should be after 2 and 6 can be any where ===> 3 orders

                     i.e., 2 1 6  ,  2 6 1  and  6 2 1

Total = I + II + III + IV = ( 5+5 = 10 ) + ( 5+5 = 10 ) + 3 + 3 = 26

Comments

II) fix the first pop operation as 1, then

            i) fix the second pop operation as 1, ===> remaining three elements i.e., 4,5 and 6

pls chk is it a typo? i think first pop operation should be 2 here!

---

is it a default assumption?

yes.

 

pls chk is it a typo? i think first pop operation should be 2 here!

yes, it is a typo.. updated !

 

Finally, you got it or not ?

---

yes finally i got it!! amazing explanation!!! hat's off  seriously!!

actually I was checking that why u took only 3 ways for case III and case IV ;

i was writing all the ways for popping elements in case I and case II to check why u didnot followed the same idea there!!

now i got this amazing explanation!!

thanks for spending your valuable time on this question!!