Given $N$ different elements, how many different possibilities there are to Push and Pop all the elements to\from a stack?
In the beginning, the stack is empty and every element can be pushed to the stack only once.
Example: Given 2 elements {$1,2$} the ways, we can push and pop them -
- push 1 pop 1 push 2 pop 2 > we will end up with 1,2.
- push 2 pop 2 push 1 pop 1 > we will end up with 2,1.
- push 1 push 2 pop 2 pop 1 > we will end up with 2,1.
- push 2 push 1 pop 1 pop 2 > we will end up with 1,2.
I have tried as following:
Catalan numbers - using this formula I've "changed" every element into a "( )" when "(" = to push and ")" = to pop. That gave me that for every number $N$ I would have: $Cn={1\over n+1} * {2n\choose n}$
But it seems like when I use that formula it doesn't count every element as an individual, meaning that I miscount possibilities by doing that.
What am I missing...?
We want to decide on an order of pushes and pops, and we want to decide on an order in which the numbers are pushed. That gives us $C_n\cdot n!$ different possibilities, where $C_n = \frac1{n+1}\binom{2n}{n}$ is the $n$th Catalan number.
For instance, in your examples, the top two have push, pop, push, pop while the bottom two have push, push, pop, pop. Then for each of those push-pop-orders, we either first push $1$ first then $2$, or we push $2$ first then $1$ next.