I was trying to solve a stack permutation problem in taocp. The question asks us to find no: of permutations of n numbers from 1...n that can be generated using a stack. The no:s 1...n can be pushed into the stack in that order only. When an element is popped of the stack, it is appended to an output queue. Once all elements are in output queue, the order of elements in the queue is a permutation obtained using stack.
For ex:- To obtain 2,3,1 from 1,2,3 we follow the sequence of operations
push 1,push 2,pop 2,push 3,pop 3,pop 1
Not all permutations can be obtained using the stack (for ex: - 3,1,2).
Let the no: of permutations of 1...n be a(n) with a(0) = 1 (only empty permutation possible with no numbers).
We have to find a(n+1)
Suppose that nl no:s appear to left of "1" and nr no:s to right of "1" in a permutation.The process of obtaining a permutation for those nl numbers to the left of "1" can be considered as permuting 2...(nl+1) using a stack (The "1" at the bottom of the stack can be ignored). This no: will be the same as no: of permutations possible for 1...nl using a stack(Only the number of numbers matter).
The term a(n) is simply the nth catalan number.