Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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 (updated) 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
add comment

1 Answer

up vote 2 down vote accepted

You appear to have over-counted: there are actually $14$ possible permutations, which I list below:

$$\begin{array}{} abcd&abdc&acbd&acdb&adcb\\ bcda&bdca&cbda&cdba&dcba\\ bacd&badc&bcad&cbad \end{array}$$

These are the stack-sortable permutations of $a,b,c,d$. In general there are $C_n$ stack-sortable permutations of $a_1,\dots,a_n$, where $$C_n=\frac1{n+1}\binom{2n}n$$ is the $n$-th Catalan number; they are also the permutations that avoid the pattern $231$.

Added: Let $\sigma$ be the sequence of pops and pushes that produces a stack-sortable permutation $\pi$ of $a_1,\dots,a_n$. Each time an element is printed from $A$, write down the string (); each time an element is pushed onto $B$, write down (; and each time one is popped off $B$ and printed, write down ). It’s not hard to see that the result is a correctly matched string of $n$ left and $n$ right parentheses. Conversely, if you start with a correctly matched string of $n$ left and $n$ right parentheses, interpret each ( as an instruction to pop the top element of $A$ and push it onto $B$, and interpret each ) as an instruction to pop the top element of $B$ and print it, you’ll produce a stack-sortable permutation of $a_1,\dots,a_n$. (Printing an element directly from $A$ is equivalent to popping it from $A$ and pushing it onto $B$, then popping it from $B$ and printing it.)

This describes a bijection between the stack-sortable permutations of $a_1,\dots,a_n$ and the correctly matched strings of $n$ left and $n$ right parentheses, and it is well known that there are $C_n$ of the latter.

share|improve this answer
    
Thanks a lot Brian!! btw are there any real time examples for 231 pattern avoiding permutations.. I mean.. why should we avoid them?? –  VISHNU VIVEK Dec 2 '12 at 11:50
1  
@Vishnu: You’re welcome! It’s not that we should avoid them; it’s just that they, like other combinatorial objects counted by the Catalan numbers, seem to come up quite often. –  Brian M. Scott Dec 2 '12 at 11:54
    
Oh I see.. thanks again Brian :) anyhow..I'll ask a separate question regarding the 231-pattern and try to learn more about it.. there's not a lot about this in the net either.. :) –  VISHNU VIVEK Dec 2 '12 at 12:05
    
I posted the question here, but not much luck.. Then I read your profile sir and I can see that you are the right man for this question :) So, if there are 3 stacks with the same rules applied, will the same formula work for that too? or should I go for a different approach.. –  VISHNU VIVEK Dec 2 '12 at 12:55
    
the deeper I go into programming, the deeper I get entangled in the excitement of Mathematics! –  VISHNU VIVEK Dec 2 '12 at 12:58
show 2 more comments

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.