0 votes 0 votes explain me briefly what is valid stack stack permutations ? Magma asked Nov 14, 2018 Magma 951 views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Somoshree Datta 5 commented Nov 14, 2018 reply Follow Share Answer is D 0 votes 0 votes srestha commented Nov 14, 2018 reply Follow Share @Somoshree why is it invalid? 0 votes 0 votes Magma commented Nov 14, 2018 reply Follow Share No D ) Total permutation - valid stack permutation :3 0 votes 0 votes Somoshree Datta 5 commented Nov 14, 2018 reply Follow Share 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. 2 votes 2 votes Somoshree Datta 5 commented Nov 14, 2018 reply Follow Share Magma yes..typo :P 0 votes 0 votes Magma commented Nov 14, 2018 reply Follow Share 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 0 votes 0 votes Sayan Bose commented Nov 14, 2018 reply Follow Share 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 0 votes 0 votes Magma commented Nov 14, 2018 reply Follow Share 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 ?? 0 votes 0 votes Somoshree Datta 5 commented Nov 14, 2018 reply Follow Share 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 0 votes 0 votes Sayan Bose commented Nov 14, 2018 reply Follow Share 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 0 votes 0 votes Manas Mishra commented Nov 14, 2018 reply Follow Share @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 0 votes 0 votes Please log in or register to add a comment.