1
$\begingroup$

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?

1 Answers 1

2

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.

  • 0
    the first version was the one which I had in mind.. I tried yesterday, but the same formula wasn't helping.. then I referred in the net and found that there was a 2-stack sortable permutation.. but couldn't find any formula associated with it..so I think there isn't any easy method to solve it.. If u get any info regarding this in the future, do tell me.. thanks :)2012-12-03