Well, it looks like I didn't leave the oil cap off my car after all: most likely explanation is that engine pressure blew it off in transit. I feel better about that.

Two simple terms are introduced with today's puzzle.

# PERMUTATIONS AND STACKS.

I need to introduce two terms here. The first is that of a "permutation" which is simply a re-ordering.

For example, there is only a single permutation of the number 1, but there are two permutations of the numbers 1..2, namely "1,2" and "2,1". There are more permutations of the numbers 1..3. Some of these are "1,2,3", "1,3,2", "3,2,1"....

The second term I wish to introduce is the notion of a "stack" of numbers, sometimes called a "LIFO" stack (for last-in, first-out). A stack is just a list (it's easier to see why it's called a stack if you imagine the numbers arranged vertically) which you can do two things with: you can "push" a number onto the top of the stack, and you can "pop" a number off the top of the stack.

Starting with the stack 3,2 Pushing 1 onto it gives 1,3,2 Pushing 4 onto it gives 4,1,3,2 Popping 4 off it leaves 1,3,2 Popping 1 off it leaves 3,2
3
2
1
3
2
4
1
3
2
1
3
2
3
2

## Problems:

• 1. How many permutations of 3 numbers are there? Of four? five? Solution
• 2. The general case: how many permutations of N numbers? Additional marks if you can give a reasonable explanation of why. Solution

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.

• 3. How many different permutations of the three numbers can you make on the third stack? Can you make all of them? Solution
• 4. Supposing you start with the numbers 1,2,3,4 on the first stack. How many arrangements can you make on the third stack? Solution
• 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
• 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
• 7. Find the fixed number of stacks that is required to allow you to make all the permutations, however many numbers are in the starting column? (If you don't think it can be done, indicate why not). Solution
• 8. If backwards moves are allowed too, find the fixed number of stacks that is required to allow you to make all the permutations (of the starting numbers) in the final stack, however many numbers are in the starting column. (Again, if you don't think this can be done, say why not). Solution