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?

Stack(push pop) permutations are similar to number of balanced parenthesis

For example: if n = 3, Permutations are

123 ()()()

321 ((()))

231 (()())

213 (())()

132 ()(())

So if n = 6 valid stack permutations will be equal to 6th catalan number which is 132 but how calculate with restriction that 3 comes are 3rd position?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.