Stack Doubt

Question

The question basically says no. of different outputs produced for given sequence of input (1,2,...,n)

I thought in terms of push - pop pairs but cant arrive at the answer 

@arjun sir , @bikram sir

Answer 1

I thought in terms of push - pop pairs but cant arrive at the answer 

You are very very close to the answer. Let us first see what we get when $n=3$ and later generalize it.

So for an input sequence, $1,2,3$ following are the possible permutations we can get as output as a result of the pop operations in some order.

$$<1,2,3>, <1,3,2>, <3,2,1>, <2,1,3>, <2,3,1>$$

Note that $<3,1,2>$ is not possible as we have to wait until $3$ is pushed into the stack and then pop it to get it first in the permutation. But at this point, we cannot pop $1$ before $2$.

That gives us $5$ out of $6$ possible permutation of the input sequence. Plug $n=3$ in all the options and you see only option (B) gives us $5$.

---

To obtain certain sequence as output we perform push and pop operation in some order. For every push operation, write down a left parenthesis and for every pop operation, write a corresponding right parenthesis.

For instance, to obtain the sequence $<1,3,2>$ in the above example we do following push pop operation

$$<push(1), pop(1), push(2), push(3), pop(3), pop(2)>$$

After parenthesization substitution we get this $()(())$

Thus for all possible valid permutations possible as an output of push and pop operation in some order is actually all possible enumeration of proper parenthesization which is given by Catalan Number

HTH

Comments

Do you want me to include the proof in my answer? I think that would be a bit vigorous and way beyond the scope of this question.

---

The leftmost parenthesis L matches some right parenthesis R, which must partition the formula into two balanced pieces, the part between L and R, and the part to the right of R. If the left part contains k pairs, the right part must contain n − k − 1 pairs, since L,R represent one pair.

Both of these sub formulas must be well formed, which leads to the recurrence and can be represented by Catlan Number.

Doesnt the above reduces to number of binary trees

---

That is absolutely right. What you just explained is actually establishing one-on-one correspondence with binary trees which gives a recurrence relation something like this -
$$C_{n+1}=\sum_{i=0}^{n-1}C_iC_{n-i-1}$$

I personally think that proving that number of permutation is given by Catalan number is bit harder and vigorous than establishing these relationships. I just stumbled upon this video of MAA that gave a wonderful example of how this really works.

https://youtu.be/eoofvKI_Okg