4
$\begingroup$

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...?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There is a limitation on pop in that as you build the order, you can never have more pops than pushes. How is that shown in your expression for number of different possibilities? $\endgroup$ – dan post Aug 20 at 14:27
  • $\begingroup$ @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. $\endgroup$ – Arthur Aug 20 at 14:30
  • $\begingroup$ Arthur, thank you for the clarification. $\endgroup$ – dan post Aug 20 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.