# Given $N$ different elements, how many different Possibility there are to Push and Pop all the elements to\from stack

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 -

1. push 1 pop 1 push 2 pop 2 > we will end up with 1,2.
2. push 2 pop 2 push 1 pop 1 > we will end up with 2,1.
3. push 1 push 2 pop 2 pop 1 > we will end up with 2,1.
4. 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.
• @danpost That's what the Catalan numbers $C_n$ are for. That's exactly what they count. They were mentioned in the question, so I didn't think to clarify them. I will do so. – Arthur Aug 20 at 14:30