PERMUTATIONS AND STACKS.

Question 6

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.

6. How many arrangements can you make of 3, 4, 5 numbers if you have four stacks instead of three? Again, you're only allowed to move from the first stack to the second, from the second to the third, or from the third to the last stack (no backwards moves).

Solution

For 3 numbers, you can get all 6 permutations; for 4 numbers, you can make all 24 permutations. For 5 numbers, you can make all 120 permutations. You can also make all 720 combinations of 6 numbers, but only 5018 of the 5040 possible combinations of 7 numbers.

A form is given below where you can try this out; however, I don't recommend that you try much more than 5 numbers and 4 stacks!

Start with numbers on the first stack.

Use a total of stacks.

Found so far:

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