Hi Evan,

Let me look at going from 3 to 4. There are 3 × 2 × 1 = 6 permutations of the numbers 1, 2 and 3. (Permutation means that order is important so for example 123 is a different permutation than 132.) There are so few permutations of 1, 2 and 3 that I can list them

123
132
213
231
312
321

I can extend each one of them to a permutation of 1, 2, 3 and 4 by inserting the digit 4

before the first number
between the first and second number
between the second and third number, or
after the third number.

For example 213 can be extended to

4213
2413
2143, and
2134.

Thus there are 4 times as many permutations of 1, 2, 3 and 4 as there are permutations of 1, 2 and 3. Hence there are 4 × 3 × 2 × 1 = 24 permutations of 1, 2, 3 and 4.

Now I can extend each of these to a permutation of 1, 2, 3, 4 and 5 by inserting the digit 5

before the first number
between the first and second number
between the second and third number
between the third and fourth number
after the fourth number.

Hence there are 5 × 4 × 3 × 2 × 1 = 120 permutations of 1, 2, 3, 4 and 5.

And so on,
Penny