Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

There are two stacks A and B.

A :  a,b,c,d   ('a' is on top and 'd' is at the bottom of the stack)
B :  (empty)

There are two rules.

If an element of A is popped, it must be printed immediately or pushed into B.
If an element of B is popped, it can only be printed.

So, how many permutations of a,b,c,d are possible? (continue reading)

P.S. Well, I did calculations manually(didn't use any formula) and got 14 as the answer. However, it took around 10 minutes to do the lengthy steps. So, is there an easy way to do this?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

This problem looks like the problem of single stack sorting. "Single" because onle your stack B is used to sort, the stack A is only for input. Donald Knuth has analysed this, and characterized it as the 231-avoiding permutations, and has shown their number equals the Catalan numbers.

Now if my observation is correct, you must have counted wrong (original number you gave was 28). The Catalan numbers are 1, 2, 5, 14, 42, 132,

(added, after you recomputed) Thus, we get a formula, the number of "single-stack sortable permutations of length n" is the $n$-th Catalan number $C_n = \frac 1{n+1}{2n \choose n}$. That does not yet explain the connection. There is a lot to learn about Catalan numbers, see the wiki-page for a lot of situations where they arise! Also the page to the online encyclopedia of integer sequence I referred to has more than enough links to keep you busy for a long time.

share|improve this answer
    
yeah.. I did check again and it was 14.. (i'll change it now) and wow.. amazed at your brilliance.. so, is there any way to calculate it more easily?? like a formula? thanks in advance :) –  VISHNU VIVEK Dec 1 '12 at 12:39
1  
Formula added to Answer. You will enjoy yourself with the many examples in the wikipedia page I linked to, I am certain. –  Hendrik Jan Dec 1 '12 at 13:14
    
thanks.. that is all I needed :) –  VISHNU VIVEK Dec 1 '12 at 13:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.