2. The general case: how many permutations of N numbers? Additional marks if you can give a reasonable explanation of why.
The answer is n!, (pronounced "N factorial"), which is equal to
n x (n-1) x ... x 3 x 2 x 1
Why? Well, consider the process of producing a single permutation. Taking all n numbers, you want to stick them in n slots in some order.
You have n choices of which number to put into the first slot. For each of these choices, you have n-1 choices of which number to put in the second slot, giving you n x (n-1) ways of filling the first two slots.
For each of these, you have n-2 numbers remaining, so there are n-2 choices of a number to fill the third slot. Thus there are n x (n-1) x (n-2) ways to fill the first three slots.
Continuing this argument, there are n! total permutations.
This was due to Spike, and is a nice explanation. Let's suppose there are a number, k, of ways to arrange n-1 numbers.
Then, for each of these arrangements, there are a total of n places we can insert the number n into the sequence to produce a different arrangement of n numbers.
Perhaps an example is in order. Suppose there are k arrangements of the numbers 1..3. Let's pick one: 1,2,3. Then from this arrangement, we can construct 4 permutations of the numbers 1,2,3,4, as follows:
4, 1, 2, 3
1, 4, 2, 3
1, 2, 4, 3
1, 2, 3, 4
Following this argument through, there are a total of kxn permutations. In other words, to get from the number of permutations of n-1 things to the number of permutations of n things, you multiply the previous result by n.
Since there is 1 permutation of the number 1, this means there will be 1x2 permutations of 2 numbers, 1x2x3 permutations of three numbers, and so on.