#made easy

Question

Stack A has entries a,b,c,d(with a on top).Stack B is empty.

An entry popped out of stack A is pushed into stack B.

An entry popped out of stack B can only be printed.

The no. of possible permutation for printing the elements are __ ?

1. 24
2. 12
3. 21
4. 14

can anybody give a generalized formula with explanation for this ?

Answer 1

This problem can be interpreted as

how many distinct arrangements of n pairs of left-right parentheses are there all of which close?

how? consider push(a)  to be first opening opening parenthesis and pop(a) to be first closing parenthesis

similarly push(b) to be first second opening parenthesis and pop(b) to be second closing parenthesis

similarly for c and d

Answer to this question is nth catalan number

$\large C_n = \frac{1}{n+1} \binom{2n}{n}$

In our question n= 4,

$\large C_n = \frac{1}{4+1} \binom{8}{4} = \frac{1}{5} \times 70 = \color{red}{14}$

Comments

great answer