How many sequences possible in stack , if the input(1,2,3,...,n) is in order?

Question

How many permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence $(1, 2, 3, 4, 5,\dots, n)$ in that order?

Example If $n=5$, then outputs

• $3,4,5,2,1$
• $1,2,3,4,5$
• $5,4,3,2,1$ etc.

are possible, and outputs

• $3,4,5,1,2$
• $1,5,2,3,4$
• $5,4,3,1,2$ etc.

are impossible.

Answer 1

Your guess about Catalan numbers is correct. We have a sequence of numbers (pushes), and each of them is popped at some moment. Write a push as a left bracket and a pop as a right bracket, so that, for instance, the sequence $3,4,5,2,1$ corresponds to $((()()()))$. Then we have a one-to-one correspondence with proper bracket sequences, which are enumerated by Catalan numbers.