0
$\begingroup$

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?

$\endgroup$

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.