PERMUTATIONS AND STACKS.

Question 5

OK, the scenario is this: supposing you've got three stacks. The first stack has the numbers 1, 2, 3 on it in order from top-to-bottom (ie, the first number you can pop off the stack is 1, then 2, then 3). The second and third stacks are empty.

You're allowed two kinds of moves. You can either pop a number off the first stack and push it onto the second stack, or pop a number off the second stack and push it onto the third stack. "Backwards" moves are not allowed. You have to move all the numbers from the first stack to the third.

5. (Harder) Can you work out a method (without trying them all) of calculating the number of permutations achievable starting with N numbers on the first stack?

Solution

You can be clever here; first, here's a method to just count them.

Start with numbers on the first stack.


Press this button to calculate obtainable permutations of n numbers using s stacks:

Alternative solution

This alternative relies on the fact that, for the three-stack case, there is one and only one sequence of moves to produce any obtainable final permutation.

Proof

An indication of the proof of the above statement is as follows. I don't dot the i's and cross the t's because it's a little tedious.

Consider some final permutation p1,...,pn of the starting position 1,...,n. Suppose there are two sequences of moves, M=m1,...,m2n and M'=m'1,...,m'2n which produce this final result, where each mi and each m'i are of the form 1->2 or 2->3.

Let the first position at which M and M' differ be i. At this time, suppose that the numbers at the top of each of the first two stacks are pj and pk.

If mi is 1->2 and m'i is 2->3 then clearly the final permutations obtained by these two sequences cannot be the same; for pj and pk will have to appear in the final permutations in a different order.

A symmetrical argument holds if mi is 2->3 and m'i is 1->2.

Consequently, the supposition that there are two different sequences which produce the same final permutation must be false.