ACE_DS_2019

Question

explain me briefly what is valid stack stack permutations ?

Comments

Answer is D

---

@Somoshree why is it invalid?

---

No D )

Total permutation - valid stack permutation  :3

---

srestha maam sorry the answer is D..I solved this by eliminating the options..

Consider the sequence of 3 inputs 1,2,3.

The invalid stack combinations for this sequence of input is 3,1,2 since if inputs arrives in the order 1,2,3, after u push 1,2,3 into the stack and try popping them out, then after popping out 3, there is no way u can pop out 1 before popping out 2. So this is an invalid permutation..

Consider any other permuation of these 3 elements, u will get valid permutations. Valid permutations means that if the input arrives in some order, then a permutation of those input symbols is valid only if there is a way to pop out the elements in that order from stack after pushing them in the order that they arrived.

---

Magma yes..typo :P

---

yeah hit and trial is  best way to doing this type of question

but how they form a general equation = $\frac{\binom{2n}{n}}{n+1}$ ?? :3

---

Nice question! Total no. of stack permutations is n! and no. of valid stack permutations is actually Catalan number. So invalid stack permutations is Total Stack Permutations - Valid Stack Permutations 

---

Hit and trial method is also a long procedure nah ??

fist valid stack permutation of 1 2 3  (now 1 , 2 ,3 are arranged in 3! = 6 ways )

means 6 different conditions are formed ??

In each condition we find the valid stack permutation ??

---

Magma u will pick each of the 6 combinations one by one and see whether it is valid or not provided the input comes in the sequence 1,2,3..if it is valid then it becomes a valid stack permutation. I guess this takes much lesser amount of time rather than trying to derive the equation given :3

---

Magma Deriving a generic formula for valid stack permutations isn't easy and neither is it explained in any of the standard books. I remember this formula from the various applications of Catalan number I read here : https://www.geeksforgeeks.org/applications-of-catalan-numbers/. I recommend going through this , it will be of use for solving various other problems too in which Catalan number has been applied directly 

---

@somoshree supppose in exam if asked in NAT that find no of invalid stack permutation for  inputs , then it will obvioulsy take a long time to deive using hit and trial method