There are n different elements,
already know the order each element is pushed in.
How many different kinds of combination can there be for the poping order?
EDIT
In fact I know there are 2n!/(n+1)n!^2 combinations,but why?
+1
A:
A stack can be popped in only a single order -- the reverse of the order the elements were pushed.
AttishOculus
2009-11-29 07:58:34
Yes, but the OP does not specify that all of the pushes occur before any pops (or vice versa).
Amber
2009-11-29 08:00:07
@Dav I don't see how the interleaving of pushes and pops affects the order of pops, if it's truly a stack then the items pop off in the order they were pushed, end of story. So we can choose an order of pushes and vary that, but that's not very interesting, that's just simple combinations.
djna
2009-11-29 09:32:36
Too bad the owner of the question doesn't care enough to phrase the question properly, so that we won't have to guess what xe meant...
AttishOculus
2009-11-29 15:45:10
@djna ... suppose you pop each item immediately after it's pushed? Then the pop order is the same as the push order, exactly the opposite of when you first push them all on and then pop them all off.
Eric
2009-11-29 17:01:12
+1, the original question doesn't seem to make much sense. In a stack, LIFO is the only possible order to pop.
ammoQ
2009-12-03 09:05:22
+1
A:
Suppose your elements are called A, B, C, ... and pushed in that order.
Let P(X) mean "Push X" and O(X) mean "Pop X"
Let N be the number of elements.
So what are the pop orders?
Possibilities when N=1: P(A)O(A). (i.e. "A")
Possibilities when N=2: P(A)P(B)O(B)O(A). ("BA") P(A)O(A)P(B)O(B). ("AB")
Possibilities when N=3: ABC and BAC (from above, followed by P(C)O(C).) CBA. (from P(A)P(B)P(C)O(C)O(B)O(A).) But not CAB, since if "C" comes off first, it must have gone on last, so nothing else has come off yet, so they can only come off in the order BA.
Building from that pattern, you should be able to construct and solve a recurrence relation that gives the answer you need.
Eric
2009-11-29 16:52:48
A:
Nice one Eric. However, when I tried with ABC, I got 4 possibilities, ABC, BAC, BCA and CBA.
Pity the formula presented is not clear, because I can't make n=3 give an answer of 4 from simple interpretations of what was written above.
Induction would seem to be the answer to proving the formula (as it often is when the question is of the form "prove that ... is given by formula ...").
And there is a certain symmetry in the four possibilities above, which makes me think it might not be too difficult to come up with the answer.
EDIT: Actually, can't we get ACB also? AaBCcb. Where uppercase letters are a push, lowercase a pop. So, 5 possibilities, CAB is definitely not possible.
Tony van der Peet
2009-12-03 08:55:29